[code=c]
#include "bool.h"
#include "graph.h"
#include "queue.h"


void compute_indegrees(graph *g, int in[])
{
    int i,j;            /* counters */

    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];        /* 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);
    for (i=1; i<=g->nvertices; i++)
        if (indegree[i] == 0) enqueue(&zeroin,i);

    j=0;
    while (empty(&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,TRUE);
    print_graph(&g);

    topsort(&g,out);

    for (i=1; i<=g.nvertices; i++)
        printf(" %d",out[i]);
    printf("\n");

}

[/code]

Copied from
http://www.cs.sunysb.edu/~skiena/392/programs/topsort.c

看不懂~~~能写出思路吗?

每次挑选入度为0的顶点，然后删去从这个点出发的所有边。循环往复。如果找不到这样的点，说明图中有环，无法拓扑排序。

思路

[quote]
[b]Topological Sort Algorithm[/b]
A: Direct Acyclic Graph(DAG), Sort the nodes in such order, if we have an edge E(u, v), u must before v in the sorted list.
It is very useful in scheduling, a possible sequence of activities which considers all requirements ( availability of material - storage - processing - sale). 
[b]In school, since the course has its prerequisite courses, scheduling might affect your graduation date. Here is one algorithm.[/b]

   1. Find a node without predecessor
   2. Append the node at the end of the sorted list
   3. 'Remove' the node and all its edges
   4. Repeat step 1 until the graph is empty
[/quote]

Copied from
[url]http://bobcat.webappcabaret.net/javachina/faq/algo_01.htm#algo_Q5051[/url]