图的遍历

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