VC++有向无环图所有拓扑序列的生成(6)
{
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。