c++ - 使用 DFS 在图中查找连通分量 (adjA)

Question

我今天一直在网上搜索，试图找出如何在邻接表上运行 DFS vector<list<edge>> adjA ，但我无法弄清楚如何正确执行此操作。我能在网上找到的最好的例子是:Find connected components in a graph但是使用他的第一种方法似乎不起作用，我对 union/集合没有足够的信心来尝试他的另一种方法。这是我到目前为止所拥有的:(忽略 test_vector 和 cc ，我专注于让 cc_count 工作)

edge 是一个包含以下内容的结构:

struct edge{
    int to; //copy of to_original (dont worry about this it's for a different functionality)
    int w; //weight of edge
    int from_original; //from vertex
    int to_original;  //to vertex
}

int main 中的某处:

cout << "conn: " << connected(adjA, test_vector) << endl;

---

int connected(vector<list<edge>> &adjA, vector<short int> &cc){
        int v_size = adjA.size();
        vector<bool> discovered(false,v_size);
        int cc_count = 0;
        for(unsigned int u = 0; u < adjA.size(); u++){
            if(!discovered[u]){
                cout << u << endl;
                discovered[u] = true;
                cc_count+=1;
                dfs(adjA,discovered,cc,cc_count,u);
            }
        }
        return cc_count;
    }

---

    void dfs(vector<list<edge>>&adjA, vector<bool> &discovered, vector<short int> &cc, int &cc_count,int u){
    for(unsigned int v = 0; v < adjA[u].size();v++){
        if(!discovered[v]){
            cout << v << endl;
            discovered[v] = true;
            dfs(adjA, discovered,cc,cc_count,v);
        }
    }

    }

来自 cout << v << endl; 行和 cout << u << endl它将打印显示它能够访问每个节点一次。但是，我正在增加 cc_count我认为不正确。在这个邻接表中:

0->[1]->[3]->[5]
1->[0]->[2]->[3]->[4]
2->[1]->[4]
3->[0]->[1]->[4]->[5]
4->[1]->[2]->[3]->[5]->[6]
5->[0]->[3]->[4]->[6]
6->[4]->[5]

程序会输出:

0
1
2
3
4
5
6
conn: 7

当 conn 应该为 1 时，因为整个图是一个单独的组件。我觉得我可能会以错误的方式解决这个问题。有什么我应该做的改变吗？使用 DFS 或 BFS 有更好的方法吗？

我为糟糕的格式道歉，我花了将近一个小时试图让堆栈溢出错误消失。

邻接表表示的图

Answer 1

您的 dfs 方法根本不查看边缘。我不知道问题中的 edge 是什么，但我们假设它是成对的(两个端点)。

然后

for(unsigned int v = 0; v < adjA[u].size();v++) {
    // do something with v
}

实际上应该是

for (auto const & e: adjA[u]) {
    // do something with the endpoint of e other than u
}