Maggie 的博客

简体中文

English

简体中文

English

外观

English

图的定义 ​

图是由顶点集 V 和顶点间的关系集合 E（边的集合）组成的一种数据结构，可以用二元组定义为：G=（V，E）

基本术语 ​

  1. 有向图和无向图

    在图中，若边具有方向，称为有向图；若边没有方向，称为无向图。

  2. 完全图、稠密图、稀疏图

    • 具有 n 个顶点，n(n-1)/2 条边的图，称为完全无向图
    • 具有 n 个顶点，n(n-1)条弧的有向图，称为完全有向图。
    • 完全无向图和完全有向图都称为完全图。
    • 对于一般无向图，顶点数为 n，边数为 e，则 0<=e<=n(n-1)/2
    • 对于一般有向图，顶点数为 n，弧数为 e，则 0<=e<=n(n-1)
    • 当一个图接近完全图时，则称它为稠密图，相反，当一个图含有较少的边或者弧则称为稀疏图

  3. 度、入度、出度

    • 在图中，一个顶点依附的边或弧的数目，称为该顶点的度。
    • 在有向图中，一个顶点依附的弧头数目，称为顶点的入度，一个顶点依附的弧尾数目，称为该顶点的出度，某个顶点的入度和出度之和称为该顶点的度。

图的存储 ​

图的存储结构可以分为5种：

  1. 邻接矩阵

    图的邻接矩阵存储方式是用两个数组来表示图：

    一个一维数组存储图中顶点信息；（顶点数组）
    一个二维数组（称为邻接矩阵）存储图中边或弧的信息（边数组）

  2. 邻接表

    邻接矩阵是一种不错的图存储结构。 但是： 对于边树相对顶点较少的图，这种结构是存在存储空间的极大浪费的。

    因此，可以考虑使用邻接表存储。

  3. 十字链表

    • 对于有向图而言，邻接表也是有缺陷的。
    • 试想想哈，关心了出度问题，想了解入度问题就必须把整个图遍历才能知道。
    • 反之，逆邻接表解决了入度问题却不了解出度的情况。
    • 那是否可以将邻接表和逆邻接表结合起来呢？答案是肯定的。
    • 这就是所谓的存储结构： 十字链表。

  4. 邻接多重表

    • 有向图的优化存储结构为十字链表。
    • 对于无向图的邻接表，删除一条边时，需要找到并处理两个对应的边结点。
    • 这种操作较为麻烦，邻接多重表可以改善这一问题。

  5. 边集数组

    • 边集数组侧重于对边依次进行处理的操作，而不适合对顶点相关的操作。
    • 边集数组由两个一维数组组成，一个存储顶点信息，一个存储边的信息，包括起点下标（start），终点下标（end）和权值（weight）

    图的遍历 ​

两种图遍历算法：

  1. 深度优先遍历（Depth_First_Search）,也称为深度优先搜索，简称DFS
  2. 广度优先遍历（Breadth_First_Search）,又称为广度优先搜索，简称BFS。

深度优先遍历类似树的前序遍历，广度优先遍历类似于树的层序遍历。

深度优先搜索 ​

深度优先搜索采用的思想🔖: 类似于树的先序遍历（根左右）

  1. 首先访问顶点 i，并将其访问标记置为访问过，即 visited[i]=1;
  2. 然后检查与顶点 i 相邻的顶点 j。若 j 未被访问，则访问它，设置 visited[j]=1，并从 j 开始重复此过程；若 j 已被访问，则继续检查 i 的其他相邻顶点。
  3. 若与 i 有边相连的顶点都被访问过，则退回到前一个访问顶点并重复刚才过程，直到从起点可达的所有顶点都被访问。若图中还有未访问的顶点，则另选起点继续遍历。

广度优先搜索 ​

广度优先搜索采用的思想🔖： 队列

  1. 开始时要将其置空
  2. 在每访问一个顶点时，要将其入队
  3. 在访问一个顶点的所有后继时，要将其出队。
  4. 若队列为空时，说明每个访问过的顶点的所有后继均已访问完毕，因而本次遍历可以结束。若此时还有未访问的顶点，需要另选起点进行遍历。

图的应用 ​

关于图的几个概念定义： ​

  1. 连通图： 在无向图中，若任意两个顶点 i 到顶点 j 有路径相连（当然从 j 到 i 也一定有路径）。则称该无向图为连通图。
  2. 强连通图： 在有向图中，若任意两个顶点 i 到 j 有路径相连，则称该有向图为强连通图。
  3. 连通网： 边带有权值的连通图称为连通网，权值可以表示连接两个顶点的代价。
  4. 生成树： 一个连通图的生成树是指一个连通子图，它含有图中全部 n 个顶点，但只有足以构成一棵树的 n-1 条边。一棵有 n 个顶点的生成树有且仅有 n-1 条边，如果生成树中再添加一条边，则必定成环。
  5. 最小生成树： 在连通网的所有生成树中，所有边的代价和最小的生成树，称为最小生成树。

👉应用1️⃣:生成树 ​

在图论中，常常将树定义为一个无回路的连通图

两种遍历的算法可以获得生成树：

深度优先（搜索）生成树、广度优先（搜索）生成树

在一般情况下，图中的每条边若给定了权，这时，我们所关心的不是生成树，而是生成树中边上权值之和。若生成树中每条边上权值之和达到最小，称为最小生成树。

👉应用2️⃣:最小生成树 ​

最小生成树的两种方法 ​

避圈法：

第一种最小生成树： 普里姆算法（prim）
第二种最小生成树： 克鲁斯卡尔算法（kruskal）

破圈法： 运筹学最小生成树破圈法

避圈法是： 你每次从当前可选的边中找权值最小的一条保留下来，前提是不会形成回路。

破圈法是： 逐步删除回路中权值最大的边，并保持图的连通性。算法结束： 当剩余边数等于顶点数减 1 时。

1️⃣最小生成树算法：普里姆算法（prim） ​

普里姆算法思想： 在连通无向网中任取一个顶点 k 作为起点，令 U={k}，W=V-U，其中 V 为所有顶点的集合。每次选择一端在 U、另一端在 W 的最小权值边，将该边加入生成树，并将 W 中对应的顶点移入 U。随后更新 U 到 W 中各顶点的最小连接边权，重复此过程，直到 W 为空。

undirected-graph

算法思想过程：

设置2个数据结构：

lowcost[i]: 本例数组下标从 0 开始，lowcost[i] 对应图中的顶点 i+1，记录已选顶点集合到该顶点的最小连接边权。图中边权均大于 0，因此用 0 标记该顶点已加入最小生成树（MST）。

visitInfo: 表示已经访问的节点。

  1. 以顶点 1 为起点初始化，每次加入新顶点后更新 lowcost（∞ 表示当前没有连接 U 与该顶点的边）：

下面依次列出选中的边和更新后的完整数组，与后面的过程表对应。

text
// 数组各项依次对应顶点 1、2、3、4、5、6
初始化：                   lowcost = [0, 6, 1, 5, ∞, ∞]
选边 (1,3)，加入顶点 3：    lowcost = [0, 5, 0, 5, 5, 4]
选边 (3,6)，加入顶点 6：    lowcost = [0, 5, 0, 2, 5, 0]
选边 (6,4)，加入顶点 4：    lowcost = [0, 5, 0, 0, 5, 0]
选边 (3,2)，加入顶点 2：    lowcost = [0, 0, 0, 0, 3, 0]
选边 (2,5)，加入顶点 5：    lowcost = [0, 0, 0, 0, 0, 0]

上面的图用表格表示如下：

其中（∞ 代表没有关系）

123456
1∞615∞∞
26∞5∞3∞
315∞754
45∞7∞∞2
5∞35∞∞6
6∞∞426∞

例： V={1,2,3,4,5,6}。以顶点 1 为起点，初始化 U={1}，W={2,3,4,5,6}。

实现 Prim 算法的过程：

U 表示已加入生成树的顶点集合，W 表示未加入的顶点集合。每一步选择连接 U 与 W 的最小权值边，将该边加入生成树，并将 W 中对应的顶点移入 U。

表中 U 的粗体数字表示本步新加入的顶点，∅ 表示空集。

步骤选边 / 权值U（已选）W（未选）
初始化—{1}{2, 3, 4, 5, 6}
1(1,3) / 1{1, 3}{2, 4, 5, 6}
2(3,6) / 4{1, 3, 6}{2, 4, 5}
3(6,4) / 2{1, 3, 6, 4}{2, 5}
4(3,2) / 5{1, 3, 6, 4, 2}{5}
5(2,5) / 3{1, 3, 6, 4, 2, 5}∅

最终选出 5 条边，总权值为 1+4+2+5+3=15。第 4 步也可选择同权值的边 (3,5)，随后选择 (5,2)，得到另一棵总权值同为 15 的最小生成树。

2️⃣最小生成树算法:克鲁斯卡尔算法（kruskal） ​

克鲁斯卡尔算法的基本思想是： 将图中所有边按权值递增排序，依次选取不会与已选边构成回路的边。对于含 n 个顶点的连通图，选出 n-1 条边即可。

时间复杂度：

克鲁斯卡尔算法的时间开销主要来自边的排序。设边数为 e，使用高效的并查集实现时，时间复杂度通常为 O(e log e)，适合边数较少的稀疏图。

算法步骤：

a、对图的存储结构，按照权值，从小到大排序。

b、初始化并查集，让每个顶点各自属于一个集合。

c、按权值从小到大检查各条边。若两端顶点属于同一集合，则跳过该边；否则执行步骤 d。

d、将该边加入生成树，累加权值，并合并两端顶点所在的集合。例如，下图首先选择边 (1,3)，其权值为 1。若并查集数组为 a，初始时 a[1]=1、a[3]=3，可以通过设置 a[1]=3 合并两个集合。重复上述过程，直到选出 n-1 条边。

【注】： 并查集-图的连通性

undirected-graph 克鲁斯卡尔最小生成树过程 kruskal

最后可选择 (2,3) 或 (3,5)，两条边的权值均为 5，因此最小生成树不唯一，总权值均为 15。

避圈法：

Prim 算法和 Kruskal 算法都通过逐步添加边构造最小生成树。Prim 每次选择连接已选顶点集合与未选顶点集合的最小权值边；Kruskal 则按全局边权递增的顺序，选择不会形成回路的边。 两种算法都保证添加边时不形成回路，这种构造方式称为避圈法。Prim 通过每次加入一个未选顶点避免回路，Kruskal 则可以使用并查集判断是否形成回路。

破圈法：

从完整的连通网出发，逐步删除环中的最大权值边，同时保持图的连通性。当剩下 n-1 条边时，就得到一棵最小生成树。

算法思想：

  1. 按权值从大到小检查各条边。若该边位于回路中，则删除；若删除后会使图不连通，则保留。
  2. 重复上述过程，直到剩余边数为 n-1，构造完成。

👉应用3️⃣:最短路径 ​

讨论最短路径的方法有两种： 单源点最短路径、所有顶点对的最短路径。

单源点最短路径：迪杰斯特拉（Dijkstra）算法 ​

定义： 单源点最短路径是指：给定一个出发点（单源点）和一个有向网 G=（V，E），求出源点到其它各顶点之间的最短路径。
问题： 怎样求出单源点的最短路径呢？
解答： 将源点到终点的所有路径都列出来，然后在里面选最短的一条即可。这种枚举方式可以用计算机实现，但路径较多时效率很低。
方法： 迪杰斯特拉（Dijkstra）在做了大量观察后，首先提出了按路长度递增序产生各顶点的最短路径算法，我们称之为迪杰斯特拉算法
算法思想： Dijkstra 算法适用于非负边权的图。设 V 为网中所有顶点集合，设置并逐步扩充一个集合 S，存放已求出其最短路径的顶点，则尚未确定最短路径的顶点集合 V-S：按路径长度递增的顺序逐个把 V-S 中的顶点加到 S 中，直到全部顶点的最短路径已确定，或剩余顶点均不可达。每次选择尚未确定且当前距离最小的顶点，加入 S，并更新其相邻顶点的距离。若剩余顶点的距离均为 ∞，则结束计算，它们从源点不可达。

dijkstra
终点从V0到各终点的最短路径
i=1i=2i=3i=4i=5
V1∞∞∞∞∞
V210(V0,V2)
V3∞60(V0,V2,V3)50(V0,V4,V3)
V430(V0,V4)30(V0,V4)
V5100(V0,V5)100(V0,V5)90(V0,V4,V5)60(V0,V4,V3,V5)
VKV2V4V3V5无
PathV0-V2V0-V4V0-V4-V3V0-V4-V3-V5
S{V0,V2}{V0,V2,V4}{V0,V2,V4,V3}{V0,V2,V4,V3,V5}

Dijkstra 算法采用贪心思想，按最短距离递增的顺序，逐步确定源点到各顶点的最短路径。在上图中，V0 到 V2、V4、V3、V5 的最短距离分别为 10、30、50、60，而 V1 从 V0 不可达。计算完成后，可以直接查询源点到目标顶点的最短距离。

所有顶点对之间的最短路径：Floyd 算法 ​

所有顶点对之间的最短路径是指： 对于给定的有向网 G=（V，E），要对 G 中任意对顶点有序对 V、W（V<>W）,找出 V 到 W 的最短距离和 W 到 V 的最短距离。
解决此问题有效的方法： 对于非负边权的图，可以轮流以每个顶点为源点，执行 Dijkstra 算法。也可以使用 Floyd 算法直接计算所有顶点对的最短路径，其时间复杂度为 O(n³)。

Floyd 算法思想：

用图的权值矩阵初始化距离矩阵 D，其中 D[i][j] 表示顶点 i 到 j 的当前最短距离。依次将每个顶点作为中间顶点，比较并更新距离，最终得到所有顶点对的最短距离矩阵。

Floyd-warshall算法描述：

ts
// floydWarshell
let n = 4;
let arcs = [
    [0, 3, Infinity, 7],
    [8, 0, 2, Infinity],
    [5, Infinity, 0, 1],
    [2, Infinity, Infinity, 0]
]

function floydWarshell() {
    for (let k = 0; k < n; k++) {
        for (let i = 0; i < n; i++) {
            for (let j = 0; j < n; j++) {
                arcs[i][j] = min(arcs[i][j], arcs[i][k] + arcs[k][j])
            }
        }
    }
}

function min(num1, num2) {
    return num1 < num2 ? num1 : num2;
}

floydWarshell();
floyd

上图使用另一组数据，演示 Floyd 算法逐轮更新距离矩阵和路径记录的过程。每轮选取一个顶点 k 作为中间顶点，比较 D[i][j] 与 D[i][k] + D[k][j]，若经过 k 的路径更短，则更新距离及对应的路径记录。图中依次以顶点 0、1、2、3 作为中间顶点完成更新。

👉应用4️⃣:拓扑排序 ​

通常我们把计划、施工过程、生产流程等都当成一个工程，一个大工程常常被划分成许多较小的子工程，这些子工程称为活动，这些活动完成时，整个工程也就完成了。

AOV 网介绍 ​

在这种有向图中，顶点表示活动，有向边表示活动的优先关系，这有向图叫做顶点表示活动的网络（Activity On Vertex）简称 AOV 网。
在 AOV 网中，<i,j>有向边表示 i 活动应先于 j 活动开始，即 i 活动必须完成后，j 活动才可以开始，并称 i 为 j 的直接前驱，j 为 i 的直接后继。这种前驱与后继的关系有传递性，此外，任何活动 i 不能以它自己作为自己的前驱或者后继，这叫做反自反性。从前驱和后继的传递性和反自反性来看，AOV 网中不能出现有向回路（或称有向环），对工程而言，将无法进行：对程序流程而言，将出现死循环。

拓扑排序的步骤：

  1. 在 AOV 网中选一个入度为 0 的顶点且输出
  2. 在 AOV 网中删除此顶点及该顶点发出来的所有有向边
  3. 重复 1，2 两步，直到 AOV 网中所有顶点都被输出或网中不存在入度为 0 的顶点。

👉应用5️⃣:关键路径 ​

若以带权有向图的顶点代表事件（event）或工程进展状态，用弧表示活动，弧上的权值表示完成该活动所需要的时间，则这样的带权有向图称为 AOE 网（Activity On Edge Network）

  1. 只有在某顶点所代表的事件发生后，从该顶点出发的各有向边所代表的活动才能开始。
  2. 只有在进入某点的各有向边所代表的活动都已结束，该顶点所代表的事件才能发生。

关键路径（临界路径）： 在 AOE 网络中从源点到汇点（结束顶点）的最长路径。关键路径上的活动为关键活动。

总结 ​

1：Prim是计算最小生成树的算法，比如为N个村庄修路，怎么修花销最少。

Dijkstra是计算最短路径的算法，比如从a村庄走到其他任意村庄的距离。

2：Prim 算法更新的是已选顶点集合到各未选顶点的最小连接边权；

Dijkstra 算法更新的是源点到各未确定顶点的当前最短距离；

  1. Prim在稠密图中比Kruskal优，在稀疏图中比Kruskal劣。

图的存储和遍历

最短路径问题

floyd-warshell

版权所有 © 2015 - 2026