广度优先搜索 - 错误结果
问题描述:
此代码实现广度优先搜索。广度优先搜索 - 错误结果
#define N 9 //nodes
#define MAXNUM 65555
#define FALSE 0
#define TRUE 1
int main() {
int i, j;
int network[N][N]; //Adjacency matrix
int dist[N]; //distances from node u
int u = 0; //choose first node
void bfs(int, int [N][N], int [N]);
for (i = 0; i < N; i++) {
dist[i] = MAXNUM;
for (j = 0; j < N; j++) {
if (i == j) {
network[i][j] = 0;
} else {
network[i][j] = MAXNUM;
network[j][i] = MAXNUM;
}
}
}
network[0][1]=1; network[0][3]=1; network[0][5]=1;
network[1][0]=1; network[1][2]=1; network[1][6]=1;
network[2][1]=1; network[2][3]=1; network[2][7]=1;
network[3][0]=1; network[3][2]=1; network[3][4]=1;
network[4][3]=1; network[4][5]=1; network[4][7]=1;
network[5][0]=1; network[5][4]=1; network[5][6]=1;
network[6][1]=1; network[6][5]=1; network[6][7]=1;
network[7][2]=1; network[7][4]=1; network[7][6]=1;
bfs(u, network, dist);
return 0;
}
void bfs(int u, int network[N][N], int dist[N]) {
int w, v, onScanQ[N], ScanQ[N], Qsize = 0;
int k;
for (v = 0; v < N; v++) {
dist[v] = MAXNUM;
onScanQ[v] = FALSE;
}
dist[u] = 0;
ScanQ[1] = u;
onScanQ[u] = TRUE;
Qsize = 1;
k = 1;
printf("\nBFS has started examining:\n");
do {
v = ScanQ[k];
printf("%d ", v);
for (w = 0; w < N; w++) {
if ((network[v][w] < MAXNUM) && (!onScanQ[w])) {
Qsize++;
ScanQ[Qsize] = w;
onScanQ[w] = TRUE;
dist[w] = dist[v] + 1;
printf("(%d) ", w);
}
k++;
}
} while (k <= Qsize);
printf("\n");}
但是,而不是这些结果:
BFS已经开始研究: 0(1)(3)(5)1(2)(6)3(4)5 2(7 )6 4 7
我从输出,仅此:
BFS已经开始研究: 0(1)(3)(5)
什么是缺失?
答
在while循环内部快速显示while
中的条件不等于true
,因此仅打印一组输出!
printf("Qsize=%d k=%d\n", Qsize, k);
} while (k <= Qsize);
输出:
Qsize=4 k=10
+0
谢谢!计数器k的位置是错误的。正确的位置在for循环之后。 – John 2011-12-24 14:04:09
+0
如果您使用了for(k = 0; k
你是怎么发现,当你通过代码在调试器阶梯? – 2011-12-24 13:36:29
您能否介绍一下您的内部数据结构,如ScanQ,onScanQ;计数器/索引像v,w;你的输出格式 - 这是什么意思“0(1)(3)(5)”? - 主要是你的算法! .. OTOH你有没有尝试去调试呢?请分享您的经验! – 2011-12-24 13:44:30
我是C新手,并未尝试调试它。我会尝试。该网络是[立方体](http://img861.imageshack.us/img861/2667/networkcube.jpg)。我尝试检查此网络是否与此代码连接。该算法检查第一个节点(u = 0)。 ScanQ是扫描的节点,onScanQ是下一个扫描节点。输出给出第一个节点u = 0,句子中没有句子及其邻居节点! – John 2011-12-24 13:58:25