C++深度优先搜索（DFS）实施

我想实现有竞争力的编程一书描述的以下DFS代码：C++深度优先搜索（DFS）实施

#include <cstdio> 
#include <vector> 
using namespace std; 

#define MAX 10 
#define DFS_BLACK 1 
#define DFS_WHITE -1 
typedef pair<int, int> ii; 
typedef vector<ii> vii; 
typedef vector<int> vi; 

vi dfs_num; 
vector<vii> adj(MAX); 

void dfs(int u) { 
    dfs_num[u] = DFS_BLACK; 
    for (int i = 0; i < (int)adj[i].size(); i++) { 
     ii v = adj[u][i]; 
     if (dfs_num[v.first] == DFS_WHITE) 
      dfs(v.first); 
    } 
    printf(" %d", u); 
} 

int main() { 
    int v, e, x, y; 

    scanf("%d %d", &v, &e); 
    for (int i = 0; i < e; i++) { 
     scanf("%d %d", &x, &y); 
     adj[x].push_back(ii(y, 1)); 
     adj[y].push_back(ii(x, 1)); 
    } 

    int numCC = 0; 
    dfs_num.assign(v, DFS_WHITE); 
    for (int i = 0; i < v; i++) 
     if (dfs_num[i] == DFS_WHITE) 
      printf("Component %d:", ++numCC), dfs(i), printf("\n"); 
    printf("There are %d connected components\n", numCC); 
}

我想获得的是：

Input:  Output: 
9 7   Component 1: 0 1 2 3 4 
0 1   Component 2: 5 
1 2   Component 3: 6 7 8 
1 3   There are 3 connected components 
2 3 
3 4 
6 7 
6 8

对于以下图表：

graph1

但我正在逐渐“分量1：3 2 1“，那么它崩溃。我究竟做错了什么？

任何帮助表示赞赏。

来源

2014-09-04 ceferrari

for (int i = 0; i < (int)adj[i].size(); i++) {

到：

for (int i = 0; i < (int)adj[u].size(); i++) { 
//       ^u, not i

Live demo link

来源

2014-09-04 17:57:02

就是这样。谢谢！！ – ceferrari 2014-09-04 18:03:38

整体逻辑似乎确定，但我看到在一些细节奇怪的事情：在第17行

，该换循环，应该是adj [u]，而不是adj [i]？

其他的事情，我注意到：

不使用单字母的变量名，将大大有助于我们理解你的代码......意味着你会得到更多的答复。
您的连接组件将以相反的顺序打印（3 2 1，而不是1 2 3），因为在dfs（）中您递归调用后打印
我问你为什么在第31行中使用一对当第二个int为1时为32，并且你从不使用它。

来源

2014-09-04 18:01:09

1.这是主要问题。按照Piotr S.的建议解决。1.对不起。 2.修正了这一点，谢谢。 3.数字1应该是重量，但我还没有使用它们 – ceferrari 2014-09-04 18:07:42

C++深度优先搜索（DFS）实施

回答

相关问题