【数据结构】图的邻接表存储及BFS&DFS

浅浅的花香味﹌ 2021-10-30 00:48 220阅读 0赞

#include<iostream>
    #include<vector>
    #include<queue>
    using namespace std;
    const int MAX = 1000; // 最大节点数
    vector<int> Adj[MAX]; // 定义邻接表
    queue<int> Q; // BFS辅助队列
    bool visited[MAX]; // 节点访问标志
    int v;
    
    // 初始化图
    void InitGraph() {
        cin>>v;
        for (int i = 0, x; i < v; i ++) {
            cin>>x;
            while (x != -1) {
                Adj[i].push_back(x);
                cin>>x;
            }
        }
    }
    
    // 打印邻接表
    void ShowAdj() {
        cout<<"Graph"<<endl;
        for (int i = 0; i < v; i++) {
            cout<<i<<" -> ";
            for (int j = 0; j < Adj[i].size()-1; j++)
                cout<<Adj[i][j]<<" -> ";
            cout<<Adj[i][Adj[i].size()-1]<<endl;
        }
    }
    // 访问节点
    void Visit(int i) {
        cout<<i<<" ", visited[i] = true;
    }
    
    // 广度优先搜索
    void BFS(int i) {
        Visit(i);
        Q.push(i);
        while (!Q.empty()) {
            int now = Q.front();
            Q.pop();
            for (int j = 0, x; j < Adj[now].size(); j++) {
                x = Adj[now][j];
                if (!visited[x]) {
                    Visit(x);
                    Q.push(x);
                }
            }
        }
    }
    
    void BFSTraverse() {
        for (int i = 0; i < v; i++) {
            visited[i] = false;
        }
        cout<<"BFS: ";
        for (int i = 0; i < v; i++) {
            if (!visited[i])
                BFS(i);
        }
        cout<<endl;
    }
    
    // 深度优先搜索
    void DFS(int i) {
        Visit(i);
        for (int j = 0, x; j < Adj[i].size(); j++) {
            x = Adj[i][j];
            if (!visited[x])
                DFS(x);
        }
    }
    
    void DFSTraverse() {
        for (int i = 0; i < v; i++) {
            visited[i] = false;
        }
        cout<<"DFS: ";
        for (int i = 0; i < v; i++) {
            if (!visited[i])
            DFS(i);
        }
        cout<<endl;
    }
    
    
    int main() {
        InitGraph();
        ShowAdj();
        BFSTraverse();
        DFSTraverse();
        return 0;
    }

// 测试样例
    5
    1 4 -1
    0 4 2 3 -1
    1 3 -1
    1 4 2 -1
    3 0 2 -1
    
    // 测试结果
    Graph
    0 -> 1 -> 4
    1 -> 0 -> 4 -> 2 -> 3
    2 -> 1 -> 3
    3 -> 1 -> 4 -> 2
    4 -> 3 -> 0 -> 2
    BFS: 0 1 4 2 3
    DFS: 0 1 4 3 2