AOV网上的拓扑排序 |
您所在的位置：网站首页 › 拓扑有序 › AOV网上的拓扑排序 |
AOV网上的拓扑排序
|
在本篇博客中，将介绍AOV网上的拓扑排序，以及如何实现输出所有拓扑序列。 目录 前置概念 AOV(Activity on Vertex)网在一个表示工程的有向图中，用顶点表示活动，用有向弧表示活动之间的优先关系，这样的有向图为顶点表示活动的网，简称AOV(Activity on Vertex)网。 弧表示工程活动之间的某种前后制约关系，AOV网中不能存在回路，即不能存在环，否则某个活动的开始要以自己完成作为先决条件，这是不现实的。 如下是一个AOV网的例子。
在一个表示工程的带权有向图中，用顶点表示状态，用有向边表示活动，用边上的权值表示活动的持续时间，这种有向图的边表示活动的网，简称AOE(Activity on Edge)网。 始点/源点：有向图中没有入边的顶点，表示一个工程的开始 终点/汇点：有向图中没有出边的顶点，表示一个工程的结束 某个顶点代表的状态出现后，从该顶点出发的各活动可以立马开始。只有在进入某顶点的各活动都已经结束，该顶点代表的状态才会发生。 如下是一个AOE网的例子。
设G=（V，E）是一个具有n个顶点的有向图， 简单来说，在AOV和AOE网上的拓扑序列就是工程活动进行或状态发生上必须遵循的先后关系，显然，一个工程中，拓扑序列可能是不唯一的。 如下是为上述AOV网中的活动编号后，结点的部分拓扑序列。
............ 求解AOV网上的拓扑序列 基本思想（1）从AOV网中选择一个没有前驱的结点并输出。 （2）从AOV网中删去该结点，并且删去该结点连接的弧。 （3）重复上述操作，直至所有结点全部被输出，或AOV网中不再存在没有前驱的结点。 具体思路数据结构 我们使用邻接表来存储图结构，在存储AOV网时，为了方便地得知每个结点是否存在前驱，在顶点表中添加一个入度域。
同时，准备一个栈S，用于存储所有无前驱的顶点。
上图是一个AOV网和它的邻接表存储的示意图。 过程思路
1.在排序开始前，先将所有入度为0的顶点入栈。
2.反复出栈，即删去入度为0的顶点。出栈时需要将要删除的顶点指向的顶点的入度减1，同时把入度变为0的顶点入栈。如此反复，以模拟删除入度为0的顶点和与其连接的边的操作。 代码实现 void AovNetwork::topSort() { cout adjVex].inDegree --; //同时也需要将入度变为0的顶点入栈。 if(vertexList[tempEdge->adjVex].inDegree == 0) { vexStack.push_back(vertexList + tempEdge -> adjVex); } tempEdge = tempEdge -> next; } } // Restore the network. for(int i = 0 ; i < length ; i ++) { EdgeNode *tempEdge = vertexList[i].firstEdge; while(tempEdge != nullptr) { vertexList[tempEdge -> adjVex].inDegree ++; tempEdge = tempEdge -> next; } } cout adjVex); } tempEdge = tempEdge -> next; } dfs_topSort_ALL(tempStr); //Backtracking. tempEdge = tempVex -> firstEdge; while(tempEdge != nullptr) { if(vertexList[tempEdge->adjVex].inDegree == 0) { vexStack.pop_back(); } vertexList[tempEdge->adjVex].inDegree ++; tempEdge = tempEdge -> next; } tempStr.pop_back(); tempStr.pop_back(); vexStack.insert(vexStack.begin() + i,tempVex); } } } 总结拓扑排序是基础的数据结构算法，需要多加练习。 同时要注意递归的回溯思想，熟练地使用递归+回溯+记忆化这一套模板式的武功。 |
【本文地址】
今日新闻 |
推荐新闻 |