如何确定特定节点是否可以找到所有其他节点?
问题描述:
所以我试图确定是否可以找到一个特定的节点,可以用来查找某个图中的所有其他节点。我在C中做了一些伪代码。在使用深度优先搜索时,我无法确定如何检查访问节点。如何确定特定节点是否可以找到所有其他节点?
#include<stdio.h>
int n;
int Graph[n][n];
int visited[n];
int main (int argc, char *argv[]){
int i;
int j;
int x = 1;
for (i=0; i < n; i++){ // run DFS on all variables to determine if any one node implies all others
DFS(i) // starting node/variable
for (j=0; j<n; j++){
if (visited[j]==0){ // has not been visited
x = 0; // boolean int variable set to 0
}
}
if (x!=0){ // if all variables are visited, x will be equal to 1
printf("This variable implies all others");
return i;
}
}
printf("No variables imply all others");
return -1;
}
int DFS(int i)
{
int j;
visited[i]=1;
for(j=0;j<n;j++){
if(!visited[j]&&G[i][j]==1){
DFS(j);
}
}
}
答
一些错误代码:
这里,你确定另一x
内if clause
,这是从你的main
开始定义的一个完全不同的。
if (visited[j]==0){ // has not been visited
int x = 0; // boolean int variable set to 0
}
而且,你也忘了每DFS
之前重置visited
。
答
正如其他答案所说,你的代码是错误的。您不设置visited[]
的值(并且应该在每个循环中重置它们)。您返回main()
中的节点号码,这可能是无用的。如果你设置了x = 0;
应该离开循环(用break
):不需要检查其他值。如果i==j
(取决于您的图形编码),您不应该检查G [i] [j]。
但你为什么要这么复杂的代码?如果我理解得很清楚,你只需要寻找一个连接到其他节点的节点。因此visited[]
不是有用的。节点i
连接到所有其他G[i][j]==0
如果没有j
。它可能是:
// returns true (1) if i connected, false (0) else
int DFS(int i) {
int j;
for(j=0; j<n; j++) {
if ((j != i) && (G[i][j] == 0)) {
return 0; // we know it is not "complete"
}
}
return 1; // not false -> true :)
}
哦哇我刚刚意识到那个错误,我怎么会去重置访问?我是否必须使用for循环并将所有值都设置为0或者有更简单的方法可以做到这一点? – fatalwanderer
@fatalwanderer使用for循环很简单 –