1

我正在为有向图实现一个简单的 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++ 真的很生疏了。那么有人可以就这个问题向我解释一下吗？

编辑 在此处输入图像描述

4

1 回答 1

1

这可能更接近您正在寻找的内容，使用邻居指针。希望这可以帮助。最终的区别在于主顶点容器内的邻居的逐指针寻址，而不是在您的代码中制作的所有副本。

注意：添加构造只是设置一个节点以将顶点集合中的“下一个”节点作为其邻居，最后一个节点获得邻居的第一个节点。这似乎是你的代码试图完成的。

#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
于 2013-04-09T00:56:07.780 回答