我正在为有向图实现一个简单的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
,这很奇怪。在我看来,存储在 vector
vertices
中的顶点与传递给dfs_visit
的顶点不同,但是我真的不知道这种情况如何。我使用Java已有一段时间了,现在我对C++感到很生疏。那么,有人可以给我一些有关此问题的信息吗?编辑
最佳答案
使用邻居的指针,这可能更接近您要查找的内容。希望这可以帮助。最终,区别在于主顶点容器中邻居的按指针寻址,而不是在代码中创建的所有副本。
注意:add-construction只是将一个节点设置为在顶点集合中将“下一个”节点作为其邻居,最后一个节点成为第一个邻居。这似乎是您的代码试图实现的目标。
#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
关于c++ - 为什么我的代码不起作用?,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/15891231/