拓扑排序

我有下面的代码，但我不能实现它，因为我不知道如何使用它的顶点来表示DAG。拓扑排序

#include<iostream> 
#include "queue.h" 
#include "graph.h" 
#include "bool.h" 
using namespace std; 

void init(Queue *q) 
{ 
    q->first=0; 
    q->last=queuesize-1; 
    q->count=0; 
} 

void enqueue(Queue *q,int x) 
{ 
    if(q->count>=queuesize) 
    { 
     cout<<"queue overflow "<<endl; 
    } 
    else 
    { 
     q->last=(q->last+1)%queuesize; 
     q->q[q->last]=x; 
     q->count=q->count+1; 
    } 
} 

int dequeue(Queue *q) 

    int x; 
    if(q->count<=0) 
    { 
     cout<<" empthy "<<endl; 
    } 
    else 
    { 
     x=q->q[q->first]; 
     q->first=(q->first+1)%queuesize; 
     q->count=q->count-1; 
    } 
    return x; 
} 

int empthy_queue (Queue *q) 
{ 
    if(q->count<=0) 
    { 
     return TRUE; 
    } 
    return FALSE; 
} 

void initialize (graph *g) 
{ 
    int i; 
    g->nvertices=0; 
    g->nedges=0; 
    for(i=1; i<=maxv; i++) 
    { 
     g->degree[i]=0; 
    } 
} 

void insert(graph *g,int x,int y,boolean directed) 
{ 
    if(g->degree[x]>maxdegree) 
    { 
     cout<<"degree overflow"; 
    } 
    g->edges[x][g->degree[x]]=y; 
    g->degree[x]++; 
    if(directed==FALSE) 
    { 
     insert(g,y,x,TRUE); 
    } 
    else 
    { 
     g->nedges++; 
    } 
} 

void read_graph(graph *g,boolean directed) 
{ 
    int i; 
    int m; 
    int x,y; 
    initialize(g); 
    cin>>g->nvertices>>m; 
    for(i=1; i<=m; i++) 
    { 
     cin>>x>>y; 
     insert(g,x,y,directed); 
    } 

} 


void cpmpute_degree(graph *g,int in[]) 
{ 
    int i,j; 

    for(i=1; i<=g->nvertices; i++) 
    { 
     in[i]=0; 
    } 
    for(i=1; i<=g->nvertices; i++) 
     for(j=0; j<g->degree[i]; j++) 
     { 
      in[g->edges[i][j]]++; 
     } 

} 

void topsort(graph *g,int sorted[]) 
{ 
    int indegree[maxv]; 
    int x,y; 
    Queue zeroin; 
    int i,j; 
    cpmpute_degree(g,indegree); 
    init(&zeroin); 
    for(i=1; i<=g->nvertices; i++) 
     if(indegree[i]==0) 
     { 
      enqueue(&zeroin,i); 
     } 
    j=0; 
    while(empthy_queue(&zeroin)==FALSE) 
    { 
     j=j+1; 
     x=dequeue(&zeroin); 
     sorted[j]=x; 
     for(i=0; i<g->degree[x]; i++) 
     { 
      y=g->edges[x][i]; 
      indegree[y]--; 
      if(indegree[y]==0) 
      { 
       enqueue(&zeroin,y); 
      } 
     } 
    } 

    if(j!=g->nvertices) 
    { 
     printf("Not a DAG -- only %d vertices found\n",j); 
    } 
} 

int main() 
{ 
    graph g; 
    int out[maxv]; 
    int i; 
    read_graph(&g,false); 
    topsort(&g,out); 
    for(i=1; i<=g.nvertices; i++) 
    { 
     cout<<out[i]<<" "; 
    } 



    return 0; 
}

请告诉我如何从键盘读取图形，使给定的图形应该是DAG？我的意思是这一个

等等。假设顶点是6个边8 请帮助我，当我进入图形几次，它写了这个输出

printf("Not a DAG -- only %d vertices found\n",j);

请给我正确的输入图形（顶点6，边8）

来源

2011-11-17 dato datuashvili

啊，所以你有一个含糊不清的代码模糊的问题：让我来帮你！如果你展示了产生该输出的实际特定输入，解释了为什么你认为这是错误的，以及到目前为止已经做了什么来解释它，这可能会有所帮助。 – Useless

假设输入像这样1-2 2-3 3-4 4-5 5-6 6-7 7-1（7个顶点，7个边） –

真的没有理由将'Graph'实例作为指针。改用引用（在适当的地方使用'const'）。 –

您可以通过调查你的read_graph功能推断正确输入格式：

void read_graph(graph *g,boolean directed){ 
int i; 
int m; 
int x,y; 
initialize(g); 
cin>>g->nvertices>>m; 
for(i=1;i<=m;i++){ 
    cin>>x>>y; 
    insert(g,x,y,directed); 
}

在nvertices然后第一cin存储用户输入。之后使用m来遍历剩余的输入，所以它等于边的数量。

下面的每一行表示图中的一条边。据推测，这两个数字代表起始节点和结束节点。

所以，正确的输入，生成6个顶点8边图中的是：

6 8 
[eight lines of edges here]

来源

2011-11-17 14:26:01 Kevin

不，我有问题如何通过DAG，以便不应该有周期请帮助我与这些 –

图形是否是DAG取决于用户通过什么。如果他给你一个循环图，没有任何你可以做到这一点。 – Kevin

是的，但我的问题是如何使用我的x和y点来表示DAG图表，以便不创建循环，请让我为图表示例 –

我不知道究竟你的意思。

您的意思是在尝试拓扑排序之前检查它确实是否是DAG？那么，拓扑排序的诀窍是，如果有一个循环，它会自动失败。因此，拓扑排序本身就是DAGness的一个测试（我认为没有更简单的测试）。因此，不是首先测试该图是否为DAG，而是尝试对其进行拓扑分类。如果你成功了，那是一个DAG，如果你失败了，你就完成了，它不是DAG，你可以告诉用户，即你也完成了。

或者您是否要求输入可能会描述DAG的文件（以便您可以测试您的代码）？

如果我正确理解你的输入格式，下面应该是：

它应该描述如下图：

1 ------> 2 ----- 
\  |  \ 
    \  |  V 
    \  | 4 -> 5 
    \  | \ | 
    \ V  V V 
    ---> 3 ----> 6

（我希望你能understad我的ASCII艺术）

来源

2011-11-17 16:39:25 celtschk

回答

相关问题