上海市青浦区建设局网站,网站制作工具有哪些,wordpress 前台用户,网站如何从后台进入拓扑序列
对于任何无回路的AOV网#xff0c;其顶点均可排成拓扑序列#xff0c;并且其拓扑序列未必唯一。步骤如下#xff1a;
1.从网中选择一个入度为0的顶点且输出。
2.从网中删除该顶点及其所有出边。
3.执行1#xff0c;2#xff0c;直至所有顶点已输出#xff0…拓扑序列
对于任何无回路的AOV网其顶点均可排成拓扑序列并且其拓扑序列未必唯一。步骤如下
1.从网中选择一个入度为0的顶点且输出。
2.从网中删除该顶点及其所有出边。
3.执行12直至所有顶点已输出或网中剩余顶点均不为0说明网中存在回路无法继续拓扑排列。因此拓扑排列算法也可用来判断一个有向图中是否存在回路。 准备工作
假定AOV网用邻接表的形式存储为实现拓扑排序算法事先需做好以下两项准备工作
1.建立一个数组count[ ]count[i]的元素值取对应顶点i的入度。
2.建立一个堆栈栈中存放入度为0的顶点每当一个顶点的入度为0就将其压入栈。 优化模拟堆栈
事实上可以不为该顶点栈另外分配存储空间而实直接利用入度为0的顶点的count[ ]数组元素的值来模拟堆栈的压入和弹出。方法如下
1.设置一个”栈顶指针“top以指示当前”栈顶“位置这里的”栈“是模拟的实际并不存在真正的堆栈。
2.初始化“栈”时top值设为-1表示”栈“空。
3.当顶点i的入度为0应该进“栈”时将“栈顶指针”所指的顶点序号放在count[i]中并更新“栈顶指针”top令其指向顶点i
count[I]top;
topi;
4.当应该从“栈”中弹出一个顶点时把原“栈顶”位置记录下来top退到“次栈顶”
jtop;
topcount[top];
入度为0的顶点均要被压入“栈”故每一次“弹出”的顶点top所指向的顶点入度都是0显然顶点的被弹出次序实际是“栈顶”指针top的变化次序也就是拓扑排序时顶点的输出次序。如果“栈顶指针”top值变为-1而顶点却未被全部输出说明网中有回路此时算法强制终止拓扑排序。 实现代码
形式一类封装
//对包含n个顶点的AOV网进行拓扑排序
void Graph_List::TopoOrder() {int n graphsize;int* count new int[n];//计算count数组for (int i 0; i n; i) count[i] 0;for (int i 0; i n; i) {Edge* p Head[i].adjacent;while (p ! NULL) {count[p-VerAdj];p p-link;}}int top -1; //初始化“栈顶指针”for (int i 0; i n; i) {if (count[i] 0) {count[i] top;top i;}}for (int i 0; i n; i) {//若循环体尚未被执行n次栈顶指针已为-1说明有回路终止程序if (top -1) {cout There is a cycle in network! endl;return;}else {int j top; //从栈中弹出一个顶点jtop count[top];cout j endl; //输出该顶点Edge* p Head.adjacent; //令p为j的边链表头指针while (p ! NULL) { //从当前的图中删除与j关联的边int k p-VerAdj; //k为边终点if (--count[k] 0) { //入度-1count[k] top; //若入度为0则k入栈top k;}p p-link;}}}delete[] count;
}
形式二数组模拟队列和邻接表
const int N100010;
int n; //顶点数
//数组模拟队列和邻接表的拓扑排序
void topsort() {int q[N]; //模拟队列的数组qint hh 0, tt -1; //队头hh队尾ttint count[N] { 0 }; //存储图中所有顶点的入度int h[N]{ -1 }, e[N], ne[N], idx 0; //h为顶点结点e存储顶点值ne表示链接关系,-1表示无邻接点//计算所有顶点的入度for (int i 1; i n; i) {for (int j h[i]; j ! -1; j ne[j]) {count[e[j]];}}//将n个顶点中所有入度为0的顶点入队for (int i 1; i n; i) {if (count[i] 0) q[tt] i;}//while (hh tt) {int t q[hh]; //队头取出顶点//遍历所有与t邻接的顶点for (int i h[t]; i ! -1; i ne[i]) {int j e[i]; //与t邻接的顶点j的入度都-1count[j]--; if (count[j] 0) q[tt] j; //若入度为0则入队}}//若队尾ttn-1则证明n个顶点全部遍历if (tt n - 1) {//此时队列内存储的便是拓扑序列for (int i 0; i n; i) cout q[i] ;}//否则未全部遍历存在回路else cout There is a cycle in network! endl;
} 《数据结构》刘大友||第6章 图||6.4拓扑排序
