拓扑排序(二)之 C++详解(二)
vex]++;
node = node->nextEdge;
}
}
// 将所有入度为0的顶点入队列
for(i = 0; i < mVexNum; i ++)
if(ins[i] == 0)
queue[rear++] = i; // 入队列
while (head != rear) // 队列非空
{
j = queue[head++]; // 出队列。j是顶点的序号
tops[index++] = mVexs[j].data; // 将该顶点添加到tops中，tops是排序结果
node = mVexs[j].firstEdge; // 获取以该顶点为起点的出边队列
// 将与"node"关联的节点的入度减1；
// 若减1之后，该节点的入度为0；则将该节点添加到队列中。
while(node != NULL)
{
// 将节点(序号为node->ivex)的入度减1。
ins[node->ivex]--;
// 若节点的入度为0，则将其"入队列"
if( ins[node->ivex] == 0)
queue[rear++] = node->ivex; // 入队列
node = node->nextEdge;
}
}
if(index != mVexNum)
{
cout << "Graph has a cycle" << endl;
delete queue;
delete ins;
delete tops;
return 1;
}
// 打印拓扑排序结果
cout << "== TopSort: ";
for(i = 0; i < mVexNum; i ++)
cout << tops[i] << " ";
cout << endl;
delete queue;
delete ins;
delete tops;
return 0;
}
复制代码
说明：
(01) queue的作用就是用来存储没有依赖顶点的顶点。它与前面所说的Q相对应。
(02) tops的作用就是用来存储排序结果。它与前面所说的T相对应。