c - 深度优先搜索代码不打印任何内容

Question

我得到一个任务，要求在 DFS 中打印顶点序列。我没有发现我的代码有任何问题，但它不打印任何内容。

下面是输出应该是怎样的。

Input   Output
6      Vertex 1 is visited
1 4    Vertex 4 is visited
1 6    Vertex 2 is visited
2 4    Vertex 5 is visited
2 5    Vertex 6 is visited
2 6    Vertex 3 is visited
3 4 

这里的前6是顶点数。

这是我的代码片段:

#include <stdio.h>
#include <string.h>
#define MAX 100

int m[MAX][MAX], used[MAX];
int i, n, a, b;

void dfs(int v)
{
  int i;
  // Mark the vertex that is visited
  used[v] = 1;
  printf("Vertex %d is visited\n",v);

  // looking for an edge, through which you can get to the vertex that is not visited 

  for(i = 1; i <= n; i++)
    if (m[v][i] && !used[i]) dfs(i);
}

int main(void)
{


  // read input data
  scanf("%d",&n);
  while(scanf("%d %d",&a,&b) == 2)
    m[a][b] = m[b][a] = 1;

  //run dfs from the top 1
  dfs(1);

  return 0;
}

Answer 1

您的 while 循环没有退出条件。 scanf 只是等待接下来的 2 个数字。您应该修改它，以便在完成输入顶点后继续。像这样:

while(scanf("%d %d", &a, &b)) {

    if(a == -1) break;

    m[a][b] = m[b][a] = 1;
}

当您输入 -1 和其他内容时，您将退出循环。