18、【图】拓扑排序

一、拓扑排序介绍

拓扑排序(Topological Order)是指，将一个有向无环图(Directed Acyclic Graph简称DAG)进行排序进而得到一个有序的线性序列。

这样说，可能理解起来比较抽象。下面通过简单的例子进行说明！
例如，一个项目包括A、B、C、D四个子部分来完成，并且A依赖于B和D，C依赖于D。现在要制定一个计划，写出A、B、C、D的执行顺序。这时，就可以利用到拓扑排序，它就是用来确定事物发生的顺序的。

在拓扑排序中，如果存在一条从顶点A到顶点B的路径，那么在排序结果中B出现在A的后面。

二、拓扑排序的算法图解

拓扑排序算法的基本步骤：

1. 构造一个队列Q(queue) 和拓扑排序的结果队列T(topological)；
2. 把所有没有依赖顶点的节点放入Q；
3. 当Q还有顶点的时候，执行下面步骤：
3.1 从Q中取出一个顶点n(将n从Q中删掉)，并放入T(将n加入到结果集中)；
3.2 对n每一个邻接点m(n是起点，m是终点)；
3.2.1 去掉边<n,m>;
3.2.2 如果m没有依赖顶点，则把m放入Q;
注：顶点A没有依赖顶点，是指不存在以A为终点的边。

以上图为例，来对拓扑排序进行演示。

第1步：将B和C加入到排序结果中。
    顶点B和顶点C都是没有依赖顶点，因此将C和C加入到结果集T中。假设ABCDEFG按顺序存储，因此先访问B，再访问C。访问B之后，去掉边<B,A>和<B,D>，并将A和D加入到队列Q中。同样的，去掉边<C,F>和<C,G>，并将F和G加入到Q中。
    (01) 将B加入到排序结果中，然后去掉边<B,A>和<B,D>；此时，由于A和D没有依赖顶点，因此并将A和D加入到队列Q中。
    (02) 将C加入到排序结果中，然后去掉边<C,F>和<C,G>；此时，由于F有依赖顶点D，G有依赖顶点A，因此不对F和G进行处理。
第2步：将A,D依次加入到排序结果中。
    第1步访问之后，A,D都是没有依赖顶点的，根据存储顺序，先访问A，然后访问D。访问之后，删除顶点A和顶点D的出边。
第3步：将E,F,G依次加入到排序结果中。

因此访问顺序是：B -> C -> A -> D -> E -> F -> G

三、拓扑排序的代码说明

拓扑排序是对有向无向图的排序。下面以邻接表实现的有向图来对拓扑排序进行说明。

1. 基本定义

 1 #define MAX 100
 2 // 邻接表
 3 class ListDG
 4 {
 5     private: // 内部类
 6         // 邻接表中表对应的链表的顶点
 7         class ENode
 8         {
 9             int ivex;           // 该边所指向的顶点的位置
10             ENode *nextEdge;    // 指向下一条弧的指针
11             friend class ListDG;
12         };
13 
14         // 邻接表中表的顶点
15         class VNode
16         {
17             char data;          // 顶点信息
18             ENode *firstEdge;   // 指向第一条依附该顶点的弧
19             friend class ListDG;
20         };
21 
22     private: // 私有成员
23         int mVexNum;             // 图的顶点的数目
24         int mEdgNum;             // 图的边的数目
25         VNode *mVexs;            // 图的顶点数组
26 
27     public:
28         // 创建邻接表对应的图(自己输入)
29         ListDG();
30         // 创建邻接表对应的图(用已提供的数据)
31         ListDG(char vexs[], int vlen, char edges[][2], int elen);
32         ~ListDG();
33 
34         // 深度优先搜索遍历图
35         void DFS();
36         // 广度优先搜索（类似于树的层次遍历）
37         void BFS();
38         // 打印邻接表图
39         void print();
40         // 拓扑排序
41         int topologicalSort();
42 
43     private:
44         // 读取一个输入字符
45         char readChar();
46         // 返回ch的位置
47         int getPosition(char ch);
48         // 深度优先搜索遍历图的递归实现
49         void DFS(int i, int *visited);
50         // 将node节点链接到list的最后
51         void linkLast(ENode *list, ENode *node);
52 };

(1) ListDG是邻接表对应的结构体。 mVexNum是顶点数，mEdgNum是边数；mVexs则是保存顶点信息的一维数组。
(2) VNode是邻接表顶点对应的结构体。 data是顶点所包含的数据，而firstEdge是该顶点所包含链表的表头指针。
(3) ENode是邻接表顶点所包含的链表的节点对应的结构体。 ivex是该节点所对应的顶点在vexs中的索引，而nextEdge是指向下一个节点的。

2. 拓扑排序

 1 /*
 2  * 拓扑排序
 3  *
 4  * 返回值：
 5  *     -1 -- 失败(由于内存不足等原因导致)
 6  *      0 -- 成功排序，并输入结果
 7  *      1 -- 失败(该有向图是有环的)
 8  */
 9 int ListDG::topologicalSort()
10 {
11     int i,j;
12     int index = 0;
13     int head = 0;           // 辅助队列的头
14     int rear = 0;           // 辅助队列的尾
15     int *queue;             // 辅组队列
16     int *ins;               // 入度数组
17     char *tops;             // 拓扑排序结果数组，记录每个节点的排序后的序号。
18     ENode *node;
19 
20     ins   = new int[mVexNum];
21     queue = new int[mVexNum];
22     tops  = new char[mVexNum];
23     memset(ins, 0, mVexNum*sizeof(int));
24     memset(queue, 0, mVexNum*sizeof(int));
25     memset(tops, 0, mVexNum*sizeof(char));
26 
27     // 统计每个顶点的入度数
28     for(i = 0; i < mVexNum; i++)
29     {
30         node = mVexs[i].firstEdge;
31         while (node != NULL)
32         {
33             ins[node->ivex]++;
34             node = node->nextEdge;
35         }
36     }
37 
38     // 将所有入度为0的顶点入队列
39     for(i = 0; i < mVexNum; i ++)
40         if(ins[i] == 0)
41             queue[rear++] = i;          // 入队列
42 
43     while (head != rear)                // 队列非空
44     {
45         j = queue[head++];              // 出队列。j是顶点的序号
46         tops[index++] = mVexs[j].data;  // 将该顶点添加到tops中，tops是排序结果
47         node = mVexs[j].firstEdge;      // 获取以该顶点为起点的出边队列
48 
49         // 将与"node"关联的节点的入度减1；
50         // 若减1之后，该节点的入度为0；则将该节点添加到队列中。
51         while(node != NULL)
52         {
53             // 将节点(序号为node->ivex)的入度减1。
54             ins[node->ivex]--;
55             // 若节点的入度为0，则将其"入队列"
56             if( ins[node->ivex] == 0)
57                 queue[rear++] = node->ivex;  // 入队列
58 
59             node = node->nextEdge;
60         }
61     }
62 
63     if(index != mVexNum)
64     {
65         cout << "Graph has a cycle" << endl;
66         delete queue;
67         delete ins;
68         delete tops;
69         return 1;
70     }
71 
72     // 打印拓扑排序结果
73     cout << "== TopSort: ";
74     for(i = 0; i < mVexNum; i ++)
75         cout << tops[i] << " ";
76     cout << endl;
77 
78     delete queue;
79     delete ins;
80     delete tops;
81 
82     return 0;
83 }

说明：
(01) queue的作用就是用来存储没有依赖顶点的顶点。它与前面所说的Q相对应。
(02) tops的作用就是用来存储排序结果。它与前面所说的T相对应。

三、拓扑排序的C++实现

  1 /**
  2  * C++: 无回路有向图(Directed Acyclic Graph)的拓扑排序
  3  *      该DAG图是通过邻接表实现的。    7  */
  8 
  9 #include <iomanip>
 10 #include <iostream>
 11 #include <vector>
 12 #include <cstring>
 13 using namespace std;
 14 
 15 #define MAX 100
 16 // 邻接表
 17 class ListDG
 18 {
 19     private: // 内部类
 20         // 邻接表中表对应的链表的顶点
 21         class ENode
 22         {
 23             int ivex;           // 该边所指向的顶点的位置
 24             ENode *nextEdge;    // 指向下一条弧的指针
 25             friend class ListDG;
 26         };
 27 
 28         // 邻接表中表的顶点
 29         class VNode
 30         {
 31             char data;          // 顶点信息
 32             ENode *firstEdge;   // 指向第一条依附该顶点的弧
 33             friend class ListDG;
 34         };
 35 
 36     private: // 私有成员
 37         int mVexNum;             // 图的顶点的数目
 38         int mEdgNum;             // 图的边的数目
 39         VNode *mVexs;            // 图的顶点数组
 40 
 41     public:
 42         // 创建邻接表对应的图(自己输入)
 43         ListDG();
 44         // 创建邻接表对应的图(用已提供的数据)
 45         ListDG(char vexs[], int vlen, char edges[][2], int elen);
 46         ~ListDG();
 47 
 48         // 深度优先搜索遍历图
 49         void DFS();
 50         // 广度优先搜索（类似于树的层次遍历）
 51         void BFS();
 52         // 打印邻接表图
 53         void print();
 54         // 拓扑排序
 55         int topologicalSort();
 56 
 57     private:
 58         // 读取一个输入字符
 59         char readChar();
 60         // 返回ch的位置
 61         int getPosition(char ch);
 62         // 深度优先搜索遍历图的递归实现
 63         void DFS(int i, int *visited);
 64         // 将node节点链接到list的最后
 65         void linkLast(ENode *list, ENode *node);
 66 };
 67 
 68 /*
 69  * 创建邻接表对应的图(自己输入)
 70  */
 71 ListDG::ListDG()
 72 {
 73     char c1, c2;
 74     int v, e;
 75     int i, p1, p2;
 76     ENode *node1, *node2;
 77 
 78     // 输入"顶点数"和"边数"
 79     cout << "input vertex number: ";
 80     cin >> mVexNum;
 81     cout << "input edge number: ";
 82     cin >> mEdgNum;
 83     if ( mVexNum < 1 || mEdgNum < 1 || (mEdgNum > (mVexNum * (mVexNum-1))))
 84     {
 85         cout << "input error: invalid parameters!" << endl;
 86         return ;
 87     }
 88  
 89     // 初始化"邻接表"的顶点
 90     mVexs = new VNode[mVexNum];
 91     for(i=0; i<mVexNum; i++)
 92     {
 93         cout << "vertex(" << i << "): ";
 94         mVexs[i].data = readChar();
 95         mVexs[i].firstEdge = NULL;
 96     }
 97 
 98     // 初始化"邻接表"的边
 99     for(i=0; i<mEdgNum; i++)
100     {
101         // 读取边的起始顶点和结束顶点
102         cout << "edge(" << i << "): ";
103         c1 = readChar();
104         c2 = readChar();
105 
106         p1 = getPosition(c1);
107         p2 = getPosition(c2);
108         // 初始化node1
109         node1 = new ENode();
110         node1->ivex = p2;
111         // 将node1链接到"p1所在链表的末尾"
112         if(mVexs[p1].firstEdge == NULL)
113           mVexs[p1].firstEdge = node1;
114         else
115             linkLast(mVexs[p1].firstEdge, node1);
116     }
117 }
118 
119 /*
120  * 创建邻接表对应的图(用已提供的数据)
121  */
122 ListDG::ListDG(char vexs[], int vlen, char edges[][2], int elen)
123 {
124     char c1, c2;
125     int i, p1, p2;
126     ENode *node1, *node2;
127 
128     // 初始化"顶点数"和"边数"
129     mVexNum = vlen;
130     mEdgNum = elen;
131     // 初始化"邻接表"的顶点
132     mVexs = new VNode[mVexNum];
133     for(i=0; i<mVexNum; i++)
134     {
135         mVexs[i].data = vexs[i];
136         mVexs[i].firstEdge = NULL;
137     }
138 
139     // 初始化"邻接表"的边
140     for(i=0; i<mEdgNum; i++)
141     {
142         // 读取边的起始顶点和结束顶点
143         c1 = edges[i][0];
144         c2 = edges[i][1];
145 
146         p1 = getPosition(c1);
147         p2 = getPosition(c2);
148         // 初始化node1
149         node1 = new ENode();
150         node1->ivex = p2;
151         // 将node1链接到"p1所在链表的末尾"
152         if(mVexs[p1].firstEdge == NULL)
153           mVexs[p1].firstEdge = node1;
154         else
155             linkLast(mVexs[p1].firstEdge, node1);
156     }
157 }
158 
159 /* 
160  * 析构函数
161  */
162 ListDG::~ListDG() 
163 {
164     ENode *node;
165 
166     for(int i=0; i<mEdgNum; i++)
167     {
168         node = mVexs[i].firstEdge;
169         while (node != NULL)
170         {
171             delete node;
172             node = node->nextEdge;
173         }
174     }
175 
176     delete[] mVexs;
177 }
178 
179 /*
180  * 将node节点链接到list的最后
181  */
182 void ListDG::linkLast(ENode *list, ENode *node)
183 {
184     ENode *p = list;
185 
186     while(p->nextEdge)
187         p = p->nextEdge;
188     p->nextEdge = node;
189 }
190 
191 
192 /*
193  * 返回ch的位置
194  */
195 int ListDG::getPosition(char ch)
196 {
197     int i;
198     for(i=0; i<mVexNum; i++)
199         if(mVexs[i].data==ch)
200             return i;
201     return -1;
202 }
203 
204 /*
205  * 读取一个输入字符
206  */
207 char ListDG::readChar()
208 {
209     char ch;
210 
211     do {
212         cin >> ch;
213     } while(!((ch>='a'&&ch<='z') || (ch>='A'&&ch<='Z')));
214 
215     return ch;
216 }
217 
218 
219 /*
220  * 深度优先搜索遍历图的递归实现
221  */
222 void ListDG::DFS(int i, int *visited)
223 {
224     ENode *node;
225 
226     visited[i] = 1;
227     cout << mVexs[i].data << " ";
228     node = mVexs[i].firstEdge;
229     while (node != NULL)
230     {
231         if (!visited[node->ivex])
232             DFS(node->ivex, visited);
233         node = node->nextEdge;
234     }
235 }
236 
237 /*
238  * 深度优先搜索遍历图
239  */
240 void ListDG::DFS()
241 {
242     int i;
243     int *visited;       // 顶点访问标记
244 
245     visited = new int[mVexNum];
246     // 初始化所有顶点都没有被访问
247     for (i = 0; i < mVexNum; i++)
248         visited[i] = 0;
249 
250     cout << "== DFS: ";
251     for (i = 0; i < mVexNum; i++)
252     {
253         if (!visited[i])
254             DFS(i, visited);
255     }
256     cout << endl;
257 
258     delete[] visited;
259 }
260 
261 /*
262  * 广度优先搜索（类似于树的层次遍历）
263  */
264 void ListDG::BFS()
265 {
266     int head = 0;
267     int rear = 0;
268     int *queue;     // 辅组队列
269     int *visited;   // 顶点访问标记
270     int i, j, k;
271     ENode *node;
272 
273     queue = new int[mVexNum];
274     visited = new int[mVexNum];
275     for (i = 0; i < mVexNum; i++)
276         visited[i] = 0;
277 
278     cout << "== BFS: ";
279     for (i = 0; i < mVexNum; i++)
280     {
281         if (!visited[i])
282         {
283             visited[i] = 1;
284             cout << mVexs[i].data << " ";
285             queue[rear++] = i;  // 入队列
286         }
287         while (head != rear) 
288         {
289             j = queue[head++];  // 出队列
290             node = mVexs[j].firstEdge;
291             while (node != NULL)
292             {
293                 k = node->ivex;
294                 if (!visited[k])
295                 {
296                     visited[k] = 1;
297                     cout << mVexs[k].data << " ";
298                     queue[rear++] = k;
299                 }
300                 node = node->nextEdge;
301             }
302         }
303     }
304     cout << endl;
305 
306     delete[] visited;
307     delete[] queue;
308 }
309 
310 /*
311  * 打印邻接表图
312  */
313 void ListDG::print()
314 {
315     int i,j;
316     ENode *node;
317 
318     cout << "== List Graph:" << endl;
319     for (i = 0; i < mVexNum; i++)
320     {
321         cout << i << "(" << mVexs[i].data << "): ";
322         node = mVexs[i].firstEdge;
323         while (node != NULL)
324         {
325             cout << node->ivex << "(" << mVexs[node->ivex].data << ") ";
326             node = node->nextEdge;
327         }
328         cout << endl;
329     }
330 }
331 
332 /*
333  * 拓扑排序
334  *
335  * 返回值：
336  *     -1 -- 失败(由于内存不足等原因导致)
337  *      0 -- 成功排序，并输入结果
338  *      1 -- 失败(该有向图是有环的)
339  */
340 int ListDG::topologicalSort()
341 {
342     int i,j;
343     int index = 0;
344     int head = 0;           // 辅助队列的头
345     int rear = 0;           // 辅助队列的尾
346     int *queue;             // 辅组队列
347     int *ins;               // 入度数组
348     char *tops;             // 拓扑排序结果数组，记录每个节点的排序后的序号。
349     ENode *node;
350 
351     ins   = new int[mVexNum];
352     queue = new int[mVexNum];
353     tops  = new char[mVexNum];
354     memset(ins, 0, mVexNum*sizeof(int));
355     memset(queue, 0, mVexNum*sizeof(int));
356     memset(tops, 0, mVexNum*sizeof(char));
357 
358     // 统计每个顶点的入度数
359     for(i = 0; i < mVexNum; i++)
360     {
361         node = mVexs[i].firstEdge;
362         while (node != NULL)
363         {
364             ins[node->ivex]++;
365             node = node->nextEdge;
366         }
367     }
368 
369     // 将所有入度为0的顶点入队列
370     for(i = 0; i < mVexNum; i ++)
371         if(ins[i] == 0)
372             queue[rear++] = i;          // 入队列
373 
374     while (head != rear)                // 队列非空
375     {
376         j = queue[head++];              // 出队列。j是顶点的序号
377         tops[index++] = mVexs[j].data;  // 将该顶点添加到tops中，tops是排序结果
378         node = mVexs[j].firstEdge;      // 获取以该顶点为起点的出边队列
379 
380         // 将与"node"关联的节点的入度减1；
381         // 若减1之后，该节点的入度为0；则将该节点添加到队列中。
382         while(node != NULL)
383         {
384             // 将节点(序号为node->ivex)的入度减1。
385             ins[node->ivex]--;
386             // 若节点的入度为0，则将其"入队列"
387             if( ins[node->ivex] == 0)
388                 queue[rear++] = node->ivex;  // 入队列
389 
390             node = node->nextEdge;
391         }
392     }
393 
394     if(index != mVexNum)
395     {
396         cout << "Graph has a cycle" << endl;
397         delete queue;
398         delete ins;
399         delete tops;
400         return 1;
401     }
402 
403     // 打印拓扑排序结果
404     cout << "== TopSort: ";
405     for(i = 0; i < mVexNum; i ++)
406         cout << tops[i] << " ";
407     cout << endl;
408 
409     delete queue;
410     delete ins;
411     delete tops;
412 
413     return 0;
414 }
415 
416 int main()
417 {
418     char vexs[] = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
419     char edges[][2] = {
420         {'A', 'G'}, 
421         {'B', 'A'}, 
422         {'B', 'D'}, 
423         {'C', 'F'}, 
424         {'C', 'G'}, 
425         {'D', 'E'}, 
426         {'D', 'F'}}; 
427     int vlen = sizeof(vexs)/sizeof(vexs[0]);
428     int elen = sizeof(edges)/sizeof(edges[0]);
429     ListDG* pG;
430 
431     // 自定义"图"(输入矩阵队列)
432     //pG = new ListDG();
433     // 采用已有的"图"
434     pG = new ListDG(vexs, vlen, edges, elen);
435 
436     pG->print();   // 打印图
437     //pG->DFS();     // 深度优先遍历
438     //pG->BFS();     // 广度优先遍历
439     pG->topologicalSort();     // 拓扑排序
440 
441     return 0;
442 }