查找連接圖（ADJA）使用DFS

Question

組件我已經在互聯網搜索今天試圖找出如何鄰接表vector<list<edge>> adjA上運行DFS，但我只是無法弄清楚如何正確地做到這一點。我可以在網上找到的最好的例子是：Find connected components in a graph 但用他的第一種方法似乎沒有工作，我沒有與工會有足夠的信心/臺試試他的另一種方法。這是我到目前爲止有：（無視test_vector和cc，我專注於獲得cc_count工作）

邊緣是一個包含結構：

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主：

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 

當康恩應該爲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 
}