C++输出有向无环图的拓扑序列
1，拓扑序列拓扑序列的概念拓扑序列的应用
2，拓扑排序步骤3，举例4，代码实现
1，拓扑序列
拓扑序列的概念
在一个有向无环图中，若有弧 < i , j > 存在，则在拓扑序列中， i 一定排在 j 的前面，具有这种性质的线性序列称为拓扑有序序列。
拓扑序列的应用
（1）可以获得相互关联的若干事件的执行顺序； （2）可以判断一个有向图中是否有回路（环）。
2，拓扑排序步骤
（1）在有向图中选取一个入度为 0 （即没有前驱顶点）的顶点。
（2）保存该顶点至输出结果中，从图中删除该顶点及与该顶点相连的弧。
（3）重复（1）（2）步，直到所有的顶点都已输出或图中没有前驱为 0 的顶点为止。
3，举例
如图， （1）选择入度为 0 的顶点 v0, 将其保存到数组 result 中，删除 v0 及与其相连的弧。
（2）继续选择入度为 0 的顶点，可以选 v3, 也可以选 v1, 这里选 v1, 将其保存到数组 result 中，删除 v1 及与其相连的弧。
（3）继续选择入度为 0 的顶点，可以选 v3, 也可以选 v2, 这里选 v2, 将其保存到数组 result 中，删除 v2 及与其相连的弧。
（4）继续选择入度为 0 的顶点，为 v3, 将其保存到数组 result 中，删除 v3 及与其相连的弧。此时只剩下 v4 ,且其入度为 0 ，继续选择一次将其保存到数组 result 中，排序结束。
result 数组的数据： 0， 1， 2， 3， 4 即为一个拓扑序列。
4，代码实现
#include<iostream>
#include<queue>
#include<vector>
using namespace std
;
#define Max 9999
int n
, m
;
int G
[Max
][Max
];
int inDegree
[Max
];
vector
<int> result
;
void topsort()
{
queue
<int> node
;
for (int i
= 0; i
< n
; ++i
)
{
if (inDegree
[i
] == 0)
{
node
.push(i
);
inDegree
[i
] = -1;
}
}
if (node
.empty())
{
cout
<< "该图无拓扑排序" << endl
;
return;
}
while (!node
.empty())
{
int temp
= node
.front();
node
.pop();
for (int i
= 0; i
< n
; ++i
)
{
if (G
[temp
][i
] != 0)
{
inDegree
[i
]--;
G
[temp
][i
] = 0;
}
if (inDegree
[i
] == 0)
{
node
.push(i
);
inDegree
[i
] = -1;
}
}
result
.push_back(temp
);
}
if (result
.size() < n
)
{
cout
<< "该图无拓扑排序" << endl
;
}
else
{
cout
<< "该图的一个拓扑排序为：" << endl
;
for (int i
= 0; i
< result
.size(); ++i
)
{
cout
<< result
[i
] << " ";
}
}
}
int main()
{
cout
<< "输入顶点数：";
cin
>> n
;
cout
<< "输入边数：";
cin
>> m
;
cout
<< "输入各边的信息：";
fill(G
[0], G
[0] + Max
* Max
, 0);
fill(inDegree
, inDegree
+ Max
, 0);
int u
, v
;
for (int i
= 0; i
< m
; ++i
)
{
cin
>> u
>> v
;
G
[u
][v
]++;
inDegree
[v
]++;
}
topsort();
return 0;
}
输入输出信息：
