Я реализую простой обход 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++. Так может ли кто-нибудь пролить свет на эту проблему?
Редактировать
Как вы знаете, он вдруг становится равным 0? Можете ли вы построить минимальный тестовый сценарий? (Потому что это много кода, который вы просите пробраться через ...) –
@Oli: Вы можете просто запустить мой код. В моем конструкторе был граф из 3 вершин. Я использую Visual Studio 2012. Спасибо. – Chan
Вы не можете ожидать, что люди копируют и вставляют весь ваш код в чистый проект, компилируют его, изобретают образец ввода и начинают его отлаживать. Попробуйте уменьшить проблему. –