没有两次搜索的无向图的 DFS

Question

早上好，

我是图形界的新手，有一些关于DFS的问题，在其他题目中没有找到。

我拿了站点的DFS代码：

（我采用了 Java 实现）

该图是在主函数中构建的：

    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 2);
    g.addEdge(2, 0);
    g.addEdge(2, 3);
    g.addEdge(3, 1);
    g.addEdge(2, 4);

但是如果我像这样更改第一行：

    g.addEdge(1, 0);

DFS结果不同，因为是有向图。那么将 DFS 实现为无向图的最佳方法是什么，而不需要在列表上做两个 "searches"？（我认为这是最简单的方法）。我找到了几种方法来实现 DFS 到有向图，但 none 到无向图。 DFS 会不会只用于有向图？

关于图表最好的书是什么？

此致

安东尼奥

Answer 1

您使用的代码实际上非常好。处理这个问题的最简单方法是更改图形而不是 DFS 的实现。因此，您按如下方式更改函数 addEdge 以在两个方向上添加边：

void Graph::addEdge(int v, int w)
{
    adj[v].push_back(w); // Add w to v’s list.
    adj[w].push_back(v);
}

DFS for undirected Graphs whithout two searches