Поиск подключенных компонентов в графе (adjA) с использованием DFS

Question

Я искал в Интернете сегодня, пытаясь выяснить, как запустить DFS в списке смежности vector<list<edge>> adjA, но я просто не могу понять, как это сделать правильно. Лучшим примером, который я мог найти в Интернете, был: 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 
} 

где-то в ИНТ основной:

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 
}