百练百会 bestWit

Appearance

L7_04 图论算法 ​

一、图的泛洪算法(Flood Fill) ​

1.1 泛洪算法概述 ​

泛洪算法（Flood Fill）是一种从起始点开始，向四周扩散遍历所有连通节点的算法。

1.2 四方向泛洪填充 ​

cpp
void floodFill(vector<vector<int>>& grid, int i, int j, int oldColor, int newColor) {
    if (i < 0 || i >= grid.size() || j < 0 || j >= grid[0].size()) {
        return;
    }
    if (grid[i][j] != oldColor) {
        return;
    }
    
    grid[i][j] = newColor;
    
    floodFill(grid, i + 1, j, oldColor, newColor);
    floodFill(grid, i - 1, j, oldColor, newColor);
    floodFill(grid, i, j + 1, oldColor, newColor);
    floodFill(grid, i, j - 1, oldColor, newColor);
}

1.3 八方向泛洪填充 ​

cpp
void floodFill8(vector<vector<int>>& grid, int i, int j, int oldColor, int newColor) {
    if (i < 0 || i >= grid.size() || j < 0 || j >= grid[0].size()) {
        return;
    }
    if (grid[i][j] != oldColor) {
        return;
    }
    
    grid[i][j] = newColor;
    
    // 八个方向
    for (int dx = -1; dx <= 1; dx++) {
        for (int dy = -1; dy <= 1; dy++) {
            if (dx != 0 || dy != 0) {
                floodFill8(grid, i + dx, j + dy, oldColor, newColor);
            }
        }
    }
}

1.4 BFS 实现泛洪填充 ​

cpp
void floodFillBFS(vector<vector<int>>& grid, int startI, int startJ, int newColor) {
    int oldColor = grid[startI][startJ];
    if (oldColor == newColor) return;
    
    int rows = grid.size();
    int cols = grid[0].size();
    queue<pair<int, int>> q;
    
    q.push({startI, startJ});
    grid[startI][startJ] = newColor;
    
    int dx[] = {-1, 1, 0, 0};
    int dy[] = {0, 0, -1, 1};
    
    while (!q.empty()) {
        auto [i, j] = q.front();
        q.pop();
        
        for (int k = 0; k < 4; k++) {
            int ni = i + dx[k];
            int nj = j + dy[k];
            if (ni >= 0 && ni < rows && nj >= 0 && nj < cols && grid[ni][nj] == oldColor) {
                grid[ni][nj] = newColor;
                q.push({ni, nj});
            }
        }
    }
}

二、连通分量 ​

2.1 无向图的连通分量 ​

cpp
void dfsCC(int node, vector<bool>& visited, const vector<vector<int>>& graph) {
    visited[node] = true;
    for (int neighbor : graph[node]) {
        if (!visited[neighbor]) {
            dfsCC(neighbor, visited, graph);
        }
    }
}

int countConnectedComponents(const vector<vector<int>>& graph) {
    int n = graph.size();
    vector<bool> visited(n, false);
    int count = 0;
    
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            count++;
            dfsCC(i, visited, graph);
        }
    }
    return count;
}

2.2 强连通分量(Kosaraju算法) ​

cpp
void dfs1(int node, vector<bool>& visited, const vector<vector<int>>& graph, vector<int>& order) {
    visited[node] = true;
    for (int neighbor : graph[node]) {
        if (!visited[neighbor]) {
            dfs1(neighbor, visited, graph, order);
        }
    }
    order.push_back(node);
}

void dfs2(int node, vector<bool>& visited, const vector<vector<int>>& reversedGraph, vector<int>& component) {
    visited[node] = true;
    component.push_back(node);
    for (int neighbor : reversedGraph[node]) {
        if (!visited[neighbor]) {
            dfs2(neighbor, visited, reversedGraph, component);
        }
    }
}

vector<vector<int>> kosaraju(const vector<vector<int>>& graph) {
    int n = graph.size();
    vector<bool> visited(n, false);
    vector<int> order;
    
    // 第一次DFS
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            dfs1(i, visited, graph, order);
        }
    }
    
    // 构建反向图
    vector<vector<int>> reversedGraph(n);
    for (int i = 0; i < n; i++) {
        for (int j : graph[i]) {
            reversedGraph[j].push_back(i);
        }
    }
    
    // 第二次DFS
    fill(visited.begin(), visited.end(), false);
    reverse(order.begin(), order.end());
    vector<vector<int>> components;
    
    for (int node : order) {
        if (!visited[node]) {
            vector<int> component;
            dfs2(node, visited, reversedGraph, component);
            components.push_back(component);
        }
    }
    return components;
}

三、最小生成树 ​

3.1 Kruskal算法 ​

cpp
struct Edge {
    int u, v, weight;
    bool operator<(const Edge& other) const {
        return weight < other.weight;
    }
};

vector<int> parent;
vector<int> rank_;

int find(int x) {
    if (parent[x] != x) {
        parent[x] = find(parent[x]);
    }
    return parent[x];
}

void unite(int x, int y) {
    x = find(x);
    y = find(y);
    if (x == y) return;
    if (rank_[x] < rank_[y]) {
        parent[x] = y;
    } else {
        parent[y] = x;
        if (rank_[x] == rank_[y]) {
            rank_[x]++;
        }
    }
}

int kruskal(int n, vector<Edge>& edges) {
    sort(edges.begin(), edges.end());
    parent.resize(n);
    rank_.resize(n, 0);
    for (int i = 0; i < n; i++) {
        parent[i] = i;
    }
    
    int totalWeight = 0;
    int edgesUsed = 0;
    
    for (const Edge& e : edges) {
        if (find(e.u) != find(e.v)) {
            unite(e.u, e.v);
            totalWeight += e.weight;
            edgesUsed++;
            if (edgesUsed == n - 1) break;
        }
    }
    return totalWeight;
}

3.2 Prim算法 ​

cpp
int prim(int n, const vector<vector<pair<int, int>>>& graph) {
    vector<bool> inMST(n, false);
    vector<int> key(n, INT_MAX);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    
    key[0] = 0;
    pq.push({0, 0});
    
    int totalWeight = 0;
    
    while (!pq.empty()) {
        auto [weight, u] = pq.top();
        pq.pop();
        
        if (inMST[u]) continue;
        inMST[u] = true;
        totalWeight += weight;
        
        for (auto [v, w] : graph[u]) {
            if (!inMST[v] && w < key[v]) {
                key[v] = w;
                pq.push({w, v});
            }
        }
    }
    return totalWeight;
}

四、最短路径 ​

4.1 Dijkstra算法 ​

cpp
vector<int> dijkstra(int start, const vector<vector<pair<int, int>>>& graph) {
    int n = graph.size();
    vector<int> dist(n, INT_MAX);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    
    dist[start] = 0;
    pq.push({0, start});
    
    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();
        
        if (d > dist[u]) continue;
        
        for (auto [v, w] : graph[u]) {
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
    return dist;
}

4.2 Bellman-Ford算法 ​

cpp
vector<int> bellmanFord(int start, int n, const vector<tuple<int, int, int>>& edges) {
    vector<int> dist(n, INT_MAX);
    dist[start] = 0;
    
    for (int i = 0; i < n - 1; i++) {
        for (auto [u, v, w] : edges) {
            if (dist[u] != INT_MAX && dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
            }
        }
    }
    
    // 检测负权环
    for (auto [u, v, w] : edges) {
        if (dist[u] != INT_MAX && dist[v] > dist[u] + w) {
            // 存在负权环
        }
    }
    return dist;
}

4.3 Floyd-Warshall算法 ​

cpp
vector<vector<int>> floydWarshall(const vector<vector<int>>& graph) {
    int n = graph.size();
    vector<vector<int>> dist = graph;
    
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (dist[i][k] != INT_MAX && dist[k][j] != INT_MAX) {
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }
    }
    return dist;
}

五、图论算法对比 ​

算法用途时间复杂度适用场景
Flood Fill连通区域标记O(n*m)图像分割、区域标记
Kruskal最小生成树O(E log E)稀疏图
Prim最小生成树O(E + V log V)稠密图
Dijkstra最短路径O((V + E) log V)非负权图
Bellman-Ford最短路径O(VE)含负权边图
Floyd-Warshall所有点对最短路径O(V³)稠密图、小规模图

百炼成钢，融会贯通

© 2026 百练百会（bestwit）GESP备考一站式平台 | 京ICP备16040576号-5