为什么深度优先搜索以这种方式检查顶点？
Why Depth First Search checks vertices this way?
我正在学习图形并且遇到过这样的深度优先搜索算法的实现，该算法在图形中找到循环
我们为什么要检查 w !== u。在什么情况下可以 w === u ?
dfs(v, u) {
this._marked[v] = true;
const adj = this._graph.adj(v);
for (const w of adj) {
if (!this._marked[w]) {
this.dfs(w, v);
} else if (w !== u) {
this.hasCycle = true;
}
}
}
您的算法似乎是针对无向图的，u 是 v 的父级。当你调用 this._graph.adj(v) 时，它 returns 所有相邻的包括父 u。条件 w !== u 检查你是否访问过一个节点两次，这意味着你有两条不同的路径从你的根节点到该节点。这意味着一个循环。但是在 u 是父节点的情况下，您计算边缘 E(u,v) 两次，这不是循环的定义。
我正在学习图形并且遇到过这样的深度优先搜索算法的实现，该算法在图形中找到循环
我们为什么要检查 w !== u。在什么情况下可以 w === u ?
dfs(v, u) {
this._marked[v] = true;
const adj = this._graph.adj(v);
for (const w of adj) {
if (!this._marked[w]) {
this.dfs(w, v);
} else if (w !== u) {
this.hasCycle = true;
}
}
}
您的算法似乎是针对无向图的，u 是 v 的父级。当你调用 this._graph.adj(v) 时，它 returns 所有相邻的包括父 u。条件 w !== u 检查你是否访问过一个节点两次，这意味着你有两条不同的路径从你的根节点到该节点。这意味着一个循环。但是在 u 是父节点的情况下，您计算边缘 E(u,v) 两次，这不是循环的定义。