type
Post
status
Published
password
date
Feb 18, 2025
slug
summary
category
数据结构
URL
tags
图
icon
图
图（Graph）是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：，其中， 表示一个图， 是图 中顶点的集合， 是图 中边的集合。
注意：当线性表没有数据节点时，线性表为空表；树中没有节点时，树为空树；图可以没有边，但是在图中不允许没有顶点。
ㅤ | 邻接矩阵时间复杂度 | 邻接链表时间复杂度 | 空间复杂度 |
深度优先遍历(DFS) | |||
广度优先遍历(BFS) | |||
拓扑排序(入度 or DFS) | |||
二分图检测 | |||
环的检测 | ㅤ | ||
Dijkstra | 采用二叉堆或者斐波纳契堆 | ㅤ | |
Bellman-Ford |
因为邻接矩阵遍历边 | ㅤ | |
SPFA |
因为邻接矩阵遍历边 | ㅤ | |
Floyd | 需要将链表的边权重转移到矩阵 中 | ||
Kosaraju | ㅤ | ||
Tarjan | ㅤ |
有向图与无向图
- 无向边：若顶点 x 和 y 之间的边没有方向，则称该边为无向边(x,y)，(x,y) 与 (y,x) 意义相同，表示 x 和 y 之间有连接。
- 有向边：若顶点 x 和 y 之间的边有方向，则称该边为有向边，与表示的意义是不同的，表示从 x 连接到 y ，x 称为尾，y 称为头。表示从 y 连接到 x ，y 称为尾， x 称为头。
顶点与顶点的度
上述有向图中， 顶点的度为 3，其中出度为 2，入度为 1。
图分类
完全图
完全图：每个顶点都与其他顶点相邻接的图。
- 无向完全图：在无向图中，如果任意两个顶点之间都存在边，则称该图为无向完全图。（含有n个顶点的无向完全图有 条边）
- 有向完全图：在有向图中，如果任意两个顶点之间都存在方向互为相反的两条边，则称该图为有向完全图。（含有 n 个顶点的有向完全图有 条边）
连通图
无向图
在无向图G中，如果从顶点 到顶点 有路径，则称 和 是连通的，如果对于图中任意两个顶点 和 都是连通的，则称G是连通图(ConnectedGraph)。下图左侧是非连通图，右侧是连通图：
有向图
强连通
在有向图 中，如果从顶点 可以到达顶点 ，从顶点 可以到达顶点 ，则称 和 是连通的。如果再有向图中任意两个顶点 和 都是强连通的，则称 是强连通图(ConnectedGraph)。下图左侧是非强连通图，右侧是强连通图：
弱连通
把有向图 看作无向图，如果从顶点 到顶点 有路径，则称 和 是弱连通的，如果对于图中任意两个顶点 和 都是弱连通的，则称G是弱连通图(ConnectedGraph)。下图左侧是非弱连通图，右侧是弱连通图：
异质图
二分图
指标
度
存储
邻接矩阵
图的邻接矩阵（Adjacency Matrix）存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息，一个二维数组（称为邻接矩阵）存储图中的边或弧的信息。
数据结构
C++
创建图
C++
优缺点
- 邻接矩阵的优点：数组存储方式容易实现图的操作。例如：求某顶点的度、判断顶点之间是否有边（弧）、找顶点的邻接点等等。
- 邻接矩阵的缺点：采用数组存储方式，图若有 个顶点则需要 个单元存储边(弧)，空间存储效率为。 当顶点数目较多，边数目较少时，此时图为稀疏图，这时尤其浪费空间。
邻接链表
邻接矩阵对于边数相对顶点较少的图，存在对存储空间的极大浪费的现象。因此这种存储方式对于稀疏图来说不是很合适。借鉴于线性表的解决方案，可以考虑对边或弧使用链式存储的方式来避免空间浪费的问题。
- 顶点表：图中顶点用一个一维数组存储，当然，顶点也可以用单链表来存储，不过数组可以较容易地读取顶点信息，更加方便。另外，对于顶点数组中，每个数据元素还需要存储指向第一个邻接点的指针，以便于查找该顶点的边信息。
- 边表：图中每个顶点 的所有邻接点构成一个线性表，由于邻接点的个数不定，所以用单链表存储，无向图称为顶点 的边表，有向图则称为顶点 作为弧尾的出边表。
数据结构
C++
创建图
十字链表
那么对于有向图来说，邻接表是有缺陷的。关心了出度问题，想了解入度就必须要遍历整个图才能知道，反之，逆邻接表解决了入度却不了解出度的情况。那我们思考了：有没有可能把邻接表和逆邻接表结合起来呢？
数据结构
其中
tailvex 是指弧起点在顶点表的下标，headvex 是指弧终点在顶点表中的下标，headlink 是指针域(入)，指向终点相同的下一条边，taillink 是指针域(出)，指向起点相同的下一条边。如果是网，还可以再增加一个weight 域来存储权值。邻接多重表
如果在无向图的应用中，关注的重点是顶点，那么邻接链表是不错的选择，但如果更关注边的操作，比如对已访问过的边做标记，删除某一条边等操作，却是比较繁琐的。如下图所示，图中黄色标记的结点表示A-D之间的边，在邻接表中一条边需要两个结点表示。因此如果对于边的操作（标记或者删除）则需要访问两条链表。
因此可以仿照十字链表的方式，对边表结点的结构进行一些改造。
数据结构
其中
Data 是顶点的值，Ivex 和 Jvex 是与某条边依附的两个顶点在顶点表中的下标；ilink 指向依附顶点 Ivex 的下一条边，jlink 指向依附顶点 Jvex 的下一条边。这就是邻接多重表结构。图的遍历
深度优先DFS
深度优化遍历( Depth First Search )，也有称为 深度优化搜索 ，简称为 DFS 。事实上，我们在树的遍历中早已涉及DFS，层序遍历、中序遍历和后序遍历都属于深度优先遍历的方式，因为这些遍历方式本质上都归结于栈。他的基本思想是，从顶点开始，沿着一条路一直走到底，如果发现不能到达目标解，那就返回到上一个节点，然后从另一条路开始走到底，深度优先算法的搜索过程如下图所示：
递归版
邻接矩阵
邻接矩阵的有向图与无向图的深度遍历的代码是一致的。
邻接链表
邻接链表的有向图与无向图的深度遍历的代码是一致的。
非递归版
邻接矩阵-使用栈
邻接链表
广度优先BFS
非递归版-使用队列
邻接矩阵
邻接矩阵的有向图与无向图的广度遍历的代码是一致的。
邻接链表
邻接链表的有向图与无向图的广度遍历的代码是一致的。
图的检测
785.二分图的检测（一般指无向图）
二分图定义
二分图(中文翻译问题,有时也称作二部图)，是图论中的一种特殊模型。 如果图可以分为两部分: 绿色和蓝色,并且每一条连线都连接着一个绿色顶点和一个蓝色定点,则称这个图为一个二分图.下图就是一个二分图：
二分图检测
首先，选择一个节点，置为蓝色(绿色也可)。再将与之连线的节点置为对立的颜色——绿色，按深度优先(广度优先也可)的逻辑，将节点依次置为对立色，如果最终结果为：每条边都连接这一个蓝色和一个绿色节点,则二分图检测成功。
环的检测
环的定义
在图论中，环（英语：cycle）是一条只有第一个和最后一个顶点重复的非空路径。
环的检测
度的判断（有向图、无向图都可以）
使用拓扑排序可以判断一个图中是否存在环，具体步骤如下：
- 求出图中所有结点的度。
- 将节点入栈，注意有向图与无向图的入栈条件不同
- 当栈不空时，弹出栈首元素，把与栈首元素相邻节点的度减一。如果相邻节点的度变为1（或者有向图的入度变为0），则将相邻结点入队。
- 循环结束时判断已经访问的结点数是否等于 n。等于 n 说明全部结点都被访问过，无环；反之，则有环。
注意：拓扑排序入度法与有向图环检测的入度法相同。这种方法只能判断是否有环，以及输出环中的元素；但是不能判断元素属于哪个环。
邻接矩阵
有向图与无向图的区别主要是有向图的入度需要为0，无向图的度需要小于等于1。
邻接链表
并查集
只需要将边进行合并，并在合并之前判断是否已经联通即可，如果合并之前已经联通说明存在环。
684. 冗余连接 - 无向图
685. 冗余连接 II - 有向图
DFS算法
使用 DFS 可以判断一个无向图和有向中是否存在环。深度优先遍历图，如果在遍历的过程中，发现某个结点有一条边指向已访问过的结点，并且这个已访问过的结点不是上一步访问的结点，则表示存在环。
但是我们不能仅仅使用一个 bool 数组来表示结点是否访问过。规定每个结点都拥有三种状态，白、灰、黑。开始时所有节点都是白色，当开始访问某个节点时该节点变为灰色，当该节点的所有邻接点都访问完，该节点颜色变为黑色。那么我们的算法则为：如果遍历的过程中发现某个节点有一条边指向颜色为灰的节点，那么存在环；如果节点没有访问过那么就进行遍历；如果访问完了，那么就不访问。
注意：对于有向图与无向图的深度遍历不同的是。无向图需要定义一个father数组，用以存储在DFS过程中顶点的父顶点(或者说是生成树上的父节点)，避免出现原路返回，或者回到前一个节点误判为有环。综上无向图的检测方法可以用于有向图，但是有向图的检测方法不可以用于无向图。
- 包含father数组的代码可以用于有向图与无向图
- 不包含father数组的代码只能用于有向图
递归版（包含了father数组）
对于有向图，为了效率可以省略father数组的算法。
邻接矩阵
邻接链表
非递归版（包含了father数组）
对于有向图，为了效率可以省略father数组的算法。
邻接矩阵
邻接链表
环的数量与输出
之前环的检测只能判断是否有环，但是不能输出环的数量与每个环中的顶点。使用DFS算法无法检测出图中的所有环，所以本节在dfs算法的基础上，依次计算不同长度、不同起点的环依次进行遍历。该算法的难度是避免出现重复的环，所以需要对每个环定一个序，或者说“标准型”。要求第一个节点是序号最小的（从而对一个环确定初始节点），第二个节点是第一个节点的相邻两个节点中序号较小的一个（从而确定搜索的方向是顺时针还是逆时针），剩下的节点按顺序依次取即可。
dfs算法并不能识别出所有的环
因为使用DFS算法无法检测出图中的所有环，所以本节在dfs算法的基础上，依次计算不同长度的环。
环数量的检测及输出
在dfs算法的基础上，依次计算不同长度、不同起点的环依次进行遍历。该算法的难度是避免出现重复的环，所以需要对每个环定一个序，或者说“标准型”。要求第一个节点是序号最小的（从而对一个环确定初始节点），第二个节点是第一个节点的相邻两个节点中序号较小的一个（从而确定搜索的方向是顺时针还是逆时针），剩下的节点按顺序依次取即可。
python（递归版）
C++递归版
邻接矩阵（有向、无向图源码相同）
邻接链表（有向、无向图源码相同）
C++非递归版
计算连通分量（一般使用DFS）
连通分量
连通分量是无向图中的一个子图，在该子图中任意两个顶点都是连通的。如下图所示：
算法 | 检测 | 计算连通分量 | 矩阵时间复杂度 | 邻接链表时间复杂度 | 空间复杂度 |
DFS | ✓ | ✓ | |||
BFS | ✓ | ✓ | |||
Warshell | ✓ | ㅤ | 需要将邻接链表转为矩阵 | ||
Union-Find | ✓ | ✓ | |||
Tarjan | ✓ | ㅤ | ㅤ | ㅤ | ㅤ |
Warshell算法（只能判断是否为连通图）
- 传递闭包：存在一个有向图，能用布尔邻接矩阵表示（1、0）。如果给定图的顶点之间存在任意长度的有向路径，则布尔矩阵值为1；否则为0。如果所有元素的布尔矩阵都为1，那么就是连通图
Warshall算法可以计算一个布尔邻接矩阵的传递闭包。可以在常数时间内判断是否可以从第i个顶点到达第j个顶点。Warshell的基本思想是：如果存在 ，则 。
并查集计算连通分量
对连通图的检测可以使用Union-Find算法，Union-Find算法复杂度。
邻接矩阵
邻接表
DFS计算连通分量
广度优先搜索或深度优先搜索都可以计算图的连通分量。无论哪种搜索，都从某个特定顶点 开始搜索，将与顶点 相连的所有顶点便是一个连通分量。循环遍历未访问的其他顶点，可以依次得到连通分量。
递归法
非递归法
BFS计算连通分量
广度优先搜索或深度优先搜索都可以计算图的连通分量。无论哪种搜索，都从某个特定顶点 开始搜索，将与顶点 相连的所有顶点便是一个连通分量。循环遍历未访问的其他顶点，可以依次得到连通分量。
非递归法
强连通分量
强连通分量是有向图中的一个子图，在该子图中，所有的节点都可以沿着某条路径访问其他节点。
Kosaraju
算法原理
显然上图中有两个强连通分量，即强连通分量A和强连通分量B，分别由顶点A0-A1-A2和顶点B3-B4-B5构成。
我们现在试想能否按照无向图中求连通分量的思路求解有向图的强连通分量。我们假设，DFS从强连通分量B的任意一个顶点开始，那么恰好遍历整个图需要2次DFS，和连通分量的数量相等，而且每次DFS遍历的顶点恰好属于同一个连通分量。但是，我们若从连通分量A中任意一个顶点开始DFS，我们只需要一次DFS就访问了所有的顶点，此时就不能得到正确的结果。所以，我们应该按照特定的顺序进行DFS，需要保证被指向的强连通分量的至少一个顶点排在指向这个连通分量的所有顶点前面即可，比如B3、A0、A1、A2、B4、B5。 B3排在了强连通分量A所有顶点的前面。
现在我们的关键问题就是如何得到这样一个满足要求的顶点顺序，Kosaraju给出了这解决办法：对原图取反，然后从反向图的任意节点开始进行DFS的逆后序遍历，逆后序得到的顺序一定满足我们的要求。
算法流程
- 对原图取反，从任意一个顶点开始对反向图进行逆后续DFS遍历。逆后续遍历，实际上就是首先进行DFS后续遍历，然后对后续遍历进行取反
- 按照逆后续遍历栈中的顶点出栈顺序，对原图进行DFS遍历，一次DFS遍历中访问的所有顶点都属于同一强连通分量。
python版本
邻接矩阵
邻接链表
Tarjan算法
Tarjan不仅用于计算强连通分量问题，同时还用于计算割点与割边问题。
算法流程
割点与割边
- 割边：在无向连通图中，删除了连通图的某条边后，图不再连通。这样的边被称为割边，也叫做桥。
- 割点：在无向连通图中，删除了连通图的某个点以及与这个点相连的边后，图不再连通。这样的点被称为割点。
割点与桥（割边）的关系：1）有割点不一定有桥,有桥一定存在割点；2）桥一定是割点依附的边。如下图所示，顶点C为割点，但和C相连的边都不是桥。
割点和割边作为无向图中不可或缺的属性，自然也有很重要的意义。比如在设计交通道路网的时候，设计者必须考虑问题就是如何尽量减少道路图中割点或割边的个数，因为如果存在割点或割边，此处的交通压力自然非常大，显然是设计的时候需要规避的。
DFS、BFS检测方法
对于无向图 G(V,E)，根据定义，如果要求解割点则需要三步：
- DFS或BFS跑一遍图，记录下 的连通分量为 。
- 枚举所有顶点 （边 ） 并删除，再用BFS跑一边删除顶点后的子图，求出子图的连通分量 。
- 比较 和 ，如果 则说明 是割点（ 是割边）反之不是。
Tarjan算法
Tarjan 算法是图论中非常实用的算法之一，能解决强连通分量，双连通分量，割点和桥，求最近公共祖先（LCA）等问题。
算法流程
在具体实现Tarjan算法上，我们需要在DFS（深度优先遍历）中，额外定义三个数组dfn[]，low[]，parent[]
- dfn数组：dfn数组的下标表示顶点的编号，数组中的值表示该顶点在DFS中的遍历顺序(或者说时间戳)，每访问到一个未访问过的顶点，访问顺序的值（时间戳）就增加1。子顶点的dfn值一定比父顶点的dfn值大（但不一定恰好大1，比如父顶点有两个及两个以上分支的情况）。
- low数组：low数组的下标表示顶点的编号，数组中的值表示DFS中该顶点不通过父顶点能访问到的祖先顶点中最小的顺序值（或者说时间戳）。每个顶点初始的low值和dfn值应该一样，在DFS中，我们根据情况不断更新low的值。如果 是 的父节点
low(i)=min(low(i),low(j))；如果 还在栈中 (还在搜索中，此时low(j)的值还没有确定，只能使用dfn(j))low(i)=min(low(i),dfn(j))
- parent数组：parent数组下标表示顶点的编号，数组中的值表示该顶点的父顶点编号，它主要用于更新low值的时候排除父顶点，当然也可以其它的办法实现相同的功能。
割点与割边
假设DFS中我们从顶点U访问到了顶点V（此时顶点V还未被访问过），那么我们称顶点U为顶点V的父顶点，V为U的孩子顶点。在顶点U之前被访问过的顶点，我们就称之为U的祖先顶点。
割点的判断
- 对于连通区域1：对于顶点D而言，D的孩子顶点可以通过连通区域1红色的边回到D的祖先顶点C（此时C已被访问过），所以此时D不是割点。
- 对于连通区域2：连通区域2中的顶点，必须通过D才能访问到D的祖先顶点，所以说此时D为割点。
- 对于根节点A：对于图1中的根节点A只有1个孩子节点，所以不是割点；对于图2的根节点A有2个孩子节点，所以是割点。
割边的判断
- 桥（割边）：low[v] > dfn[u] 就说明V-U是桥。子节点的
low[v]大于父节点dfn[u]
邻接矩阵
邻接链表
强连通图
dfn[6]=low[6]=4：返回，点6是一个强连通图。
dfn[5]=low[5]=3：返回，点5是一个强连通图。
- 接着遍历结点4，其
dfn[4]=5、low[4]=1，dfn[2]=6、low[2]=5。所以依次退出栈2、3、4、1
邻接矩阵
邻接链表
拓扑排序
如果一个有向图的任意顶点都无法通过一些有向边回到自身，那么称这个有向图为有向无环图。拓扑排序（Topological Sorting）是一个有向无环图（DAG, Directed Acyclic Graph）的所有顶点的线性序列。且该序列必须满足下面两个条件：
- 每个顶点出现且只出现一次。
- 若存在一条从顶点 A 到顶点 B 的路径，那么在序列中顶点 A 出现在顶点 B 的前面。
拓扑排序的输出序列是不唯一的，如下图所示，其有向无环图的一个拓扑序列可以是：0,1,2,3,4,6,5,7，也可以是：0,1,2,4,6,3,5,7。
注：有向无环图（DAG）才有拓扑排序，非DAG图没有拓扑排序一说。
入度表法
- 从图中选择一个入度为0的顶点，输出该顶点。
- 从图中删除该节点及其所有出边（即与之邻接的所有顶点入度-1）
- 反复执行这两个步骤，直至所有节点都输出，即整个拓扑排序完成；或者直至剩下的图中再没有入度为0的节点，这就说明此图中有回路，不可能进行拓扑排序。
邻接矩阵-有向无环图
邻接链表-有向无环图
DFS方法
假设我们当前搜索到了节点 ，如果它的所有相邻节点都已经搜索完成，那么这些节点都已经在栈中了，此时我们就可以把 入栈。可以发现，如果我们从栈顶往栈底的顺序看，由于 处于栈顶的位置，那么 出现在所有 的相邻节点的前面。因此对于 这个节点而言，它是满足拓扑排序的要求的。
算法流程
对于图中的任意一个节点，它在搜索的过程中有三种状态，即：
- 未搜索：我们还没有搜索到这个节点；嗯，嗯，这两个方面，他说，那咱们这边不是每天都有的
- 搜索中：我们搜索过这个节点，但还没有回溯到该节点，即该节点还没有入栈，还有相邻的节点没有搜索完成）；
- 已完成：我们搜索过并且回溯过这个节点，即该节点已经入栈，并且所有该节点的相邻节点都出现在栈的更底部的位置，满足拓扑排序的要求。
通过上述的三种状态，我们就可以给出使用深度优先搜索得到拓扑排序的算法流程，在每一轮的搜索搜索开始时，我们任取一个「未搜索」的节点开始进行深度优先搜索。我们将当前搜索的节点 标记为「搜索中」，遍历该节点的每一个相邻节点 ：
- 如果 为「未搜索」，那么我们开始搜索 ，待搜索完成回溯到 ；
- 如果 为「搜索中」，那么我们就找到了图中的一个环，因此是不存在拓扑排序的；
- 如果 为「已完成」，那么说明 已经在栈中了，而 还不在栈中，因此 无论何时入栈都不会影响到 之前的拓扑关系，以及不用进行任何操作。
当 的所有相邻节点都为「已完成」时，我们将 放入栈中，并将其标记为「已完成」。
在整个深度优先搜索的过程结束后，如果我们没有找到图中的环，那么栈中存储这所有的 个节点，从栈顶到栈底的顺序即为一种拓扑排序。下面的幻灯片给出了深度优先搜索的可视化流程。图中的「白色」「黄色」「绿色」节点分别表示「未搜索」「搜索中」「已完成」的状态。
递归版
邻接矩阵
邻接链表
非递归版
邻接矩阵
邻接链表
AOE关键路径
问题场景
前面我们说过的拓扑排序主要是为解决一个工程能否顺序进行的问题，但有时我们还需要解决工程完成需要的最长时间问题。关键路径指：最长的路径
- AOV网（Activity On Vertex NetWork）用顶点表示活动，边表示活动（顶点）发生的先后关系。AOV网的边不设权值，若存在边<a,b>则表示活动a必须发生在活动b之前。
- AOE网（Activity On edge Network) 用顶点表示事件，用有向边表示活动，用边上的权值表示活动的持续时间。由于一个工程，总有一个开始，一个结束，在正常情况下，AOE网只有一个源点（入度为 0 的点）和一个汇点（出度为 0 ）。
因为所有部件可以同时建造，所以只要最长时间的「发动机」不建造完毕集中部件就无法进行。所以：
开始 -> 发动机完成 -> 部件集中完成 -> 组装完成 就是最长权重（关键路径），组装完成最短用时 6 。缩短关键路径上的时间就能缩短最短时间，但是缩短的同时关键路径会动态发生变化，比如发动机建造时间 <= 2 ，继续缩短发动机建造时间就没用了。解决方法
：对于 AOE 网中的任意一个顶点来说，从源点到该点的最长路径代表着该顶点的最早发生时间。
例如，图 1 中从 V1 到 V5 有两条路径，V1 作为源点开始后，a1 和 a2 同时开始活动，但由于 a1 和 a2 活动的时间长度不同，最终 V1->V3->V5 的这条路径率先完成。但是并不是说 V5 之后的活动就可以开始，而是需要等待 V1->V2->V5 这条路径也完成之后才能开始。所以对于 V5 来讲，。
：表示在不推迟整个工期的前提下，事件 允许的最晚发生时间。
例如，图 1 中，在得知整个工期完成的时间是 18 天的前提下，V7 最晚要在第 16 天的时候开始，因为 a10 活动至少需要 2 天时间才能完成，如果在 V7 事件在推迟，就会拖延整个工期。所以，对于 V7 来说，它的 。
：表示活动 ai 的最早开始时间，如果活动 ai 是由弧 <Vk,Vj> 表示的，那么活动 ai 的最早开始的时间就等于时间 Vk 的最早发生时间，也就是说：。
e(i)很好理解，拿图 1 中 a4 来说，如果 a4 想要开始活动，那么首先前提就是 V2 事件开始。所以 。
：表示活动 ai 的最晚开始时间，如果活动 ai 是由弧 <Vk,Vj> 表示，ai 的最晚开始时间的设定要保证 Vj 的最晚发生时间不拖后。所以，。
在得知以上四种统计数据后，就可以直接求得 AOE 网中关键路径上的所有的关键活动，方法是：**对于所有的边来说，如果它的最早开始时间等于最晚开始时间，称这条边所代表的活动为关键活动。**由关键活动构成的路径为关键路径。
ㅤ | V1 | V2 | V3 | V4 | V5 | V6 | V7 | V8 | V9 |
0 | 6 | 4 | 5 | 7 | 7 | 16 | 14 | 18 | |
0 | 6 | 6 | 8 | 7 | 10 | 16 | 14 | 18 |
ㅤ | a1 | a2 | a3 | a4 | a5 | a6 | a7 | a8 | a9 | a10 | a11 |
0 | 0 | 0 | 6 | 4 | 5 | 7 | 7 | 7 | 16 | 14 | |
0 | 2 | 3 | 6 | 6 | 8 | 7 | 7 | 10 | 16 | 14 | |
0 | -2 | -3 | 0 | -2 | -3 | 0 | 0 | -3 | 0 | 0 |
通过 ，其中 的值都各自相同，所以，在图 1 中的 AOE 网中有两条关键路径：
邻接矩阵
邻接链表
在计算最晚发生时间的时候，需要不断计算父节点的位置。
最短路径(加权)
Dijkstra(不能有负权边，所以有向图与无向图一样)
Dijkstra算法使用了广度优先搜索解决赋权有向图或者无向图的单源最短路径问题，要求图中不存在负权边，即保证图中每条边的权重值为正。Dijkstra算法采用的是一种贪心的策略，声明一个数组
dis来保存源点到各个顶点的最短距离和一个保存已经找到了最短路径的顶点的集合：T。- 初始时，原点
s的路径权重被赋为0（dis[s] = 0）。若对于顶点s存在能直接到达的边(s,m)，则把dis[m]设为w（s, m）,同时把所有其他（s不能直接到达的）顶点的路径长度设为无穷大。初始时，集合T只有顶点s。
- 其次，从
dis数组选择最小值，则该值就是源点s到该值对应的顶点的最短路径，并且把该点加入到T中，OK，此时完成一个顶点，
- 然后，我们需要看看新加入的顶点是否可以到达其他顶点并且看看通过该顶点到达其他点的路径长度是否比源点直接到达短，如果是，那么就替换这些顶点在
dis中的值。
- 重复步骤2和步骤3，从
dis中找出最小值，并更新数组dis；直到T中包含了图的所有顶点。
邻接矩阵
邻接链表
Bellman-Ford（可以有负权边，但不能存在负环路。所以是有向图，因为如果是无向图，一旦图中存在负权边就相当于存在负权环）
Bellman-Ford算法是从Dijkstra算法引申出来的，它可以解决带有负权边的最短路径问题，但是要求图不能存在负环路；所以Bellman-Ford算法主要针对有向图，因为如果是无向图，一旦图中存在负权边，就相当于存在负权环，而如果图中没有负权边，就可以直接使用 Dijkstra 算法，效率更高。
值得注意的是，Dijkstra算法和下面的Floyd算法是基于邻接矩阵的，而Bellman-Ford算法是基于邻接表。Bellman-Ford既不是广度遍历又不是深度遍历，Bellman-Ford需要遍历每一条边。具体Bellman-Ford的算法流程如下所示：
从源点s到任意一点p的最短路径的长度 dist，初始化数组 dist[s] 为0，其余为无穷大。以下操作循环执行至v-1次， v为顶点数： 对于每一条边edge(u,v)，如果dist[u] + weight(u,v) < dist[v]，则令dist[v] = dist[u] + weight(u,v)。若上述操作没有对dist进行更新，说明最短路径已经查找完毕，或者部分点不可达，跳出循环。否则执行下次循环；检测图中是否存在负环路，即权值之和小于0的环路。待上述循环结束之后，在进行一次遍历，即可判断路径中是否有负环路。具体而言，对于每一条边edge(u,v)，如果存在dist[u] + weight(u,v) < dist[v]的边，则图中存在负环路，即是说该图无法求出单源最短路径。否则数组dist[n]中记录的就是源点s到各顶点的最短路径长度。注意：Bellman-Ford要求图不能存在负环路。所以在第二步遍历完成之后，在进行一次遍历，如果路径缩短则说明图中存在负环路。
邻接矩阵
邻接链表
SPFA算法（Bellman-ford的队列优化，针对有向图）
SPFA(Shortest Path Faster Algorithm)算法是求单源最短路径的一种算法，它是Bellman-ford的队列优化，针对有向图，因为如果是无向图，一旦图中存在负权边，就相当于存在负权环，而如果图中没有负权边，就可以直接使用 Dijkstra 算法，效率更高。。
算法流程
- 初始化：选取顶点
s为源点，令dis[s]=0 ，其余赋值为INF。并将源点入队列。
- 读取队列头的顶点，并将头顶点
s出队列，将与s邻接的所有顶点进行松弛操作，若顶点p没有在队列中且成功的进行了松弛操作，则将邻接顶点p入队列。如果已经在队列中，则不再入队。
- 队列为空时，单源最短路径查找完毕（求最短路径至多进行 次松弛操作，所以当顶点p的循环次数顶点数目n的时候，最短路径查找完毕，此时存在负权环）。
邻接矩阵
邻接链表
Floyd（可以正确处理权值有向图和无向图。也可以用于负权有向图（但不可存在负权回路)的最短路径问题与SPFA的区别是Floyd解决多任意两点的最短路径问题）
Floyd算法是解决任意两点间的最短路径的一种算法，可以正确处理权值有向图和无向图。也可以用于负权有向图（但不可存在负权回路)的最短路径问题。其算法的时间复杂度为 ，空间复杂度 。
Floyd的核心思想是：从任意节点 到任意节点 的最短路径不外乎2种可能。1、是直接从 到 ；2、是从 经过若干个节点 到 。所以，我们假设 为节点 到节点 的最短路径的距离，对于每一个节点 ，我们检查 是否成立，如果成立，证明从 到 再到 的路径比 直接到 的路径短，我们便设置 ，这样一来，当我们遍历完所有节点 ， 中记录的便是 到 的最短路径的距离。
注意：我们可以通过计算用 O(V) 次 Dijkstra 算法计算任意两点间的最短路径。但是 Dijkstra 算法不能计算含有负边的图。
算法流程
通过Floyd计算图G=(V,E)中各个顶点的最短路径时，需要引入两个矩阵，矩阵 中的元素 表示顶点 到顶点 的距离。矩阵 中的元素 ，表示顶点 到顶点 经过了 记录的值所表示的顶点。
- 初始化矩阵 和矩阵 。 对所有 ，，其中 为图的权值。
- 更新矩阵 和矩阵 。对中间结点 ，若 a[i][j]>a[i][k]+a[k][j] ，则令 ，同时更新 。
- 若 ，则存在一条含顶点 的负权值回路（Floyd不能处理负权值回路），算法终止；或 (顶点的数目) 算法终止；否则令 ，并转步骤2。
邻接矩阵
邻接链表
与邻接矩阵不同的地方是权重的初始化。邻接链表的初始化需要将权重转移到矩阵A；邻接矩阵的初始化只需要将权重复制到矩阵A。
树
树的检测
一个无环的连通图被称作树。一棵树必须具有以下特性：
- 是一个全连通图（所有节点相通）
- 无回路（无环）
- 图的边数=节点数-1
其中2等价于3，因此我们可以利用特性（1）（2）或者（1）（3）来判断。
最小生成树(加权)
最小生成树定义
- 连通网：在连通图中，若图的边具有一定的意义，每一条边都对应着一个数，称为权；权代表着连接连个顶点的代价，称这种连通图叫做连通网。
- 生成树：一个连通图的生成树是指一个连通子图，它含有图中全部n个顶点，但只有足以构成一棵树的n-1条边。一颗有n个顶点的生成树有且仅有n-1条边，如果生成树中再添加一条边，则必定成环。
- 最小生成树：在一个连通无向图的生成树中，所有边的代价和最小的生成树，称为最小生成树。
Kruskal算法
此算法可以称为“加边法”，初始最小生成树边数为0，每迭代一次就选择一条满足条件的最小代价边，加入到最小生成树的边集合里。
- 把图中的所有边按代价从小到大排序；
- 把图中的 个顶点看成独立的 棵树组成的森林；
- 按权值从小到大选择边，所选的边连接的两个顶点 、 应属于两颗不同的树，则成为最小生成树的一条边，并将这两颗树合并作为一颗树。
- 重复(3),直到所有顶点都在一颗树内或者有 条边为止。
邻接矩阵
邻接链表
Prim算法
此算法可以称为“加点法”，每次迭代选择代价最小的边对应的点，加入到最小生成树中。算法从某一个顶点 开始，逐渐长大覆盖整个连通网的所有顶点。
- 图的所有顶点集合为 ；初始令集合 ， ;
- 在两个集合 中能够组成的边中，选择一条代价最小的边 ，加入到最小生成树中，并把 并入到集合 中。
- 重复上述步骤，直到最小生成树有 条边或者 个顶点为止。
邻接矩阵
邻接链表
岛屿问题
使用深度遍历或者广度遍历可以计算。
旅行商
TSP(Traveling Salesman Problem)即旅行商问题：假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径长度为所有路径之中的最小值。TSP是一个典型的组合优化问题，且是一个NP完全难题，不能找到一个多项式时间复杂度的算法来求解。目前比较主流的方法是采用一些随机的、启发式的搜索算法，比如遗传算法、蚁群算法、模拟退货算法、粒子群算法等。这些算法不能求出一个最优解，但是会得到一个近似解。
问题分析
这个问题乍一看，有那么一点像“最短路径问题”，然后我们就会自然地想到用Dijkstra算法去求得“从某一个城市出发，到其他所有剩余城市的最短路径”。的确，如果是这样真的挺好，但仔细想，这个问题并非单纯这么简单，它还要求去寻找“从某个城市开始，分别经过其它城市一次且仅一次，最后再回到这个出发城市的最短巡回路径”。
对于这个问题，我们很容易想到一种类似于穷举的思路：现在假设我们要拜访11个城市，从城市1出发，最后回到城市1。显然，从城市1出来后，我们随即可以选择剩余的10个城市之一进行拜访，那么很显然这里就有10种选择，以此类推，下一次就有9种选择…总的可选路线数就是：10!。也就是说需要用for循环迭代10!次，才能找出所有的路线，进而筛选出最短的那条来。如果只拜访个10个城市或许还好的话（需要迭代3628800次），那要拜访100个城市（需要迭代 ）简直就是计算机的噩梦！更多个城市的话，计算的时间开销可想而知！ 更一般地，如果要拜访 个城市，总的可选路线数就是 ，进而时间复杂度就是 。