AOV网特点:
AOV网中的弧表示活动之间存在的某种制约关系
AOV网中不能出现回路
为避免每次都要搜索入度为零的顶点,在算法中设置一个“栈”,以保存“入度为零”的顶点。
void FindInDegree(ALGraph G, int indegree[]){
// 求各顶点的入度
for(i = 0; i < G.vexnum; i++)
indegree[i] = 0;
for(i = 0; i <G.vexnum; ++i){
p = G.vertices[i].firstarc;
while(p != NULL){
indegree[p->adjvex]++;
p = p->nextarc;
}
}
}
void TopologicalSort(ALGraph G){
// 拓扑排序
FindInDegree(G, indegree); // 对各顶点求入度
InitStack(S);
for(i = 0; i < G.vexnum; i++)
if(!indegree[i]) Push(S, i); // 入度为零的顶点入栈
count = 0; // 对输出顶点计数
while(!EmptyStack(S)){
Pop(S, i);
++count;
cout << G.vertices[i].data;
for(p = G.vertices[i].firstarc; p; p = p->nextarc){
k = p->adjvex;
--indegree(k); // 弧头顶点的入度减一
if(!indegree[k]) Push(S, k); // 新产生的入度为零的顶点入栈
}
}
if(count < G.vexnum)
cout << "图中有回路";
}
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。