如何在DFS C++中检查u，v边是否连接

Question

输入v=4，e=3
edges(1,2(
edges我想检查u=1，v=3
输出：否
是否有矩阵
0 0 0 0
1 1 0 0
0 0 0

void DFS(int i,int t)
{   
int j;
visited[i] = 1;
cout << i+1 << " ";
if(i == t)
cout << "yes";
for(j=0;j<V;j++)
{   

if(G[i][j]==1 && visited[j] == 0)
DFS(j,t,x);
}
}

Answer 1

通常情况下，像这样的DFS实现可能看起来像(我还没有测试过，所以可能会有一两个问题(：

bool dfs(int this_node, int destination_node) {
// base case where this node is the destination node
if (this_node == destination_node) return true;
// mark this node as visited
visited[this_node] = true;
// go deeper in the search
for (size_t next_node = 0; next_node < V; ++ next_node) {
// skip the search if this node isn't a valid child
if (visited[next_node] || !g[this_node][next_node]) {
continue;
}
// here is the recursive step
if (dfs(next_node, destination_node)) {
return true;
}
}
// if we made it all the way here, then the search failed to reach the destination
return false;
}

然后你就可以从主函数调用这个：

if (dfs(source_node, destination_node)) {
std::cout << "yesn";
} else {
std::cout << "non";
}