топологическая сортировка

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

Я не уверен, что именно вы имеете в виду.

Вы хотите проверить, действительно ли это DAG, прежде чем пытаться выполнить топологическую сортировку? Трюк с топологической сортировкой заключается в том, что она автоматически завершается неудачей, если есть цикл. Поэтому сама топологическая сортировка является тестом на DAGness (и я не думаю, что есть более простой). Таким образом, вместо того, чтобы сначала проверять, является ли граф DAG, вы просто пытаетесь топологически отсортировать его. Если вы преуспели, это была группа DAG, и вы закончили, если вы потерпели неудачу, это была не группа DAG, и вы можете просто сообщить об этом пользователю, т. Е. Вы также закончили.

Или вы запрашиваете возможный входной файл, который будет описывать DAG (чтобы вы могли проверить на нем свой код)?

Если я правильно понимаю ваш формат ввода, должно быть следующее:

6 8
1 2
1 3
2 3
2 5
3 6
4 5
4 6
5 6

Следует описать следующий график:

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

(надеюсь, вы понимаете мое искусство ASCII)

Answer 2

Вы можете определить правильный формат ввода, изучив функцию 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 вершинами:

6 8
[eight lines of edges here]