c++ - 拓扑排序

Question

我有以下代码，但我无法实现它，因为我不确定如何使用其顶点表示 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？我是说这个

1 2 
2 3 
3 4
4 5 

等等。假设顶点为 6，边为 8。请帮助我，当我多次进入图表时，它写下了这个输出

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

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

Answer 1

您可以通过调查您的 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);
}

第一个 cin 将用户输入存储在 nvertices 中，然后是 m。 m 稍后用于迭代剩余的输入，因此它等于边数。

后面的每一行代表图中的一条边。据推测，这两个数字分别代表开始节点和结束节点。

因此，生成 6 顶点 8 边图的正确输入是:

6 8
[eight lines of edges here]