数据结构笔记-图部分。

图

图的定义

图（Graph）是一种抽象数据类型，用于存储具有多对多逻辑关系的复杂数据结构。在图中，数据以节点（Nodes）的形式存在，节点之间的关系以边（Edges）的形式表示。

图 $ G $ 是由顶点集 $ V $ 和边集 $ E $ 组成的，记为 $ G = (V, E) $。
边是顶点的有序对或无序对，反映了顶点之间的关系。
有向图：边是顶点的有序对的图，每条边有方向。
无向图：边是顶点的无序对的图，边没有方向。

基本术语

顶点（Vertex）：图中的数据元素。
边：有向图中，顶点 $ Vi $ 到顶点 $ Vj $ 的边，也称弧。
完全图：无向完全图边数为 $ n(n - 1) / 2 $，有向完全图边数为 $ n(n - 1) $。
子图：图 $ G $ 和 $ G’ $，若 $ V(G’) \subseteq V(G) $ 和 $ E(G’) \subseteq E(G) $，则称 $ G’ $ 为图 $ G $ 的子图。
邻接：若 $ (Vi, Vj) \in E(G) $，则称 $ Vi $ 和 $ Vj $ 互为邻接点。
度：顶点 $ Vi $ 的度为与 $ Vi $ 相关联的边的个数。
- 无向图顶点 $ Vi $ 的度为与 $ Vi $ 相关联的边的个数。
- 有向图的出度OD：顶点Vi的出度为以Vi为尾的出边数。
- 有向图的入度ID：顶点Vi的入度为以Vi为头的入边数。
- 有向图的度D：入度 + 出度。
路径：顶点 $ Vp $ 至顶点 $ Vq $ 的路径是顶点序列 $ { Vp, Vi1, Vi2, …, Vin, Vq } $。
路径长度：路径上边或弧的数目。
连通：无向图中，若从顶点 $ Vi $ 到 $ Vj $ 顶点有路径，则称 $ Vi $ 和 $ Vj $ 是连通的。
简单路径：除第一个和最后一个外，其余各顶点均不相同的路径。
回路：第一个和最后一个顶点相同的路径。
简单回路：第一个和最后一个顶点相同的简单路径。

图的存储

顺序存储

使用二维数组来存储图的邻接矩阵。

邻接矩阵
- 表示图的各顶点之间关系的矩阵。
- 无向图的邻接矩阵是对称矩阵。
- 带权图的邻接矩阵存储边的权值。

链式存储

邻接表存储结构：用链表存储每个节点的所有邻接点。
- 对图 $ G $ 中每个顶点都建立一个单链表，第 $ i $ 个单链表链接图中与顶点 $ Vi $ 相邻接的所有顶点。
- 邻接表在边稀疏时比邻接矩阵省单元。
十字链表存储结构：为有向图设计，包含两个链表，分别存储每个节点的出边和入边。
邻接多重表存储结构：为带权图设计，存储每个节点的所有邻接点及其权重。

图的遍历

深度优先搜索（DFS）

定义：深度优先搜索（DFS）是一种用于遍历或搜索树或图的算法。在图的遍历中，DFS 从任意顶点开始，尽可能深地搜索图的分支。当到达一个顶点的所有邻接顶点都被访问过后，算法会回溯到上一个顶点，并继续搜索下一个未访问的邻接顶点。

过程：

选择起始顶点：从图中任选一个顶点 $ V_i $ 作为起始顶点。
访问顶点：访问起始顶点 $ V_i $。
访问邻接顶点：从 $ V_i $ 开始，访问其所有未访问过的邻接顶点 $ V_j $。
递归搜索：对每个未访问的邻接顶点 $ V_j $，递归地进行深度优先搜索。
回溯：当当前顶点的所有邻接顶点都被访问过后，回溯到上一个顶点，继续搜索下一个未访问的邻接顶点。
结束条件：当所有顶点都被访问过时，遍历结束。

算法实现： DFS 可以通过递归或栈实现。以下是使用递归实现的伪代码：

void DFS(Graph g, int v) {
    visited[v] = 1; // 标记顶点 v 为已访问
    for each w adjacent to v in g {
        if (!visited[w]) {
            DFS(g, w); // 递归访问邻接顶点 w
        }
    }
}

复杂度：

时间复杂度：$ O(V + E) $，其中 $ V $ 是顶点数，$ E $ 是边数。
空间复杂度：$ O(V) $，用于存储访问标记和递归调用的栈。

广度优先搜索（BFS）

定义：广度优先搜索（BFS）是一种遍历图的算法，从一个顶点开始，逐层访问所有顶点。在每一层中，先访问所有未访问的邻接顶点，然后再访问这些邻接顶点的邻接顶点。

过程：

选择起始顶点：从图中任选一个顶点 $ V_i $ 作为起始顶点。
访问顶点：访问起始顶点 $ V_i $ 并将其加入队列。
访问邻接顶点：从队列中取出一个顶点，访问其所有未访问的邻接顶点，并将这些邻接顶点加入队列。
重复访问：重复步骤 3，直到队列为空。
结束条件：当队列为空，即所有顶点都被访问过时，遍历结束。

算法实现： BFS 通常使用队列实现。以下是使用队列实现的伪代码：

void BFS(Graph g, int v) {
    queue Q;
    visited[v] = 1; // 标记顶点 v 为已访问
    EnQueue(Q, v); // 将顶点 v 加入队列

    while (!IsEmpty(Q)) {
        v = DeQueue(Q); // 从队列中取出一个顶点
        for each w adjacent to v in g {
            if (!visited[w]) {
                visited[w] = 1; // 标记顶点 w 为已访问
                EnQueue(Q, w); // 将顶点 w 加入队列
            }
        }
    }
}

复杂度：

时间复杂度：$ O(V + E) $，其中 $ V $ 是顶点数，$ E $ 是边数。
空间复杂度：$ O(V) $，用于存储访问标记和队列。

应用

DFS：常用于解决连通性问题、生成树问题、拓扑排序等。
BFS：常用于寻找最短路径（如在无权图中）、社交网络中的“六度分隔”问题等。

生成树

定义：生成树是包含连通图中所有顶点的极小连通子图。对于一个有 $ n $ 个顶点的连通图，生成树的边数为 $ n-1 $。

特点：

生成树覆盖了图中的所有顶点。
生成树不包含任何回路。

类型：

深度优先生成树：按照深度优先搜索的顺序生成的生成树。
广度优先生成树：按照广度优先搜索的顺序生成的生成树。

最小生成树

定义：最小生成树是一棵生成树，其所有边的权值之和最小。在带权图中，最小生成树问题就是找到一棵生成树，使得所有边的权重之和最小。

Prim算法：

适用场景：适合于边稠密的带权图。
基本思想：
1. 从任意一个顶点开始，初始化最小生成树 $ T $ 为空。
2. 每次从图中选择一条连接 $ T $ 和 $ V-T $（$ V $ 是所有顶点的集合）的权值最小的边，并将其加入 $ T $。
3. 重复步骤 2，直到 $ T $ 包含所有顶点。

Kruskal算法：

适用场景：适合于边稀疏的网。
基本思想：
1. 将所有边按权值从小到大排序。
2. 依次选择权值最小的边，如果这条边不会在 $ T $ 中形成回路，则将其加入 $ T $。
3. 重复步骤 2，直到 $ T $ 包含 $ n-1 $ 条边。

复杂度：

Prim算法：$ O(E^2) $ 或 $ O((V+E) \log V) $（使用优先队列）。
Kruskal算法：$ O(E \log E) $ 或 $ O(E \log V) $（使用排序）。

最短路径

Dijkstra算法

定义： Dijkstra算法是一种用于在带权图中找到单个源点到所有其他顶点的最短路径的算法。

基本思想：

从源点开始，初始化所有顶点的距离为无穷大，将源点的距离设为 0。
从未访问的顶点中选择距离最小的顶点 $ u $，标记为已访问。
更新 $ u $ 的所有未访问邻接顶点 $ v $ 的距离：如果通过 $ u $ 到达 $ v $ 的距离小于 $ v $ 当前的距离，则更新 $ v $ 的距离。
重复步骤 2 和 3，直到所有顶点都被访问。

复杂度：

时间复杂度：$ O(V^2) $（简单实现），$ O((V+E) \log V) $（使用优先队列）。

拓扑排序

拓扑排序是一种对有向无环图（DAG）的顶点进行线性排序的算法，使得对于任何一条从顶点 $ u $ 到顶点 $ v $ 的有向边，顶点 $ u $ 都在顶点 $ v $ 之前。这种排序不是唯一的。拓扑排序常用于任务调度、课程规划等领域。

定义

AOV网络（Activity on Vertex network）：

顶点表示活动或任务。
边表示活动或任务之间的优先关系。

拓扑排序：

对AOV网构造顶点线性序列 $ (v_1, v_2, …, v_n) $，使得对于任意 $ i < j $，如果存在从 $ v_i $ 到 $ v_j $ 的路径，则 $ v_i $ 在 $ v_j $ 之前。

拓扑排序方法

基本思想：

在AOV网中选一个无前趋（即入度为0）的顶点并输出。
从AOV网中删去该顶点及以它为尾的所有弧。
重复步骤1和2，直到所有顶点都被输出或无法继续进行。

结果：

如果所有顶点都被输出，则图中无回路，且得到的线性序列是拓扑有序序列。
如果输出的顶点数小于 $ n $，则说明图中存在回路，工程不可行。

深度优先算法实现：

初始化：为每个顶点增加一个存放顶点入度的域 $ in $。
入度统计：统计每个顶点的入度。
入度为0的顶点入栈：将所有入度为0的顶点入栈。
循环：
- 弹出栈顶元素 $ V_j $ 并输出。
- 检查 $ V_j $ 的出边表，将每条出边 $ (V_j, V_k) $ 的终点 $ V_k $ 的入度域减1。
- 若 $ V_k $ 的入度为0，则 $ V_k $ 入栈。
结束条件：如果输出的顶点数小于 $ n $，则输出有回路；否则，拓扑排序结束。

广度优先算法实现：

初始化：为每个顶点增加一个存放顶点入度的域 $ in $。
入度统计：统计每个顶点的入度。
入度为0的顶点入队：将所有入度为0的顶点入队。
循环：
- 弹出队头元素 $ V_j $ 并输出。
- 检查 $ V_j $ 的出边表，将每条出边 $ (V_j, V_k) $ 的终点 $ V_k $ 的入度域减1。
- 若 $ V_k $ 的入度为0，则 $ V_k $ 入队。
结束条件：如果输出的顶点数小于 $ n $，则输出有回路；否则，拓扑排序结束。

复杂度：

时间复杂度：$ O(V + E) $，其中 $ V $ 是顶点数，$ E $ 是边数。
空间复杂度：$ O(V) $，用于存储入度和栈/队列。