C++实现DFS以及BFS

#include 
#include 
#include 
#include 
using namespace std;
// 有向图
class Graph {
public:
    // 初始化
    Graph(int size) 
    :table(vector>(size)), size(size) {
        for(auto &row : table) {
            row = vector();
        }
    }
    // 加边
    void addEdge(int from, int to) {
        table[from].push_back(to);
    }
    // DFS 深度优先搜索
    void dfs(function func) {
        bool visited[size];
        for(int i = 0; i < size; i++) {
            visited[i] = false;
        }
        for(int i = 0; i < size; i++) {
            if(!visited[i]) {
                doDfs(visited, i, func);
            }
        }
    }

    // BFS 广度优先搜索
    void bfs(function func) {
        bool visited[size];
        for(int i = 0; i < size; i++) {
            visited[i] = false;
        }
        for(int i = 0; i < size; i++) {
            if(!visited[i]) {
                doBfs(visited, i, func);
            }
        }
    }

private:
    vector> table;
    int size;

    void doDfs(bool *visited, int node, function func) {
        if(!visited) {
            return;
        }
        visited[node] = true;
        func(node);
        // 找一个相邻的没有被访问的进行递归遍历
        for(auto beg = table[node].begin(); beg != table[node].end(); beg++) {
            if(!visited[*beg]) {
                doDfs(visited, *beg, func);
            }
        }
    }

    void doBfs(bool *visited, int node, function func) {
        auto q = queue();
        visited[node] = true;
        q.push(node);
        while(!q.empty()) {
            int head = q.front();
            q.pop();
            func(head);
            for(auto beg = table[head].begin(); beg != table[head].end(); beg++) {
                if(!visited[*beg]) {
                    q.push(*beg);
                    visited[*beg] = true;
                }
            }
        }
    }
};

// 测试
int main(int argc, char *argv[]) {
    auto g = Graph(4);
    g.addEdge(0, 1);
    g.addEdge(1, 2);
    g.addEdge(2, 3);
    g.addEdge(0, 3);
    g.addEdge(1, 3);
    cout << "进行DFS遍历：" << endl; 
    g.dfs([=](int node) {
        cout << node << " -> ";
    });
    cout << endl << "DFS遍历完毕" << endl;
    cout << "进行BFS遍历：" << endl;
    g.bfs([=](int node) {
        cout << node << " -> ";
    });
    cout << endl << "BFS遍历完毕" << endl;
    return 0;
}

编译运行

$ clang++ -o test dfs&bfs.cxx -std=c++11
$ ./test

输出

进行DFS遍历：
0 -> 1 -> 2 -> 3 -> 
DFS遍历完毕
进行BFS遍历：
0 -> 1 -> 3 -> 2 -> 
BFS遍历完毕