拓扑排序

拓扑排序练习

题目要求：

学习课程计划的辅助编排系统

总结起来基本要求如下：

1. 建立构造课程的有向无环图，求解拓扑子集的划分

2. 对拓扑子集划分的结果可以进行调整，以适度拉长修业的时间，避免学生负担过重

实现提示：

将有向无环图中的顶点集划分成若干互不相交的子集
S1,S2,…,Sm，使得任意两个有弧相连的顶点分属不同的子集，并且，若〈j,k〉是一条从顶
点j 到顶点k 的有向弧，j∈Sp ，k ∈Sq，则子集的序号必有p<q。每个子集Si (i=1,2,…,m)
中的顶点为同一学期中开设的课程。

例如根据一个简单的优先关系模型，所得出的划分实例如下：

提示：

拓扑子集划分的算法是拓扑排序算法的拓展，可以设置两个栈来处理子集的划分。一个
栈用来存放当前入度为零的顶点，另一个栈则用来存放新产生的入度为零的顶点，作备用栈。
交替使用这两个栈，当第一个栈退空时，启用备用栈作为当前栈，而那退空的栈就充当备用
栈，继续存放新产生的入度为零的顶点。事实上，同一个栈里存放的顶点即属于同一个子集，
也就是可在同一个学期开设的课程。

以上，是题目要求。

按步骤解答：

1. 建立图，用邻接表存储图，文件读入图的基本信息。

2. 先不考虑学分限制的问题，按照提示修改拓扑排序算法，求解拓扑子集的划分。

先上代码：

 1 void TopsortbyStack(Graphl& G)
 2 {
 3     using std::stack;
 4     stack <int > S1, S2;    //两个栈，交替使用，当前栈，备用栈
 5     int i;
 6     int flag;    //设置一个标志位，表示当前栈是S1或是S2
 7     //入度为0的顶点入栈
 8     for( i = 0; i < G.VerticesNum() ; i ++)
 9     {
10         if ( G.Indegree[i] == 0 )
11             S1.push( i);
12     }
13     cout<<endl;
14     flag = 1;    // 标志位为1表示当前栈为S1，标志位为2表示当前栈为2
15     while( (flag == 1 && !S1.empty()) || (flag == 2 && !S2.empty()) )
16     {
17         if( flag == 1 )
18         {
19             int v = S1.top();
20             S1.pop();
21             cout<< v<< "   ";
22             G.Mark[v] = VISITED;
23             for ( Edge e = G.FirstEdge(v); G.IsEdge(e); e = G.NextEdge(e) )
24             {
25                 G.Indegree[ G.ToVertex(e) ] --;
26                 if( G.Indegree[ G.ToVertex( e ) ] == 0 )
27                     S2.push(G.ToVertex(e));
28             }
29             //当前栈为空，则交替
30             if ( S1.empty())
31             {
32                 flag = 2;
33                 cout<< endl;
34             }
35         }
36         else
37         {
38             int v = S2.top();
39             S2.pop();
40             cout<< v<< "   ";
41             G.Mark[v] = VISITED;
42             for ( Edge e = G.FirstEdge(v); G.IsEdge(e); e = G.NextEdge(e) )
43             {
44                 G.Indegree[ G.ToVertex(e) ] --;
45                 if( G.Indegree[ G.ToVertex( e ) ] == 0 )
46                     S1.push(G.ToVertex(e));
47             }
48             //当前栈为空，则交替
49             if ( S2.empty())
50             {
51                 flag = 1;
52                 cout<< endl;
53             }
54         }
55     }
56 }

使用一个flag标志表示当前栈和备用栈的选择，感觉代码有点多。

另一个方案是一直使用S1作为当前栈，代码能够简洁一点，但是这样就需要设置一个临时栈，来实现栈的交换，不知道哪种方法更快一点。

运行结果显示（顶点从0开始计数）：

3. 接下来考虑学分限制的问题

为每个顶点添加学时属性，Hours

1 int * Hours;                //存放图中顶点的学时

思路是：从当前栈弹出最上面的那个顶点之前，先计算下本学期已经修的学时，与之相加后与280学时比较，如果比较结果小于280学时，则弹出后继续循环；

如果比较结果大于280学时，则将当前栈中剩下的元素都弹出并送进备用栈中；

 1     if( flag == 1 )
 2         {
 3             int v = S1.top();
 4             tph = tph + G.Hours[v];
 5             if ( tph <= hour)　　//如果比较结果小于280学时，则弹出后继续循环
 6             {
 7                 S1.pop();
 8                 cout<< v<< "   ";
 9                 G.Mark[v] = VISITED;
10                 for ( Edge e = G.FirstEdge(v); G.IsEdge(e); e = G.NextEdge(e) )
11                 {
12                     G.Indegree[ G.ToVertex(e) ] --;
13                     if( G.Indegree[ G.ToVertex( e ) ] == 0 )
14                         S2.push(G.ToVertex(e));
15                 }
16                 //当前栈为空，则交替
17                 if ( S1.empty())
18                 {
19                     flag = 2;
20                     tph = 0;
21                     cout<< endl;
22                 }
23             }
24             else　　　　　　//如果比较结果大于280学时，则将当前栈中剩下的元素都弹出并送进备用栈中
25             {
26                 while(!S1.empty())
27                 {
28                     int temp = S1.top();
29                     S1.pop();
30                     S2.push(temp);
31                 }
32                 flag = 2;
33                 tph = 0;
34                 cout<< endl;
35             }