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

Question

我今天一直在 Internet 上搜索，试图找出如何在邻接列表 vector<list<edge>> adjA 上运行 DFS，但我就是不知道如何正确地做到这一点。我能在网上找到的最好的例子是：Find connected components in a graph 但是使用他的第一种方法似乎不起作用，我对联合/集合没有足够的信心来尝试他的另一种方法。这是我目前所拥有的：（忽略 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 是什么，但我们假设它是 pair-like （两个端点）。

然后

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
}

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

Finding connected components in graph (adjA) using DFS

c++

list

vector

adjacency-list

depth-first-search