百练百会 bestWit

Appearance

L7_03 图的定义及遍历 ​

一、图的概念 ​

1.1 图的定义 ​

图（Graph）是由顶点（Vertex）和边（Edge）组成的一种数据结构。

1.2 图的分类 ​

类型定义特点
无向图边没有方向边是双向的
有向图边有方向边是单向的
加权图边带有权重边表示距离、成本等
无权图边没有权重所有边权重相同

1.3 图的表示 ​

1.3.1 邻接矩阵 ​

cpp
// 无向图的邻接矩阵表示
class GraphMatrix {
private:
    vector<vector<int>> adj;
    int n;
    
public:
    GraphMatrix(int size) : n(size) {
        adj.resize(n, vector<int>(n, 0));
    }
    
    void addEdge(int u, int v) {
        adj[u][v] = 1;
        adj[v][u] = 1; // 无向图
    }
    
    void addEdge(int u, int v, int weight) {
        adj[u][v] = weight;
        adj[v][u] = weight; // 无向加权图
    }
};

1.3.2 邻接表 ​

cpp
// 无向图的邻接表表示
class GraphAdjList {
private:
    vector<vector<int>> adj;
    int n;
    
public:
    GraphAdjList(int size) : n(size) {
        adj.resize(n);
    }
    
    void addEdge(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    
    void addEdge(int u, int v, int weight) {
        adj[u].emplace_back(v, weight);
        adj[v].emplace_back(u, weight);
    }
};

二、图的广度优先遍历(BFS) ​

2.1 BFS 算法 ​

cpp
void bfs(int start, const vector<vector<int>>& graph) {
    int n = graph.size();
    vector<bool> visited(n, false);
    queue<int> q;
    
    q.push(start);
    visited[start] = true;
    
    while (!q.empty()) {
        int node = q.front();
        q.pop();
        cout << node << " ";
        
        for (int neighbor : graph[node]) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                q.push(neighbor);
            }
        }
    }
}

2.2 BFS 求连通分量 ​

cpp
int countComponents(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++;
            queue<int> q;
            q.push(i);
            visited[i] = true;
            
            while (!q.empty()) {
                int node = q.front();
                q.pop();
                
                for (int neighbor : graph[node]) {
                    if (!visited[neighbor]) {
                        visited[neighbor] = true;
                        q.push(neighbor);
                    }
                }
            }
        }
    }
    return count;
}

2.3 BFS 求最短路径 ​

cpp
vector<int> shortestPathBFS(int start, int end, const vector<vector<int>>& graph) {
    int n = graph.size();
    vector<bool> visited(n, false);
    vector<int> parent(n, -1);
    queue<int> q;
    
    q.push(start);
    visited[start] = true;
    
    while (!q.empty()) {
        int node = q.front();
        q.pop();
        
        if (node == end) break;
        
        for (int neighbor : graph[node]) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                parent[neighbor] = node;
                q.push(neighbor);
            }
        }
    }
    
    // 重建路径
    vector<int> path;
    for (int v = end; v != -1; v = parent[v]) {
        path.push_back(v);
    }
    reverse(path.begin(), path.end());
    return path;
}

三、图的深度优先遍历(DFS) ​

3.1 递归实现 ​

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

void dfs(int start, const vector<vector<int>>& graph) {
    int n = graph.size();
    vector<bool> visited(n, false);
    dfsRecursive(start, visited, graph);
}

3.2 非递归实现 ​

cpp
void dfsIterative(int start, const vector<vector<int>>& graph) {
    int n = graph.size();
    vector<bool> visited(n, false);
    stack<int> s;
    
    s.push(start);
    
    while (!s.empty()) {
        int node = s.top();
        s.pop();
        
        if (!visited[node]) {
            visited[node] = true;
            cout << node << " ";
            
            // 逆序压栈，保证顺序
            for (auto it = graph[node].rbegin(); it != graph[node].rend(); ++it) {
                if (!visited[*it]) {
                    s.push(*it);
                }
            }
        }
    }
}

3.3 DFS 检测环 ​

cpp
bool hasCycle(int node, int parent, vector<bool>& visited, const vector<vector<int>>& graph) {
    visited[node] = true;
    
    for (int neighbor : graph[node]) {
        if (!visited[neighbor]) {
            if (hasCycle(neighbor, node, visited, graph)) {
                return true;
            }
        } else if (neighbor != parent) {
            return true;
        }
    }
    return false;
}

bool detectCycle(const vector<vector<int>>& graph) {
    int n = graph.size();
    vector<bool> visited(n, false);
    
    for (int i = 0; i < n; i++) {
        if (!visited[i] && hasCycle(i, -1, visited, graph)) {
            return true;
        }
    }
    return false;
}

四、图的遍历应用 ​

4.1 拓扑排序 ​

cpp
vector<int> topologicalSort(const vector<vector<int>>& graph) {
    int n = graph.size();
    vector<int> inDegree(n, 0);
    queue<int> q;
    
    // 计算入度
    for (int i = 0; i < n; i++) {
        for (int neighbor : graph[i]) {
            inDegree[neighbor]++;
        }
    }
    
    // 入度为0的节点入队
    for (int i = 0; i < n; i++) {
        if (inDegree[i] == 0) {
            q.push(i);
        }
    }
    
    vector<int> result;
    while (!q.empty()) {
        int node = q.front();
        q.pop();
        result.push_back(node);
        
        for (int neighbor : graph[node]) {
            inDegree[neighbor]--;
            if (inDegree[neighbor] == 0) {
                q.push(neighbor);
            }
        }
    }
    
    return result;
}

4.2 判断二分图 ​

cpp
bool isBipartite(const vector<vector<int>>& graph) {
    int n = graph.size();
    vector<int> color(n, -1); // -1: 未染色, 0: 颜色A, 1: 颜色B
    
    for (int i = 0; i < n; i++) {
        if (color[i] == -1) {
            queue<int> q;
            q.push(i);
            color[i] = 0;
            
            while (!q.empty()) {
                int node = q.front();
                q.pop();
                
                for (int neighbor : graph[node]) {
                    if (color[neighbor] == -1) {
                        color[neighbor] = color[node] ^ 1;
                        q.push(neighbor);
                    } else if (color[neighbor] == color[node]) {
                        return false;
                    }
                }
            }
        }
    }
    return true;
}

4.3 岛屿数量 ​

cpp
void dfsIsland(vector<vector<char>>& grid, int i, int j) {
    if (i < 0 || i >= grid.size() || j < 0 || j >= grid[0].size() || grid[i][j] == '0') {
        return;
    }
    
    grid[i][j] = '0'; // 标记为已访问
    
    dfsIsland(grid, i+1, j);
    dfsIsland(grid, i-1, j);
    dfsIsland(grid, i, j+1);
    dfsIsland(grid, i, j-1);
}

int numIslands(vector<vector<char>>& grid) {
    int count = 0;
    for (int i = 0; i < grid.size(); i++) {
        for (int j = 0; j < grid[0].size(); j++) {
            if (grid[i][j] == '1') {
                count++;
                dfsIsland(grid, i, j);
            }
        }
    }
    return count;
}

五、图的遍历对比 ​

特性BFSDFS
数据结构队列栈/递归
空间复杂度O(n)O(n)
最短路径保证（无权图）不保证
应用场景最短路径、层序遍历连通性、拓扑排序
实现方式迭代递归/迭代

百炼成钢，融会贯通

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