如何用DPS实现拓扑排序

DPS的实现

首先DPS的实现较为容易，这里给出伪代码和思想

借鉴自图——深度优先遍历(DFS)实现有向无环图的逆拓扑排序_dfs实现逆拓扑排序-CSDN博客

//返回有向图G中顶点v的第一个邻接点，如没有返回-1
int FirstNeighbor(Graph G, int v)
{
    //(......具体实现细节)
    return w;
}

//假设图G中w是v的一个邻接点，返回除w外的v的下一个邻接点，若没有，返回-1
int NextNeighbor(Graph G, int v, int w)
{
    //(......具体实现细节)
    return w;
}

//访问v顶点
void visit(int v);

//标记顶点被访问状态的数组，初始时全为false
bool visited[MAX_NUM];

//以上是DPS代码需要的函数
void DFS(Graph G, int v)
{
     visit(v);
     visited[v] = true;   //顶点v已被访问，也就是入度为0的点
//这里开始循环遍历，先从G图的v点的邻接表的第一根弧开始，若该点尚未访问则访问并递归该点，寻找该点的边表，以此寻找到其邻接结点
//在其邻接表的边表后没有边后，递归结束并退回上一个递归，上一个递归便可以继续寻找他的其他邻接节点
     for (w = FirstNeighbor(G, v); w != -1; w = NextNeighbor(G, v, w))
     {
         if (visited[w] == false)
         DFS(G, w);
     }

这就是DPS的内核，找到源点第一个邻接节点，然后通过递归寻找这个节点的邻接节点，当穷尽最深后，便会退回上一个节点，寻找该节点的第二个邻接节点

DPS实现拓扑排序

//为保证所有顶点都被排序，需遍历所有顶点
for (int i = 0; i < MAX_NUM; i++){
    if (!visited[i])
       DFS(G, i);
}

void DFS(Graph G, int v){
    visited[v] = true;
    for (w = FirstNeighbor(G, v); w != -1; w = NextNeighbor(G, v, w)){
        if (!visited[w])
           DFS(G, w);
    }
    print(v);   //输出v信息进行逆拓扑排序
}

这里就是内核所在，在DPS退出之后才输出，因此祖宗结点反而要在最后输出，因为他只有穷尽所有邻接节点的邻接节点后，**DPS(祖宗)**才会在栈中被放出来

以该图为例，a检查到邻接结点b，b未被访问过

于是调用DPS(B)，B也找自己的邻接节点，故只有当调用DPS(d)返回并输出d，才能解放c乃至最下面的a