《数据结构与算法》——拓扑排序

luciferzf

拓扑排序：
建立一个有向图，我们称之为AOV图。我们需要将AOV图中每个点进行排序，按照入度的多少的顺序。我们用栈结构来储存点，首先我们先将入度为0的点压入栈中，然后把压入栈中的点从AOV图中删除，与其相邻的点的度减一。
在代码实现的过程中，我们使用数组来储存每个点，用链表的方式来储存每个点的出度。当进行遍历的时候，我们将所有入度为0的点压入栈中，然后把改点的出度的点的入度减一。循环至所有点都被压入栈中。

1. #include<cstdio>
   
2. #include<cstdlib>
   
3. #include<iostream>
   
4. using namespace std;
   
5. 
   
6. int stack[1000];
   
7. int N;
   
8. 
   
9. class graph
   
10. {
    
11. public:
    
12.         int low;
    
13.         graph *np=NULL;
    
14. };
    
15. 
    
16. class VERTEX
    
17. {
    
18. public:
    
19.         int power=0;
    
20.         graph *np = NULL;
    
21. };
    
22. 
    
23. void Input(VERTEX vertex[])
    
24. {
    
25.         int a, b;
    
26.         printf("input the edge of graph and end with double -1:\n");
    
27.         cin >> a >> b;
    
28.         graph *cp=NULL;
    
29.         while (a != -1)
    
30.         {
    
31.                 if (vertex[a].np == NULL)
    
32.                 {
    
33.                         vertex[a].np = new graph;
    
34.                         cp = vertex[a].np;
    
35.                 }
    
36.                 else
    
37.                 {
    
38.                         cp->np = new graph;
    
39.                         cp = cp->np;
    
40.                 }
    
41.                 cp->low = b;
    
42.                 vertex[b].power++;
    
43.                 cin >> a >> b;
    
44.         }
    
45. }
    
46. 
    
47. void print(VERTEX vertex[])
    
48. {
    
49.         for (int i = 0; i < N; i++)
    
50.         {
    
51.                 printf("%d",stack[i]);
    
52.                 if (i != N-1)
    
53.                 {
    
54.                         printf("——>");
    
55.                 }
    
56.                 else
    
57.                 {
    
58.                         cout << endl;
    
59.                 }
    
60.         }
    
61. }
    
62. 
    
63. int main()
    
64. {
    
65.         int count=0;
    
66.         cout << "input the numbers of the vertexes:";
    
67.         cin >> N;
    
68.         int edge=0;
    
69.         cout<<"input the numbers of the edge:";
    
70.         cin>>edge;
    
71.         VERTEX vertex[edge];
    
72.         Input(vertex);
    
73.         graph *cp;
    
74.         while (count < N)
    
75.         {
    
76.                 int precount = count;
    
77.                 for (int i = 1; i <= N; i++)
    
78.                 {
    
79.                         if (vertex[i].power == 0)
    
80.                         {
    
81.                                 stack[count++] = i;
    
82.                                 vertex[i].power = -1;
    
83.                         }
    
84.                 }
    
85.                 while (precount != count)
    
86.                 {
    
87.                         cp = vertex[stack[precount]].np;
    
88.                         while (cp != NULL)
    
89.                         {
    
90.                                 vertex[cp->low].power--;
    
91.                                 cp = cp->np;
    
92.                         }
    
93.                         precount++;
    
94.                 }
    
95.         }
    
96.         print(vertex);
    
97.         system("PAUSE");
    
98. }

复制代码