根据下面的DFS程序框架回答问题: void DFS(Graph g, int v) //g是图的邻接矩阵或邻接表,v是g的一个顶点。 { v.color = GREY; //进入访问 ; for each w in g.neighbor(v) //找顶点v的所有相邻点 if (w.color == WHITE) ; DFS(g,w); //找顶点v的未访问过的相邻点w ; elseif (w.color == GREY) ; else ; ; v.color = BLACK; } (1) 上面的如果要对树边、交叉边、后继边和返回边都要做处理,而且还希望给所有顶点建立逆拓扑排序(设全局计数器toponum和顶点拓扑编号数组topo[]都是全局变量,且初值都是0),将算法中的空白处分补全
时间: 2024-03-03 14:53:47 浏览: 60
对树边、交叉边、后继边和返回边都要做处理,并建立逆拓扑排序的DFS算法如下:
```
void DFS(Graph g, int v) {
v.color = GREY; //进入访问
toponum++;
for each w in g.neighbor(v) { //找顶点v的所有相邻点
if (w.color == WHITE) { //树边
w.father = v; //记录父节点
DFS(g, w);
} else if (w.color == GREY) { //返回边
//do something
} else { //后继边或交叉边
if (v.topo > w.topo) { //后继边
//do something
} else { //交叉边
//do something
}
}
}
v.color = BLACK;
toponum++;
topo[toponum] = v; //记录拓扑序号
}
```
其中,全局计数器toponum和顶点拓扑编号数组topo[]用于记录每个顶点的拓扑序号;树边需要记录父节点,可以用一个指针指向父节点。对于四种类型的边,可以根据拓扑序号的大小关系进行分类处理。在DFS结束时,将当前顶点的拓扑序号记录到topo数组中。最终,topo数组中的顶点编号就是逆拓扑排序的结果。
阅读全文