前一篇，学习了根据DFS，来进行拓扑排序的方法；今天看一下，按照贪婪算法来进行拓扑排序。主要的思想：找没有入度的顶点，放到队列里面；然后，逐渐从队列里删除顶点，加入一个数组，如果产生了新的没有入度的顶点，也加入队列，重复直到队列为空。

#include<stdio.h>
#include<stdlib.h>
#include"graph.c"
#include"queue.c"
#define MAX 100

int indeg[MAX];
int vl[MAX];
int *q;
void topolsort(Graph g){
    int i,nv;

    nv=g->nv;
    for(i=0;i<nv;i++){
        struct node * vnode;
        vnode=g->adj[i];
        while(vnode){
            int u;
            u=vnode->v;
            indeg[u]++;
            vnode=vnode->next;
        }
    }
    q=initq(nv);
    
    for(i=0;i<nv;i++)
        if(indeg[i]==0)
            add(q,i);
            
    int iv;
    iv=0;
    while(!isempty()){
        int u;
        u=delete(q);
        vl[iv++]=u;

        struct node * unode;
        unode=g->adj[u];
        while(unode){
            int v;
            v=unode->v;
            if(!(--indeg[v]))
                add(q,v);
            unode=unode->next;
        }
    }
     
}

int main(){
    Graph  g;
    int n=6;
    g=init(n);

    edge e[8];
    e[0].u=0;e[0].v=2;
    e[1].u=0;e[1].v=3;
    e[2].u=1;e[2].v=3;
    e[3].u=1;e[3].v=4;
    e[4].u=2;e[4].v=3;
    e[5].u=2;e[5].v=5;
    e[6].u=3;e[6].v=5;
    e[7].u=4;e[6].v=5;


    int i;
    for(i=0;i<g->ne;i++)
        insert(g,e[i]);
    topolsort(g);
    for(i=0;i<g->nv;i++)
      printf("%d ",vl[i]);
    printf("\n");
    return 0;
}

时间复杂度分析：有向图的表示采用了邻接链表，所以时间复杂度为：Θ(V+E)。