Почему мой код не работает?

Question

Я реализую простой обход DFS для ориентированного графа:

#include <iostream> 
#include <vector> 
#include <climits> 
#include <utility> 
#include <deque> 
#include <queue> 
#include <algorithm> 
#include <iomanip> 
#include <list> 

using namespace std; 

enum class color_type { 
    BLACK, 
    WHITE, 
    GRAY 
}; 

struct vertex { 
    char label; 
    color_type color; 
    int start; 
    int finish; 
    vertex *parent; 
    vector<vertex> adjacents; 

    vertex(char label) 
     :label(label), start(0), finish(0), color(color_type::WHITE) { 
    } 

    void add_neighbor(const vertex &v) { 
     adjacents.push_back(v); 
    } 
}; 

class digraph { 
private: 
    vector<vertex> vertices;  
    int count; 

public: 
    digraph() 
     :count(0) { 
     vertex a('a'); 
     vertex b('b'); 
     vertex c('c'); 
     add_edge(a, b); 
     add_edge(b, c); 
     add_edge(c, a); 
     vertices.push_back(a); 
     vertices.push_back(b); 
     vertices.push_back(c); 
     for (int i = 0; i < vertices.size(); ++i) { 
      vertices[i].color = color_type::WHITE; 
      vertices[i].parent = NULL; 
     } 
    } 

    void add_edge(vertex &u, vertex &v) { 
     u.add_neighbor(v); 
    } 

    void dfs() { 
     dfs_visit(vertices[0]); 
    } 

    void dfs_visit(vertex &u) { 
     count++; 
     u.start = count; 
     u.color = color_type::GRAY; 
     cout << "??? visit = " << u.label << endl; 
     cout << "# neighbors: " << u.adjacents.size() << '\n'; 
     for (int i = 0; i < u.adjacents.size(); ++i) { 
      if (u.adjacents[i].color == color_type::WHITE) { 
       cout << "visit neighbor of [" << u.label << "] is: " << u.adjacents[i].label << endl; 
       u.adjacents[i].parent = &u; 
       dfs_visit(u.adjacents[i]); 
      } 
     } 
     u.color = color_type::BLACK; 
     count++; 
     u.finish = count; 
    } 

public: 
    friend ostream& operator <<(ostream& o, const digraph &dg) { 
     for (int i = 0; i < dg.vertices.size(); ++i) { 
      o << dg.vertices[i].label << ":\n"; 
      o << "\t start = " << dg.vertices[i].start << endl; 
      o << "\t finish = " << dg.vertices[i].finish << endl; 
     } 
     return o; 
    } 
}; 

int main() { 
    digraph dg; 
    dg.dfs(); 
    cout << dg << endl; 
    return 0; 
} 

Проблема заключается вызов dfs_visit() остановки после визита второй вершины. Я передаю вершину u по ссылке в качестве параметра функции dfs_visit(), но почему-то число соседей вершин b внезапно становится 0, что очень странно.
Мне показалось, что вершины, хранящиеся в векторе vertices, не совпадают с теми, которые передаются dfs_visit, но я действительно не вижу, как это может быть. Я использую Java некоторое время, и теперь я действительно ржавый с C++. Так может ли кто-нибудь пролить свет на эту проблему?

Редактировать

Answer 1

Это, вероятно, ближе к тому, что вы ищете, используя указатели для соседей. Надеюсь это поможет. В конечном итоге разница заключается в адресной ссылке соседей внутри основного контейнера вершин, в отличие от всех этих копий, сделанных в вашем коде.

Примечание: add-construction просто устанавливает узел, чтобы узел «next» в коллекции вершин был его соседом, заканчивая последним узлом, получающим первый для соседа. Казалось, это то, чего вы пытаетесь выполнить код.

#include <iostream> 
#include <vector> 
#include <climits> 
#include <utility> 
#include <deque> 
#include <queue> 
#include <algorithm> 
#include <iomanip> 
#include <list> 

using namespace std; 

enum class color_type { 
    BLACK, 
    WHITE, 
    GRAY 
}; 

struct vertex { 
    char label; 
    color_type color; 
    int start; 
    int finish; 
    vertex *parent; 
    vector<vertex*> adjacents; 

    vertex(char label) 
    :label(label), start(0), finish(0), color(color_type::WHITE) { 
    } 

    void add_neighbor(vertex &v) { 
     adjacents.push_back(std::addressof(v)); 
    } 
}; 

class digraph { 
private: 
    vector<vertex> vertices; 
    int count; 

public: 
    digraph() 
    :count(0) { 
     vertices.push_back(vertex('a')); 
     vertices.push_back(vertex('b')); 
     vertices.push_back(vertex('c')); 
     for (size_t i=0; i<vertices.size(); ++i) 
     { 
      vertices[i].color = color_type::WHITE; 
      vertices[i].parent = NULL; 
      vertices[i].add_neighbor(vertices[(i+1)%vertices.size()]); 
     } 
    } 

    void dfs() { 
     dfs_visit(vertices[0]); 
    } 

    void dfs_visit(vertex &u) { 
     count++; 
     u.start = count; 
     u.color = color_type::GRAY; 
     cout << "??? visit = " << u.label << endl; 
     cout << "# neighbors: " << u.adjacents.size() << '\n'; 
     for (int i = 0; i < u.adjacents.size(); ++i) { 
      if (u.adjacents[i]->color == color_type::WHITE) { 
       cout << "visit neighbor of [" << u.label << "] is: " << u.adjacents[i]->label << endl; 
       u.adjacents[i]->parent = &u; 
       dfs_visit(*(u.adjacents[i])); 
      } 
     } 
     u.color = color_type::BLACK; 
     count++; 
     u.finish = count; 
    } 

public: 
    friend ostream& operator <<(ostream& o, const digraph &dg) { 
     for (int i = 0; i < dg.vertices.size(); ++i) { 
      o << dg.vertices[i].label << ":\n"; 
      o << "\t start = " << dg.vertices[i].start << endl; 
      o << "\t finish = " << dg.vertices[i].finish << endl; 
     } 
     return o; 
    } 
}; 

int main() { 
    digraph dg; 
    dg.dfs(); 
    cout << dg << endl; 
    return 0; 
} 

Выход

??? visit = a 
# neighbors: 1 
visit neighbor of [a] is: b 
??? visit = b 
# neighbors: 1 
visit neighbor of [b] is: c 
??? visit = c 
# neighbors: 1 
a: 
    start = 1 
    finish = 6 
b: 
    start = 2 
    finish = 5 
c: 
    start = 3 
    finish = 4