首页 > 代码库 > 算法总结之拓扑排序

算法总结之拓扑排序

拓扑排序

1.一般应用

      拓扑排序常用来确定一个依赖关系集中,事物发生的顺序。例如,在日常工作中,可能会将项目拆分成A、B、C、D四个子部分来完成,但A依赖于B和D,C依赖于D。为了计算这个项目进行的顺序,可对这个关系集进行拓扑排序,得出一个线性的序列,则排在前面的任务就是需要先完成的任务。

2.实现的基本方法

  (1)从有向图中选择一个没有前驱(即入度为0)的顶点并且输出它.

  (2)从网中删去该顶点,并且删去从该顶点发出的全部有向边.

  (3)重复上述两步,直到剩余的网中不再存在没有前趋的顶点为止.

3.C++版本实现

 1 /*以邻接矩阵Edge[A][B]=N存放图信息:A指向B,权值为N*/ 2 /*假设不相连的边的Edge==INT_MAX*/ 3 void Topo() 4 { 5     sort(Edge+1,Edge+N+1); 6     for (int i=1; i<=N; i++) 7     { 8         int j; 9         for (j=1; j<=N; i++)  //vis为标记数组,标记是否已经存在在Topo数组中10             if (!vis[j]&&!in[j]) //in数组表示的下标顶点的入度11             {12                 Topo[i]=j;13                 vis[j]=1;14                 break;15             }16         for (int k=1;k<=N;k++) //将与j点相连的顶点的入度刷新17             if (Edge[j][k]!=INT_MAX)18                 in[k]--;19     }20 }

4.反向建图

  拓扑排序并不一定唯一,有时会要求顶点数值大的尽量在前,这个时候应该反向建图,再进行拓扑排序,来保证更多小数值顶点在后面。(贪心思想?)

  Eg:HDU 4857 POJ 3687(反向建图+拓扑排序)

5.优化

  拓扑排序每次选择一个顶点进入序列后,要更新所有与这个顶点相连的顶点的入度。而上面的代码全是把所有的顶点都遍历了一边。

  这里可以使用邻接表或者链式前向星这一类数据结构,来记录图的信息,可以做到只遍历与该顶点相连的顶点

6.优先队列实现

 1 /*优先队列+邻接表实现拓扑排序*/ 2 void Topo() 3 { 4     priority_queue<int> que; 5     for (int i=1; i<=N; i++) //将入度为零的顶点压入队列 6         if (dis[i]==0) 7             que.push(i); 8     int p=N+1; 9     while (!que.empty())10     {11         int tmp=que.top();12         que.pop();13         topo[--p]=tmp;     //存入topo数组14         int z=first[tmp];15         while (z!=-1)       //邻接表遍历与tmp相连的顶点16         {17             dis[end[z]]--; //入度减一18             if(!dis[end[z]]) que.push(end[z]);19             z=next[z];20         }21     }22 }