VC++有向无环图所有拓扑序列的生成(6)
时间:2017-06-09 23:08 来源:毕业论文 作者:毕业论文 点击:次
{ public: string data; Edge* adj; Vertex():adj(NULL){} ~Vertex(){} }; 以图1.1所示的AOV网G1为例，其邻接表存储结构如下图2.3。 基于邻接表的图类Graph类的C++代码为： class Graph { Vertex* NodeTable; int NumVertices; //图中节点的数目 int NumEdge; //边数目 public: int* nIndegree; //记录定点的入度 Graph(int size = 0); ~Graph(); int GetVertexPos(const string& vertex); //名字为vertex节点对应于 // NodeTale的位置 void InsertEdge(int v1,int v2); void InsertVertex(const int& index,const string& name); bool ToplogicalOrder(); //如果存在回路，则返回true }; 2.2.2 基于栈得到单拓扑序列的原理 栈在算法中起着存储入度为0顶点的作用，每结束一次循环，栈完成将入度为0的所有顶点压栈和弹出一个栈顶顶点的操作。单一拓扑排序是首先查找邻接表中入度为0的顶点，将其选出，在将其后继顶点的入度减1，再按上一步循环继续查找，直到所有的顶点都被找出。 不难看出, 每次循环将找出一个顶点，那么只要循环N次，就能将N个顶点依次输出。以图1.1为例，第一次循环将找出顶点0和1都入度为0的条件，那我们将按自己的算法取其一，若取0，那么0的后继有2，那么，当选取0以后，就将2的入度减1。第二次循环时，入度为0 的就是1。又按上述方法继续下去。直到循环结束，总共循环了6次，找到了这6个顶点的拓扑排序的结果的一种012345。 找6个顶点的拓扑排序要经过6次循环, 那么找N个顶点的排序结果就要经过N 次循环了。上述算法的运行结果只能找出拓扑排序的所有结果中的一种。 下面仍然以图1.1为例介绍基于栈结构的单拓扑排序算法。图2.4列出了这6个顶点的入度。由图2.4可以看出，刚开始0和1的入度为0，将0和1压入栈，栈中有2个顶点0和1。执行完压栈操作后，弹出栈顶1顶点，作为单拓扑的第一个输出顶点，并将其存在数组a中。同时将1顶点的后继顶点的入度减1，第一次循环就结束了。 接下来做第二次循环，由图2.4看出，此时发现3顶点的入度为0，所以先将3顶点压栈，然后弹出栈顶的3顶点，将3顶点存入数组中，并将3的后继顶点的入度减1，第二次循环结束，见图2.5。 (责任编辑：qin) |