图 深度优先遍历 广度优先遍历

图及其遍历.pdf

图，BFS, DFS

1. 图的定义与应用

  • 图是由节点（顶点）和边构成的数据结构，广泛应用于交通网络、通信网络、社交网络等。
  • 常见的图问题包括：
    • 图着色（节点染色，最少颜色数目）
    • 最短路径（最小移动次数或最小代价）
    • 复杂问题如魔方复原等。

2. 图的表示方式

邻接矩阵（Adjacency Matrix）

  • 使用一个二维矩阵表示图，矩阵大小为 n×nn \times n （nn 是顶点数）。

  • 特点：

    • 优点：快速查询两个节点是否相邻。
    • 缺点：空间复杂度为 Θ(n2)\Theta(n^2)，不适合稀疏图。

  • 示例代码：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    const int INF = 1e9; // 表示无穷大
    int adjMatrix[100][100]; // 假设最多有100个节点

    void initializeMatrix(int n) {
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                adjMatrix[i][j] = (i == j ? 0 : INF); // 自环为0，其他初始化为无穷大
            }
        }
    }

邻接表（Adjacency List）

  • 使用链表或向量（vector）存储每个节点的邻接信息。

  • 特点：

    • 优点：空间复杂度为 Θ(n+m)\Theta(n + m) （mm 是边数），适合稀疏图。
    • 缺点：查询两个节点是否相邻速度较慢。

  • 示例代码：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    #include <vector>
    using namespace std;

    vector<int> adjList[100]; // 假设最多有100个节点

    void addEdge(int u, int v) {
        adjList[u].push_back(v);
        adjList[v].push_back(u); // 如果是无向图
    }

3. 图的遍历算法

广度优先搜索（BFS）

  • 特点：按层遍历节点，常用于最短路径计算。

  • 实现思路

    ：

    1. 使用队列维护待访问节点。
    2. 每次访问队首节点，并将其所有未访问的邻接节点加入队列。

  • 示例代码：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    #include <queue>

    void BFS(int start, int n) {
        vector<bool> visited(n, false);
        queue<int> q;
        q.push(start);
        visited[start] = true;

        while (!q.empty()) {
            int node = q.front(); q.pop();
            // 访问当前节点
            for (int neighbor : adjList[node]) {
                if (!visited[neighbor]) {
                    q.push(neighbor);
                    visited[neighbor] = true;
                }
            }
        }
    }

深度优先搜索（DFS）

  • 特点：尽可能深入探索一条路径，遇到死胡同时回溯。

  • 实现方式：可以递归或用栈实现。

  • 示例代码：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    void DFS(int node, vector<bool>& visited) {
        visited[node] = true;
        // 访问当前节点
        for (int neighbor : adjList[node]) {
            if (!visited[neighbor]) {
                DFS(neighbor, visited);
            }
        }
    }

    void startDFS(int start, int n) {
        vector<bool> visited(n, false);
        DFS(start, visited);
    }

4. BFS与DFS的比较

算法 优点 缺点 时间复杂度
BFS 找最短路径，层次遍历直观 内存开销大（需要维护队列） O(n+m)O(n + m)
DFS 内存使用低，适合搜索深层信息 无法保证最短路径 O(n+m)O(n + m)

5. 应用与扩展

  • BFS的扩展：
    • 求无权图的最短路径。
    • 遍历所有连通分量。
  • DFS的扩展：
    • 生成DFS树，记录每个节点的发现和完成时间。
    • 边分类（树边、回边、前向边、交叉边）。

如需更详细的代码或具体例子，可以根据课程内容的重点深入补充！

图的定义与分类

1. 什么是图？

图（Graph）是一种数据结构，由 顶点（Vertex） 和 边（Edge） 组成，表示事物之间的关系。一个图通常记为 G=(V,E)G = (V, E)，其中：

  • VV 是顶点的集合，表示图中的所有节点。
  • EE 是边的集合，表示节点之间的连接关系。

2. 无权图（Unweighted Graph）

  • 无权图是一类特殊的图，在无权图中，每条边没有权重，即所有边的代价或距离视为相等（通常为1）。
  • 无权图通常用于简化问题，例如寻找两点之间的最短路径等。

示例：

  • 如果 AA 和 BB 之间有一条边，这条边没有具体的权重，仅表示 AA 和 BB 之间有连接关系。

无权图的一个简单表示：

1
2
3
A --- B
|     |
C --- D

在上述图中，所有边的权重隐含为1（默认值），因此路径的长度等于经过的边数。

3. 图的分类

根据顶点和边的不同特性，图可以分为多种类型。

3.1 按边是否有方向分类

  1. 无向图（Undirected Graph）：

    • 图中的边没有方向，即 (u,v)(u, v) 和 (v,u)(v, u) 表示同一条边。
    • 无向图适用于对称关系，如社交网络中的“好友关系”。

    示例：

    1
    2
    3
    A --- B
    |     |
    C --- D

  2. 有向图（Directed Graph，或Digraph）：

    • 图中的边有方向，即 (u,v)(u, v) 表示从 uu 到 vv 的有向边，(v,u)(v, u) 表示从 vv 到 uu 的另一条独立的有向边。
    • 有向图适用于单向关系，如网页之间的超链接、任务的依赖关系。

    示例：

    1
    2
    3
    A → B
    ↑   ↓
    C ← D

3.2 按边是否有权分类

  1. 无权图（Unweighted Graph）：

    • 边没有权重，所有边的代价相等。
    • 通常用于简单的路径或连通性问题。

  2. 有权图（Weighted Graph）：

    • 边带有权重，用于表示边的“代价”或“距离”。
    • 有权图适用于需要考虑代价的场景，例如最短路径（Dijkstra算法）或最小生成树（Kruskal算法）。

    示例：

    1
    2
    3
    4
    5
    A --3-- B
    |      /
    2     4
    |   /
    C --5-- D

3.3 按是否允许边重复或自环分类

  1. 简单图（Simple Graph）：
    • 无自环（边的两个端点相同，如 (u,u)(u, u)）且没有重边（两个顶点之间有多条边）。
  2. 多重图（Multi Graph）：
    • 允许有重边，即两个节点之间可以有多条边。
  3. 伪图（Pseudo Graph）：
    • 允许有自环。

3.4 按图的连通性分类

  1. 连通图（Connected Graph）：

    • 对于无向图，任意两个顶点之间都有路径相连。
    • 对于有向图，若任意两个顶点之间都存在路径（无论方向），则称为强连通图（Strongly Connected Graph）。

    示例：

    1
    A --- B --- C

  2. 非连通图（Disconnected Graph）：

    • 图中存在不连通的部分，即某些顶点之间没有路径相连。

    示例：

    1
    A --- B     C

3.5 特殊图的分类

  1. 完全图（Complete Graph）：

    • 图中任意两个顶点之间都有边相连。
    • 一个有 nn 个顶点的完全图有 n(n−1)2\frac{n(n-1)}{2} 条边。

    示例：

    1
    2
    3
    A --- B
    | \ / |
    C --- D

  2. 树（Tree）：

    • 一种特殊的连通无向图，没有环路，且任意两个节点之间有唯一路径。
    • 树是一个有 nn 个节点和 n−1n-1 条边的无向连通图。

    示例：

    1
    2
    3
    4
    5
      A
     / \
    B   C
       / \
      D   E

  3. 二分图（Bipartite Graph）：

    • 图的顶点集合可以分为两个不相交的子集 UU 和 VV，且所有边的两个端点分别属于 UU 和 VV。
    • 典型应用：匹配问题（如婚姻匹配、任务分配）。

    示例：

    1
    2
    3
    U: {A, B}
    V: {C, D}
    Edges: { (A, C), (B, C), (B, D) }

  4. 稀疏图和稠密图：

    • 稀疏图（Sparse Graph）：边数接近于顶点数， ∣E∣≈O(∣V∣)|E| \approx O(|V|)。
    • 稠密图（Dense Graph）：边数接近于最大可能边数， ∣E∣≈O(∣V∣2)|E| \approx O(|V|^2)。

  5. 平面图（Planar Graph）：

    • 图可以嵌入平面且没有边相交。

4. 图的表示方法

图通常有两种表示方法：

  1. 邻接矩阵：
    • 使用 n×nn \times n 的矩阵存储，适合稠密图。
    • 时间复杂度：
      • 查询节点是否相邻：O(1)O(1)
      • 遍历节点的所有邻居：O(n)O(n)。
  2. 邻接表：
    • 使用数组或链表存储每个节点的邻居列表，适合稀疏图。
    • 时间复杂度：
      • 查询节点是否相邻：O(n)O(n)
      • 遍历节点的所有邻居：O(k)O(k)，其中 kk 是邻居数。

5. 图分类的总结表

分类依据 类型 描述
边方向 无向图、有向图 边是否有方向
边权重 无权图、有权图 边是否带权重
边特性 简单图、多重图、伪图 是否允许重边或自环
连通性 连通图、非连通图 节点是否都连通
特殊结构 完全图、树、二分图 特定性质的图
边的稠密程度 稀疏图、稠密图 图的边数与节点数的关系
几何属性 平面图 图是否可以嵌入平面且无边相交

通过这些分类，可以根据问题的特性选择合适的算法和表示方式。

数据结构与算法 > 图论
#图 #DFS #BFS
图 深度优先遍历 广度优先遍历
http://wang-jiahao.github.io/posts/28191.html
作者
Jiahao Wang
发布于
2024年12月5日
更新于
2024年12月11日
许可协议