美文网首页
图的遍历

图的遍历

作者: 1nvad3r | 来源:发表于2020-08-31 20:15 被阅读0次

    1.采用深度优先搜索(DFS)遍历图

    邻接矩阵:
    const int maxn = 1010;
    int n, G[maxn][maxn];
    bool isVisit[maxn];
    
    void dfs(int index) {
        isVisit[index] = true;
        for (int i = 0; i < n; i++) {
            if (isVisit[i] == false && G[index][i] == 1) {
                dfs(i);
            }
        }
    }
    
    void dfsTrave() {
        for (int i = 0; i < n; i++) {
            if (isVisit[i] == false) {
                dfs(i);
            }
        }
    }
    
    邻接表:
    #include <vector>
    
    using namespace std;
    
    const int maxn = 1010;
    vector<int> G[maxn];
    int n;
    bool isVisit[maxn];
    
    void dfs(int index) {
        isVisit[index] = true;
        for (int i = 0; i < G[index].size(); i++) {
            int v = G[index][i];
            if (isVisit[v] == false) {
                dfs(v);
            }
        }
    }
    
    void dfsTrave() {
        for (int i = 0; i < n; i++) {
            if (isVisit[i] == false) {
                dfs(i);
            }
        }
    }
    

    2.采用广度优先搜索(BFS)遍历图

    邻接矩阵:
    #include <queue>
    
    using namespace std;
    const int maxn = 1010;
    
    int n, G[maxn][maxn];
    bool inq[maxn];
    
    void bfs(int index) {
        queue<int> q;
        q.push(index);
        inq[index] = true;
        while (!q.empty()) {
            int now = q.front();
            q.pop();
            for (int i = 0; i < n; i++) {
                if (inq[i] == false && G[now][i] == 1) {
                    q.push(i);
                    inq[i] = true;
                }
            }
        }
    }
    
    void bfsTrave() {
        for (int i = 0; i < n; i++) {
            if (inq[i] == false) {
                bfs(i);
            }
        }
    }
    
    邻接表:
    #include <queue>
    
    using namespace std;
    const int maxn = 1010;
    
    vector<int> G[maxn];
    int n;
    bool inq[maxn];
    
    void bfs(int index) {
        queue<int> q;
        q.push(index);
        inq[index] = true;
        while (!q.empty()) {
            int now = q.front();
            q.pop();
            for (int i = 0; i < G[now].size(); i++) {
                int v = G[now][i];
                if (inq[v] == false) {
                    q.push(v);
                    inq[v] = true;
                }
            }
        }
    }
    
    void bfsTrave() {
        for (int i = 0; i < n; i++) {
            if (inq[i] == false) {
                bfs(i);
            }
        }
    }
    

    1013 Battle Over Cities

    1021 Deepest Root

    1034 Head of a Gang

    1076 Forwards on Weibo

    相关文章

      网友评论

          本文标题:图的遍历

          本文链接:https://www.haomeiwen.com/subject/uzqcsktx.html