DFS를 사용하여 그래프 (adja)에서 연결된 구성 요소 찾기

Question

최근 인터넷에서 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 

전체 그래프는 단일 성분이므로 CONN는 1이어야한다. 나는 이것이 잘못된 방향으로 가고있는 것처럼 느낍니다. 내가해야 할 변화가 있습니까? DFS 또는 BFS를 사용하여 더 나은 방법이 있습니까?

잘못된 형식에 대해 사과드립니다. 스택 오버플로 오류를 해결하기 위해 거의 한 시간 만 노력했습니다. 귀하의 dfs 방법은 모든 가장자리에보고되지

Answer 1

인접리스트로 표현

그래프. 나는 질문에서 무엇이 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 
}