大学生涯学习算法 CPT102

CPT102-图论

迟然2024-05-312024-06-02

第一讲

主要内容包括图论的基本定义、图的性质、路径、树、有向图及其应用，如网络流等。下面是对文档内容的中文分析和总结：

基本定义

图（Graph G）：由有限的顶点集合 $V(G)$ 和连接顶点对的有限边集合 $E(G)$ 组成。
图的阶（Order）：图中顶点的数量，记作 $|V|$。

图的性质

邻接（Adjacency）：如果两个顶点由边连接，则它们是邻接的。
邻居（Neighbors）：邻接的顶点称为邻居。
入边（Incident）：连接顶点的边称为入边。

特殊类型的图

多重边（Multiple Edges）：连接同一对顶点的两条或多条边。
环（Loops）：连接顶点到它自己的边。
简单图（Simple Graph）：不包含多重边或环的图。

应用示例

旅行商问题（TSP）：找到覆盖所有城市的最小成本路径。
路由问题：找到从洛杉矶到纽约的最小延迟路径。

加权图

权重（Weight）：分配给每条边的数值，可以表示距离、容量或成本。

有向图（Digraphs）

有向图：图中的边有方向，用箭头（弧）表示。

度（Degree）

顶点的度（Degree）：边与顶点 V 相联系的次数，记作 $d(V)$。
度序列（Degree Sequence）：按非增序排列的顶点度数序列，必要时重复。

子图（Subgraphs）

子图：顶点集和边集都是原图的子集的图。
生成子图（Spanning Subgraph）：如果子图 H 覆盖了 G 的所有顶点，即 $V(H) = V(G)$，则称为生成子图。

第二讲

主要内容包括图的路径、连通图、图的邻接矩阵和关联矩阵。以下是对文档内容的中文分析和总结：

路径、步道和回路

步道（Walk）：是顶点和边序列的一种形式，表示从一个顶点到另一个顶点的移动。
步道的长度：步道中边的数量。
迹（Trail）：如果步道中的边都是不同的，则称为迹。
路径（Path）：如果步道中的顶点也都是不同的，则称为路径。
闭迹（Closed Walk）：起点和终点相同的步道。
回路或循环（Cycle or Circuit）：闭迹中除了起点和终点相同外，其他顶点都不同的称为回路或循环。

连通图

连通图（Connected Graph）：图中任意两个顶点之间都存在路径。
断开的图（Disconnected Graph）：由多个组成部分构成的图，每个部分内部可以是连通的，但部分之间没有路径连接。
组成部分（Components）：断开的图中，每个内部连通的子图称为一个组成部分。

图的矩阵表示

关联矩阵（Incidence Matrix）：顶点和边的关联矩阵，是一个 $|V| \times |E|$ 的矩阵，其中的元素表示顶点和边的关联次数。
邻接矩阵（Adjacency Matrix）：顶点和顶点之间的邻接矩阵，是一个 $|V| \times |V|$ 的矩阵，其中的元素表示两个顶点之间边的数量。

第三讲

主要内容包括树和森林、生成树、最小生成树、贪婪算法确定最小生成树以及最短路径问题。以下是对文档内容的中文分析和总结：

树和森林

树（Tree）：是无环的连通图。
森林（Forest）：是无环的图，可能连通也可能不连通。

树的性质

如果树 $T$ 至少有两个顶点，那么它具有以下性质：
- 从树 $T$ 中的任意顶点 $V_i$ 到另一个顶点 $V_j$ 恰好有一条路径。
- 从树 $T$ 中移除任意一条边，会得到两个组成部分，每个部分都是一棵树。
- 边的数量 $|E|$ 等于顶点数量 $|V|$ 减去 1。

生成树

生成树：是图 $G$ 的一个生成子图，即树 $T$ 与 $G$ 有相同的顶点集合。
如何绘制生成树：
- 选择 $G$ 中的任意一个顶点作为初始部分树。
- 逐个添加边，使得每个新边将一个新顶点连接到部分树上。
- 停止条件：如果图中有 $n$ 个顶点，则生成树将有 $n$ 个顶点和 $n-1$ 条边。

最小生成树

最小生成树：在所有生成树中，具有最小成本的生成树。
应用场景：
- 城市规划：设计连接多个城市的最低成本道路布局。
- 通信领域：以太网桥接布局自动配置，避免数据包在同一网络段上发送两次，因此需要使用无环的最小生成树。

贪婪算法确定最小生成树

贪婪算法：选择任意一个起始顶点形成初始部分树 $V_i$。
添加到新顶点形成新部分树的最便宜的边 $E_i$。
重复第二步，直到所有顶点都被包含在树中。

最短路径问题

图中的权重可以表示通信网络中的延迟或道路上的旅行时间。
实际问题：找到任意两个顶点之间的最短路径。
最短路径意味着最短延迟。

总结

定义了树、森林和生成树。
展示了如何绘制生成树。
引入了最小生成树的概念。
提出了贪婪算法来确定最小生成树：先选择最短的边。
引入了最短路径问题：在加权图中找到任意两个顶点之间的最短路径。

第四讲

主要介绍了一种用于确定加权图中两个顶点之间最短路径的算法——迪杰斯特拉最短路径算法（Dijkstra’s Shortest Path Algorithm, SPA）。以下是对文档内容的中文分析和总结：

最短路径算法

文档通过一个通信网络的例子，展示了如何使用加权图来表示网络，其中权重表示与每条边相关联的延迟。目标是找到从起点 $s$ 到终点 $t$ 的最小延迟路径。

算法步骤

阶段 1：从起始顶点 $s$ 开始，将其作为第一阶段的参考顶点，给所有相邻顶点标记使用单条边的路径长度，其他顶点标记为一个非常大的数（大于图中所有权重之和）。
阶段 2：选择未作为参考顶点的最小标签顶点作为第二阶段的参考顶点，这里是顶点 $a$。更新通过 $a$ 到达相邻顶点的路径长度。
阶段 3：重复步骤，选择未作为参考顶点的最小标签顶点作为下一阶段的参考顶点，这里是顶点 $c$。更新通过 $c$ 到达相邻顶点的路径长度。
阶段 4：继续这个过程，选择顶点 $e$ 作为第四阶段的参考顶点。
阶段 5：选择顶点 $b$ 作为新的参考顶点，更新通过 $b$ 到达相邻顶点的路径长度。
阶段 6：选择顶点 $d$ 作为新的参考顶点，更新通过 $d$ 到达剩余顶点的路径长度。
阶段 7：剩余顶点 $t$ 获得最小标签，算法停止，因为这是从 $s$ 到 $t$ 的最短路径长度。

迪杰斯特拉最短路径算法（SPA）

从初始节点开始，为每个节点分配一个临时距离值：初始节点为 0，其他节点为无穷大。
将初始节点设置为当前节点，将所有其他节点标记为未访问，并创建一个名为“未访问集”的集合。
对于当前节点，考虑其所有未访问的邻居，并计算它们的临时距离。将新计算的临时距离与当前分配的值进行比较，并分配较小的一个。
完成当前节点所有邻居的考虑后，将其标记为已访问，并从未访问集中移除。已访问的节点将不再被检查。
如果目标节点已被标记为已访问，或未访问集中节点的最小临时距离为无穷大，则停止。算法完成。
否则，选择标记有最小临时距离的未访问节点，将其设置为新的“当前节点”，然后返回步骤 3。

算法的优越性

为什么 SPA 是最优的？：SPA 为什么能提供最短路径？

迪杰斯特拉最短路径算法（SPA）是最优的，因为它系统性地寻找从一个起点到所有其他顶点的最短路径。SPA 的核心思想是逐步确定从起点到图中所有顶点的最短路径，它保证一旦找到从起点到某个顶点的最短路径，这个路径长度就不会被后续的迭代改变。这是因为算法总是选择当前未访问顶点中距离最小的顶点作为下一步的“参考顶点”，并且只考虑通过这个顶点到达相邻顶点的路径，如果这个路径比已知的路径更短，则更新该路径长度。

SPA 能够提供最短路径的原因在于：

贪心选择：每次迭代中，它选择最小已知距离的顶点作为当前顶点，并假设这是到达该顶点的最短路径。
松弛操作：对于每个邻居，算法执行松弛操作，如果通过当前顶点到达邻居的距离比已知的更短，则更新这个距离。
最优子结构：SPA 利用了最短路径问题的最优子结构性质，即如果两个顶点之间的最短路径包含第三个顶点，则通过第三个顶点到达另外两个顶点的部分路径也必须是最短的。

SPA 的复杂度是什么？

SPA 的时间复杂度主要取决于它如何处理图中的顶点和边。在最基本的形式中，如果使用一个简单的数组来存储距离，并且对于每个顶点都遍历其所有邻居来执行松弛操作，其时间复杂度是 (O(|V|^2))，其中 (|V|) 是顶点的数量。但是，通过使用优先队列（例如二叉堆）来管理未访问的顶点，可以显著减少查找最小顶点的时间，从而将时间复杂度降低到 (O(|V|+|E|\log|V|))，其中 (|E|) 是边的数量。