图论基础

#include <bits/stdc++.h>
using namespace std;

const int N = 100010;
const int M = 500010;

// ========== 1. 邻接矩阵存储 ==========
int g_mat[510][510];  // 适合稠密图，节点数 ≤ 500

// ========== 2. 邻接表存储 ==========
vector<int> adj[N];         // 无权图
vector<pair<int,int>> adjw[N]; // 带权图：{邻居, 权重}

void add_edge(int u, int v) {
    adj[u].push_back(v);
    adj[v].push_back(u);  // 无向图加这行
}

// ========== 3. 图的 DFS 遍历 ==========
bool vis[N];

void graph_dfs(int u) {
    vis[u] = true;
    cout << u << " ";
    for (int v : adj[u]) {
        if (!vis[v]) graph_dfs(v);
    }
}

// ========== 4. 图的 BFS 遍历 ==========
void graph_bfs(int start, int n) {
    memset(vis, false, sizeof(vis));
    queue<int> q;
    q.push(start);
    vis[start] = true;

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        cout << u << " ";

        for (int v : adj[u]) {
            if (!vis[v]) {
                vis[v] = true;
                q.push(v);
            }
        }
    }
}

// ========== 5. 连通性判断 ==========
int count_components(int n) {
    memset(vis, false, sizeof(vis));
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        if (!vis[i]) {
            graph_dfs(i);
            cnt++;
        }
    }
    return cnt;
}

// ========== 6. 环检测（无向图）==========
bool has_cycle_dfs(int u, int parent) {
    vis[u] = true;
    for (int v : adj[u]) {
        if (!vis[v]) {
            if (has_cycle_dfs(v, u)) return true;
        } else if (v != parent) {
            return true;  // 访问过且不是父节点 → 有环
        }
    }
    return false;
}

bool has_cycle(int n) {
    memset(vis, false, sizeof(vis));
    for (int i = 1; i <= n; i++) {
        if (!vis[i]) {
            if (has_cycle_dfs(i, -1)) return true;
        }
    }
    return false;
}

// ========== 7. Flood Fill（泛洪算法）==========
// 网格版：从种子点扩散，标记连通区域
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};

void flood_fill(vector<vector<int>> &grid, int x, int y, int newColor) {
    int oldColor = grid[x][y];
    if (oldColor == newColor) return;

    int n = grid.size(), m = grid[0].size();
    queue<pair<int,int>> q;
    q.push({x, y});
    grid[x][y] = newColor;

    while (!q.empty()) {
        auto [cx, cy] = q.front();
        q.pop();

        for (int d = 0; d < 4; d++) {
            int nx = cx + dx[d], ny = cy + dy[d];
            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            if (grid[nx][ny] != oldColor) continue;
            grid[nx][ny] = newColor;
            q.push({nx, ny});
        }
    }
}

// Flood Fill 计算连通块数量
int count_regions(vector<string> &grid) {
    int n = grid.size(), m = grid[0].size();
    vector<vector<bool>> visited(n, vector<bool>(m, false));
    int cnt = 0;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (grid[i][j] == '#' && !visited[i][j]) {
                cnt++;
                queue<pair<int,int>> q;
                q.push({i, j});
                visited[i][j] = true;
                while (!q.empty()) {
                    auto [x, y] = q.front();
                    q.pop();
                    for (int d = 0; d < 4; d++) {
                        int nx = x + dx[d], ny = y + dy[d];
                        if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
                        if (visited[nx][ny] || grid[nx][ny] != '#') continue;
                        visited[nx][ny] = true;
                        q.push({nx, ny});
                    }
                }
            }
        }
    }
    return cnt;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;  // n个节点，m条边
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        add_edge(u, v);
    }

    cout << "DFS: ";
    memset(vis, false, sizeof(vis));
    graph_dfs(1);
    cout << endl;

    cout << "BFS: ";
    graph_bfs(1, n);
    cout << endl;

    cout << "连通分量数: " << count_components(n) << endl;

    return 0;
}

📖 要点说明

图的两种存储方式

DFS vs BFS 遍历图

Flood Fill

• 本质是 BFS，从一个点开始扩散
• 用途：连通块计数、区域填充、岛屿数量

⚠️ 常见错误

• 无向图每条边存两次，DFS 环检测要排除父节点
• 节点编号从 1 还是 0 开始要统一
• BFS 入队时就标记，不要出队再标记

🎮 动手试试

理解判断逻辑，图遍历中大量使用条件判断：