根据下面的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) 上面的DFS算法能否遍历图g的所有顶点?如果能给出证明,否则说明理由并给出补救措施。 (2) 如果要对树边、交叉边、后继边和返回边都要做处理,而且还希望给所有顶点建立逆拓扑排序(设全局计数器toponum和顶点拓扑编号数组topo[]都是全局变量,且初值都是0),请在算法中的空白处分别标明。
时间: 2024-02-10 20:08:37 浏览: 27
(1) 上面的DFS算法不能保证遍历图g的所有顶点,因为存在可能会形成环的情况,会导致遍历无法继续进行。补救措施是在每次进入DFS时,增加一个计数器,每访问一个节点就将计数器加1,最终判断计数器是否等于图中顶点个数,如果等于,则遍历完成。
(2) 对树边、交叉边、后继边和返回边都要做处理的代码可以按照下面的方式添加:
```
void DFS(Graph g, int v) {
v.color = GREY; //进入访问
toponum++; //全局计数器加1
v.topo = 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[]用于记录每个顶点的拓扑序号;树边需要记录父节点,可以用一个指针指向父节点。对于四种类型的边,可以根据拓扑序号的大小关系进行分类处理。
相关推荐
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)