拓扑排序 C 代码

2016-08-01 11:48:50 暂无评论阳光倾城算法与数据结构 814

拓扑排序 C 代码

/* topsort.c
    Topologically sort a directed acyclic graph (DAG)
    by: Steven Skiena
    begun: March 26, 2002
*/
/*
Copyright 2003 by Steven S. Skiena; all rights reserved.
Permission is granted for use in non-commerical applications
provided this copyright notice remains intact and unchanged.
This program appears in my book:
"Programming Challenges: The Programming Contest Training Manual"
by Steven Skiena and Miguel Revilla, Springer-Verlag, New York 2003.
See our website www.programming-challenges.com for additional information.
This book can be ordered from Amazon.com at
https://www.amazon.com/exec/obidos/ASIN/0387001638/thealgorithmrepo/
*/
#include "bool.h"
#include "graph.h"
#include "queue.h"
compute_indegrees(graph *g, int in[])
{
    int i,j;            /* counters */

}
topsort(graph *g, int sorted[])
{
    int indegree[MAXV];     /* indegree of each vertex */
    queue zeroin;           /* vertices of indegree 0 */
    int x, y;           /* current and next vertex */
    int i, j;           /* counters */
    compute_indegrees(g,indegree);
    init_queue(&zeroin);

        if (indegree[i] == 0) enqueue(&zeroin,i);
    j=0;
    while (empty(&zeroin) == FALSE) {
        j = j+1;
        x = dequeue(&zeroin);
        sorted[j] = x;

            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);
}
main()
{
    graph g;
    int out[MAXV];
    int i;
    read_graph(&g,TRUE);
    print_graph(&g);
    topsort(&g,out);

        printf(" %d",out[i]);
    printf("\n");
}