GroupBlog

拓扑排序

在一个表示工程的有向图中,有顶点表示活动,用弧表示活动之间的优先关系,这样的有向图为顶点表示活动的网,我们称为AOV网,所谓的拓扑排序，其实就是对一个有向图构造拓扑序列的过程,如果该有向图是无环的，则拓扑排序可以成功，否则，则不能成功.

算法思想:

从AOV网中选择一个入度为0的节点输出;

然后删除此节点,并删除以此节点为尾的弧;

继续重复此操作，直到输出全部顶点或AOV网中不存在入度为0的顶点为止.

如果输出的节点个数等于原图的顶点个数，则拓扑排序成功，此有向图中无环, 否则，该图有环.

先看代码,用实际例子来说:

void FindID(AdjList *G,int indegree[MAXVEX])   //求出每个顶点的入度，保存在indegree数组中.
{
    int i;
    ArcNode *p;
    for(i=1;i<=G->vexnum;i++){
        indegree[i]=0;
    }
    for(i=1;i<=G->vexnum;i++){
        p=G->vertex[i].head->next;
        while(p){
            //printf("%d\n",p->adjvex);
            indegree[p->adjvex]++;
            p=p->next;
        }
    }
}
int TopoSort(AdjList *G)
{
    LinkQueue *Q;
    int indegree[MAXVEX];
    int i,count;
    ArcNode *p;
    FindID(G,indegree);
    Q=Init_LinkQueue(Q);
    for(i=1;i<=G->vexnum;i++){     //首先，将所有的入度为0的顶点入队;
        if(indegree[i] == 0){
            EnterQueue(Q,i);
        }
    }
    count=0;
    while(!IsEmpty_LinkQueue(Q)){
        OutQueue(Q,&i);                          //出队
 //       printf("%d\n",i);
        printf("%c",G->vertex[i].vexdata);
        count++; 
        p=G->vertex[i].head->next;                //遍历以此顶点为尾弧的顶点,并让对应顶点的入度减1.如果入度为0,就入队.
        while(p){
            indegree[p->adjvex]--;
            if(indegree[p->adjvex] == 0){
                EnterQueue(Q,p->adjvex);
            }
            p=p->next;
        }
    }
    if(count < G->vexnum){                      //如果输出的节点个数少于顶点，则说明有环
        return 0;
    }
    return 1;
}

以此图为例：

分别求得它们的入度:

下标: 1 2 3 4 5 6 7 8

data: A B C D E F G H

入度：0 0 1 2 2 2 2 1

程序运行步骤:

1.首先遍历indegree数组，选择入度为0的顶点对应的下标入队.

2.在队不为空的前提下,(A)1出队，(3)C的入度减1成为0，所以3入队,G的入度减为1';

3.(B)出队,G的入度减为0，7入队.H的入度也减为0，8入队,

4.(C)出队,D的入度减为1;

5(G)出队,D的入度减为 0,4入队,F的入度减为1;

6.(H)出队,F的入度减为1，6入队.

7.(D)出队,E的入度减为1.

8.(F)出队,E的入度减0,

9(E)出队;

10,因为count 等于顶点数,所以拓扑排序成功,该图是有向无环图.