您的位置: 首页  >  文章  >  数据结构—图论

数据结构—图论

分类: 文章 • 2025-02-06 20:27:40
图论〔Graph Theory〕是数学的一个分支。它以图为研究对象。图论中的图是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系。

图论是一种表示 "多对多" 的关系

图是由顶点和边组成的：(可以无边，但至少包含一个顶点)

  • 一组顶点：通常用 V(vertex) 表示顶点集合
  • 一组边：通常用 E(edge) 表示边的集合

图可以分为有向图和无向图，在图中：

  • (v, w) 表示无向边，即 v 和 w 是互通的
  • <v, w> 表示有向边，该边始于 v，终于 w

图可以分为有权图和无权图：

  • 有权图：每条边具有一定的权重(weight)，通常是一个数字
  • 无权图：每条边均没有权重，也可以理解为权为 1

图又可以分为连通图和非连通图：

  • 连通图：所有的点都有路径相连
  • 非连通图：存在某两个点没有路径相连

图中的顶点有度的概念：
  • 度(Degree)：所有与它连接点的个数之和
  • 入度(Indegree)：存在于有向图中，所有接入该点的边数之和
  • 出度(Outdegree)：存在于有向图中，所有接出该点的边数之和

图的表示：

图在程序中的表示一般有两种方式：

1. 邻接矩阵：

  • 在 n 个顶点的图需要有一个 n × n 大小的矩阵
  • 在一个无权图中，矩阵坐标中每个位置值为 1 代表两个点是相连的，0 表示两点是不相连的
  • 在一个有权图中，矩阵坐标中每个位置值代表该两点之间的权重，0 表示该两点不相连
  • 在无向图中，邻接矩阵关于对角线相等

2. 邻接链表：

  • 对于每个点，存储着一个链表，用来指向所有与该点直接相连的点
  • 对于有权图来说，链表中元素值对应着权重

例如在无向无权图中：

数据结构—图论在无向有权图中：

数据结构—图论可以看出在无向图中，邻接矩阵关于对角线对称，而邻接链表总有两条对称的边

而在有向无权图中：

数据结构—图论邻接矩阵和链表对比：

  1. 邻接矩阵由于没有相连的边也占有空间，因此存在浪费空间的问题，而邻接链表则比较合理地利用空间
  2. 邻接链表比较耗时，牺牲很大的时间来查找，因此比较耗时，而邻接矩阵法相比邻接链表法来说，时间复杂度低。

图的遍历：

图的遍历就是要找出图中所有的点，一般有以下两种方法：

1. 深度优先遍历：(Depth First Search, DFS)

基本思路：深度优先遍历图的方法是，从图中某顶点 v 出发

  1. 访问顶点 v
  2. 从 v 的未被访问的邻接点中选取一个顶点 w，从 w 出发进行深度优先遍历
  3. 重复上述两步，直至图中所有和v有路径相通的顶点都被访问到
2. 广度优先搜索：(Breadth First Search, BFS)

广度优先搜索，可以被形象地描述为 "浅尝辄止"，它也需要一个队列以保持遍历过的顶点顺序，以便按出队的顺序再去访问这些顶点的邻接顶点。

实现思路：

  1. 顶点 v 入队列
  2. 当队列非空时则继续执行，否则算法结束
  3. 出队列取得队头顶点 v；访问顶点 v 并标记顶点 v 已被访问
  4. 查找顶点 v 的第一个邻接顶点 col
  5. 若 v 的邻接顶点 col 未被访问过的，则 col 继续
  6. 查找顶点 v 的另一个新的邻接顶点 col，转到步骤 5 入队列，直到顶点 v 的所有未被访问过的邻接点处理完。转到步骤 2

要理解深度优先和广度优先搜索，首先要理解搜索步，一个完整的搜索步包括两个处理

  1. 获得当前位置上，有几条路可供选择
  2. 根据选择策略，选择其中一条路，并走到下个位置

相当于在漆黑的夜里，你只能看清你站的位置和你前面的路，但你不知道每条路能够通向哪里。搜索的任务就是，给出初始位置和目标位置，要求找到一条到达目标的路径。

  • 深度优先就是，从初始点出发，不断向前走，如果碰到死路了，就往回走一步，尝试另一条路，直到发现了目标位置。这种不撞南墙不回头的方法，即使成功也不一定找到一条好路，但好处是需要记住的位置比较少。
  • 广度优先就是，从初始点出发，把所有可能的路径都走一遍，如果里面没有目标位置，则尝试把所有两步能够到的位置都走一遍，看有没有目标位置；如果还不行，则尝试所有三步可以到的位置。这种方法，一定可以找到一条最短路径，但需要记忆的内容实在很多，要量力而行。

最短路径算法 (Shortest Path Algorithm)

1. 无权图：

问题：在图中找到某一个顶点到其它所有点的距离

基本步骤：

  1. 将所有点的距离 d 设为无穷大
  2. 挑选初始点 s，将 ds 设为 0，将 shortest 设为 0
  3. 找到所有距离为 d 为 shortest 的点，查找他们的邻接链表的下一个顶点 w，如果 dw 的值为无穷大，则将 dw 设为 shortest + 1
  4. 增加 shortest 的值，重复步骤 3，直到没有顶点的距离值为无穷大
数据结构—图论2. 有权图：

在有权图中，常见的最短路径算法有 Dijkstra 算法 Floyd 算法

迪杰斯特拉 Dijkstra 算法：Dijkstra 算法适用于权值为正的的图

Dijkstra 算法属于单源算法，即只能求出某点到其它点最短距离，并不能得出任意两点之间的最短距离。

算法步骤：

  1. 将所有边初始化为无穷大
  2. 选择一个开始的顶点，添加到优先队列中
  3. 对于该点的所有邻接顶点进行判断，如果到该点的距离小于原先的值，则将该值进行更新
  4. 将该点所有邻接顶点添加到优先队列中
  5. 从优先队列中挑选出一个路径值最小的顶点，将其弹出，作为新的顶点，重复步骤 3，4，5
  6. 直到所有点都被处理过一次

例如：

数据结构—图论
对于初始点 v 来说，某个点的 d 代表该点到初始点的距离。

首先选取 v0 作为起始点，添加到优先队列中，将v0弹出，然后对 v0 邻接点进行判断，由于一开始所有边都为无穷大，那么 <v0, v1> 和 <v0, v3> 都更新，值为 2 和 1，按路径大小升序将v3、v1添加到优先队列。

数据结构—图论

之后将 v3 弹出，对所有 v3 邻接点进行值的更新，并将所有邻接点按路径大小升序添加到优先队列中，若遇到值相同，则无所谓其先后顺序

数据结构—图论

数据结构—图论

重复这样的过程，直到所有的点都被处理过，则算法终止，这样最后可以得出从 v0 到其它 v1~v6 节点的距离。

Dijkstra 算法适合于权值为正的情况下，若权值为负则不能使用，因为出现死循环。这时候我们需要计算每个顶点被处理的次数，当某个顶点已经处理过的话，就跳出该循环。


佛洛伊德 Floyd 算法：可以求出任意两点的最短距离

Floyd 算法是一个经典的动态规划算法。用通俗的语言来描述的话，首先我们的目标是寻找从点 i 到点 j 的最短路径。

从任意节点 i 到任意节点 j 的最短路径不外乎 2 种可能：

  1. 是直接从 i 到 j
  2. 是从 i 经过若干个节点 k 到 j

所以，我们假设 Dis(i,j) 为节点 u 到节点 v 的最短路径的距离，对于每一个节点 k，我们检查Dis(i,k) + Dis(k,j) < Dis(i,j) 是否成立，如果成立，证明从 i 到 k 再到 j 的路径比 i 直接到 j 的路径短，我们便设置 Dis(i,j) = Dis(i,k) + Dis(k,j)，这样一来，当我们遍历完所有节点 k，Dis(i,j) 中记录的便是 i 到 j 的最短路径的距离。

时间复杂度： O(n^3)

最小生成树 (Minimum Spanning Trees MST)

例如：要在 n 个城市之间铺设光缆，主要目标是要使这 n 个城市的任意两个之间都可以通信，但铺设光缆的费用很高，且各个城市之间铺设光缆的费用不同，因此另一个目标是要使铺设光缆的总费用最低。这就需要找到带权的最小生成树。

特点：

  1. 该树是连通的
  2. 权值之和最小
  3. 边数比顶点个数少 1

存在个数：最小生成树在一些情况下可能会有多个

  1. 当图的每一条边的权值都相同时，该图的所有生成树都是最小生成树
  2. 如果图的每一条边的权值都互不相同，那么最小生成树将只有一个

比如：

数据结构—图论

生成最小生成树的算法一般有两种，分别是 Prim 算法和 Kruskal 算法

1. 普里姆算法 (Prim 算法):

算法步骤：

  1. 输入：一个加权连通图，其中顶点集合为 V，边集合为 E
  2. 初始化：Vnew = {x}，其中 x 为集合 V 中的任一节点(起始点)，Enew = {} 为空
  3. 在集合 E 中选取权值最小的边 <u, v>，其中 u 为集合 Vnew 中的元素，而 v 不在 Vnew 集合当中，并且 v∈V (如果存在有多条满足前述条件即具有相同权值的边，则可任意选取其中之一）
  4. 将 v 加入集合 Vnew 中，将 <u, v> 边加入集合 Enew 中
  5. 重复步骤 3、4 直到 Vnew = V

时间复杂度：O(V^2)

2. Kruskal 算法：需要一个集合用来升序存储所有边

算法步骤：

  1. 先构造一个只含有 n 个顶点，而边集为空的子图
  2. 从边集 E 中选取一条权值最小的边，若该条边的两个顶点分属不同的树，则将其加入子图。(也就是说，将这两个顶点分别所在的两棵树合成一棵树) 反之，若该条边的两个顶点已落在同一棵树上，则不可取，而应该取下一条权值最小的边再试之
  3. 重复步骤 2，直到所有点连通

时间复杂度：O( ElogV )

例如：

数据结构—图论在对所有边进行排序之后，我们得到一个边集合，从边集合中取出最小权的边 AD

数据结构—图论 剩下的边中寻找。我们找到了 CE。这里边的权重也是 5，依次类推我们找到了 6,7,7

数据结构—图论尽管现在长度为 8 的边是最小的未选择的边。但是他们已经连通了

数据结构—图论最后就剩下 EG 和 FG 了。当然我们选择了 EG

拓扑排序

拓扑排序是对有向无圈图的顶点的排序，使如果存在 vi 到 vj 的路径，则排序中 vi 在 vj 前面。如果图含有圈，则拓扑排序是不可能的。排序也不必是唯一的。拓扑排序的一个简单的方法是找到任意一个没有入边的顶点，加入序列，然后将该顶点和它的边从图中删除，对图重复该处理即得拓扑排序的结果。

定义顶点 v 的入度为边 (u,v) 的条数，计算图中所有顶点的入度。维护一个入度数组，每次遍历该数组来查找未分配拓扑编号的入度为0的顶点，找到后分配拓扑编号并更新入度数组，未找到说明存在圈。因为每次遍历都查找入度数组，所以该算法运行时间为  O(|V|2) 。O(|V|2)O(|V|2)

网络流问题：

设有向图

G=(V,E) 的给定边的容量为 cv,w ，有发点 s 和收点 t ，求从 s 到 t 可以通过的最大流量。对于 s 和 t之外的任一顶点 v ，总的进入流必然等于总的发出流。

这类问题一般都要分阶段解决。由图 G 构造一个流图 Gf ，表示在算法任意阶段已经达到的流，开始时 Gf 的所有边都没有流。再构造一个残余图 Gr ，表示每条边还能再添加多少流，可以从容量中减去当前的流来计算残余的流。每个阶段中，寻找 Gr 中从 s 到 t 的路径，称为增长通路，该路径上的最小值边就是可以添加到路径每一边上的流的量。调整 Gf 并重新计算 Gr ，当发现 Gr 中没有新路径时算法终止。路径的选择是任意的。

上面的算法有个问题是，路径选择的不同可能出现不同的结果，选择有些路径会在达到最大流量前就找不到新的路径。这是贪婪算法行不通的一个例子。

解决该问题可以通过在 Gr 中选择的路径上加上相反方向的流。可以证明，如果边的容量为有理数，该算法总能以最大流终止。这个算法并不要求图是无圈的。如果容量都为整数且最大流为 f ，则有 f 个阶段，一条增长通路可以用无权最短路径算法以 O(|E|) 时间找到，因此总运行时间为 O(f⋅|E|) 。

现在还有一个问题，如果存在流特别大的通路，因为路径是任意选择的，可能出现多次运行运行时间差距特别大的情况。避免这个问题的方法是总是选择使流增长最大的路径，可以通过修改Dijkstra算法来完成。如果最大的边容量为 capmax ，则有 O(|E|logcapmax) 个阶段，对增长通路的每次计算需要 O(|E|log|V|) 时间，因此总运行时间为 O(|E|2log|V|logcapmax) ，如果容量为小整数，则为 O(|E|2log|V|) 。


相关推荐