图遍历

深度优先遍历

步骤

• 沿一条路径访问，直到没有出边
• 回溯到上一个节点，沿另一条路径访问。
• 直到所有节点都被访问。

实现

以链式前向星为例

vector<bool> vis(n, false);
void dfs(int u){
    // 标记为已访问
    vis[u] = true;
    // 访问节点u（按具体需求）
    cout << u << ' ';
    // 遍历u的出边
    for(int i = head[u];i;i = G[i].next){
        // 访问出边终点
        int v = G[i].to;
        if(!vis[v]) dfs(v);
    }
}
// 开始遍历
dfs(1);

用途

统计连通块数量

int ans = 0;
// 访问所有节点
for(int i = 1;i <= n;i++){
    // 没访问过，说明是新的连通块
    if(!vis[i]) dfs(i), ans++;
}

广度优先遍历

步骤

• 访问与源距离为1的节点
• 访问与源距离为2的节点
• 依次类推，直到所有节点都被访问。

实现

以链式前向星为例

vector<bool> vis(n, false);
void bfs(int u){
    // 候选队列
    queue<int> q;
    // 先将源点入队
    q.push(u);
    vis[u] = true;
    // 广度优先遍历
    while(!q.empty()){
        // 取出队首节点
        int cur = q.front();
        q.pop();
        // 访问节点cur（按具体需求）
        cout << cur <<'';
        // 遍历cur的出边
        for(int i = head[cur];i;i = G[i].next){
            // 访问出边终点
            int v = G[i].to;
            if(!vis[v]){
                // 入队并标记
                q.push(v);
                vis[v] = true;
            }
        }
    }
}

用途

无权最短路径

// 记录所有点到源点的距离
vector<int> dis(n, -1);
int shortcut(int start, int end, int n){
    // 初始化
    dis.assign(n, -1);
    dis[start] = 0;
    // 广度优先遍历
    queue<int> q;
    q.push(start);
    while(!q.empty()){
        int cur = q.front();
        q.pop();
        if(cur == end) break;
        for(int i = head[cur];i;i = G[i].next){
            int v = G[i].to;
            // 下一距离 = 当前距离 + 1（无权图默认权）
            if(dis[v] == -1){
                dist[v] = dist[cur] + 1;
                q.push(v);
            }
        }
    }
    return dis[end];
}

附：链式前向星

// 每个节点的第一条出边
vector<int> head;
struct Edge{
    // 下一条边的编号
    int next = 0;
    // 边的终点
    int to = 0;
}
// 图的边
vector<Edge> G;
int cnt = 0;