图

图的存储

概念与定义

图的存储

• 图的类型模版

• 邻接矩阵
• 在图的邻接矩阵表示中，有一个记录各个顶点信息的顶点表，还有一个表示各个顶点之间关系的邻接矩阵。设图 A = (V, E) 是一个有 n 个顶点的图, 图的邻接矩阵是一个二维数组 A.Edge[n][n]，定义：
• 无向图的邻接矩阵是对称的；有向图的邻接矩阵可能是不对称的。
• 在有向图中, 统计第 i 行 1 的个数可得顶点 i 的出度，统计第 j 列 1 的个数可得顶点 j 的入度。
• 在无向图中, 统计第 i 行 (列) 1 的个数可得顶点i 的度。
• 对于带权图定义为
代码

• 邻接表
• 以邻接矩阵表示图，当边数远远小于n2 的时候，大量元素是maxWeight，会造成空间浪费。
• 邻接表是邻接矩阵的改进形式。为此需要把邻接矩阵的各行分别组织为一个单链表。
• 在邻接表中，同一个顶点发出的边链接在同一个边链表中，每一个链表结点代表一条边（边结点），结点中有另一顶点的标识 dest 和指针 link。对于带权图，边结点中还要保存该边的权值cost。
• 顶点表的第 i 个顶点中保存该顶点的数据，以及它对应边链表的头指针adj。







代码

图的遍历

• 从已给的连通图中某一顶点出发，沿着一些边访遍图中所有的顶点，且使每个顶点仅被访问一次，就叫做图的遍历 (Graph Traversal)。

• 图中可能存在回路，且图的任一顶点都可能与其它顶点相通，在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点。

• 为了避免重复访问，可设置一个标志顶点是否被访问过的辅助数组 visited[]

• 辅助数组visited[ ]的初始状态为 0, 在图的遍历过程中, 一旦某一个顶点 i 被访问, 就立即让visited[i]为 1, 防止它被多次访问。

• 深度优先搜索DFS (Depth First Search)



DFS 在访问图中某一起始顶点 v 后，由 v 出发, 访问它的任一邻接顶点 w1；再从 w1 出发, 访问与 w1邻 接但还没有访问过的顶点 w2；
然后再从 w2 出发, 进行类似的访问, … 如此进行下去, 直至到达所有的邻接顶点都被访问过的顶点 u 为止。
接着, 退回一步, 退到前一次刚访问过的顶点, 看是否还有其它没有被访问的邻接顶点。如果有, 则访问此顶点, 之后再从此顶点出发, 进行与前述类似的访问; 如果没有, 就再退回一步进行搜索。重复上述过程, 直到连通图中所有顶点都被访问过为止。
• 代码

• 广度优先搜索BFS (Breadth First Search)



BFS在访问了起始顶点 v 之后，由 v 出发, 依次访问 v 的各个未被访问过的邻接顶点 w1, w2, …, wt，然后再顺序访问 w1, w2, …, wt 的所有还未被访问过的邻接顶点。
再从这些访问过的顶点出发，再访问它们的所有还未被访问过的邻接顶点，… 如此做下去，直到图中所有顶点都被访问到为止。
广度优先搜索是一种分层的搜索过程, 每向前走一步可能访问一批顶点, 不像深度优先搜索那样有往回退的情况。因此, 广度优先搜索不是一个递归的过程。
为了实现逐层访问, 算法中使用了一个队列, 以记忆正在访问的这一层和上一层的顶点, 以便于向下一层访问。
为避免重复访问, 需要一个辅助数组 visited [ ]，给被访问过的顶点加标记。

• 连通分量
• 当无向图为非连通图时，从图中某一顶点出发，利用深度优先搜索算法或广度优先搜索算法不可能遍历到图中的所有顶点，只能访问到该顶点所在极大连通子图（连通分量）的所有顶点。
• 若从无向图每一连通分量中的一个顶点出发进行遍历, 可求得无向图的所有连通分量。
• 例如，对于非连通的无向图，所有连通分量的生成树组成了非连通图的生成森林。

最小生成树

• 使用不同的遍历图的方法，可以得到不同的生成树；从不同的顶点出发，也可能得到不同的生成树。

• 按照生成树的定义，n 个顶点的连通网络的生成树有 n 个顶点、n-1条边。

• 构造最小生成树 假设有一个网络，用以表示 n 个城市之间架设通信线路，边上的权值代表架设通信线路的成本。如何架设才能使线路架设的成本达到最小？

• 构造最小生成树的准则
• 必须使用且仅使用该网络中的 n-1 条边来连接网络中的 n 个顶点；
• 不能使用产生回路的边；
• 各边上的权值的总和达到最小。

• Kruskal算法
• 设有一个有 n 个顶点的连通网络 N = { V, E }, 最初先构造一个只有 n 个顶点、没有边的非连通图 T = {V,}, 图中每个顶点自成一个连通分量。当在 E 中选到一条具有最小权值的边时, 若该边的两个顶点落在不同的连通分量上，则将此边加入到 T 中; 否则将此边舍去，重新选择一条权值最小的边。如此重复下去, 直到所有顶点在同一个连通分量上为止。

• 普里姆(Prim)算法
• 普里姆算法的基本思想：
从连通网络 N = {V, E}中的某一顶点 u0 出发, 选择与它关联的具有最小权值的边 (u0, v), 将其顶点加入到生成树顶点集合U中。
以后每一步从一个顶点在集合U中, 而另一个顶点不在集合U中的各条边中选择权值最小的边(u, v), 把它的顶点加入到集合U中。如此继续下去, 直到网络中的所有顶点都加入到生成树顶点集合U中为止。
• 代码

最短路径 (Shortest Path)

• 最短路径问题：如果从图中某一顶点（称为源点）到另一顶点（称为终点）的路径可能不止一条，如何找到一条路径使得沿此路径上各边上的权值总和达到最小。

• 问题解法
• 边上权值非负情形的单源最短路径问题 — Dijkstra算法
• 所有顶点之间的最短路径 — Floyd算法

• 边上权值非负情形的单源最短路径问题
• 问题的提法：给定一个带权有向图D与源点 v，求从v到D中其他顶点的最短路径。限定各边上的权值大于或等于0。
• 为求得这些最短路径, Dijkstra提出按路径长度的递增次序, 逐步产生最短路径的算法。首先求出长度最短的一条最短路径，再参照它求出长度次短的一条最短路径，依次类推，直到从顶点v到其它各顶点的最短路径全部求出为止。



引入辅助数组dist。它的每一个分量dist[i]表示当前找到的从源点 v0 到终点 vi 的最短路径的长度。初始状态：
• 若从v0到顶点vi有边, 则dist[i]为该边的权值；
• 若从v0到顶点vi无边, 则dist[i]为。
假设S是已求得的最短路径的终点的集合，则可证明：下一条最短路径必然是从v0 出发，中间只经过S中的顶点便可到达的那些顶点的路径中的一条。
每次求得一条最短路径后, 其终点 加入集合S，然后对所有的 ，修改其 dist[i]值。
伪代码
这个算法是 Dijkstra 算法 的一个简化伪代码形式，常用于在加权图中求解从单个源点到所有其他顶点的最短路径。以下是各步骤的详细解释：
算法目标
从图中选定一个起点 ，计算从该起点到所有其他顶点的最短路径。
伪代码解释
① 初始化
S ← {v0};
dist[j] ← Edge[0][j], j = 1, 2, …, n-1;
• S 集合：用于存储已经找到最短路径的顶点集合，初始时只包含起点 。
• dist 数组：用于记录从起点 到其他各个顶点的当前最短路径长度。
• 初始时，直接使用图的邻接矩阵 Edge 的第 0 行数据（即从起点到其他点的边权值）。
• 如果没有边连接，权值通常设为无穷大（例如 INF）。
② 求出最短路径的长度
dist[u] ← min {dist[i]}, i ∈ V - S;
S ← S ∪ {u};
• 从当前未处理的顶点集合 中，选择一个到 距离最短的顶点 。
• 这一过程找到的是“最短路径未确定的顶点中，与起点最近的顶点”。
• 将顶点 加入集合 ，表示它的最短路径已经确定。
③ 修改
dist[k] ← min {dist[k], dist[u] + Edge[u][k]}, 对于每一个 k ∈ V - S;
• 对于图中所有尚未处理的顶点 ：
• 检查是否可以通过顶点 到达 的距离更短。
• 如果 ，更新 。
• 这个步骤是关键，用于“松弛”其他顶点的距离。
④ 判断
若 S = V, 则算法结束，否则转②。
• 检查是否所有顶点的最短路径都已确定（即 ）。
• 如果还存在未处理的顶点，回到步骤 ②。

• 所有顶点之间的最短路径
• 问题的提法：已知一个各边权值均大于0的带权有向图，对每一对顶点 vi，vj，要求求出vi 与vj之间的最短路径和最短路径长度。
• Floyd算法的基本思想：
• 定义一个n阶方阵序列：.其中 ；
• 是从顶点vi 到vj , 中间顶点是v0的最短路径长度;
是从顶点vi 到vj , 中间顶点的序号不大于k的最短路径的长度;
是从顶点vi 到vj 的最短路径长度。

活动网络 (Activity Network)

• 方法
1. 输入AOV网络。令 n 为顶点个数。
2. 在AOV网络中选一个没有直接前驱的顶点, 并输出之;
3. 从图中删去该顶点, 同时删去所有它发出的有向边;
4. 重复以上1，2步, 直到
1. 全部顶点均已输出，拓扑有序序列形成，拓扑排序完成；
2. 或图中还有未输出的顶点, 但已跳出处理循环。说明图中还剩下一些顶点, 它们都有直接前驱。这时网络中必存在有向环。

• 算法
• 在邻接表中增设一个数组count[]，记录各顶点入度。入度为零的顶点即无前驱顶点。
• 在输入数据前, 顶点表NodeTable[]和入度数组count[]全部初始化。在输入数据时, 每输入一条边<j, k>, 就需要建立一个边结点, 并将它链入相应边链表中, 统计入度信息：
• 在算法中, 使用一个存放入度为零的顶点的链式栈, 供选择和输出无前驱的顶点。
• 拓扑排序算法可描述如下：
1. 建立入度为零的顶点栈
2. 当入度为零的顶点栈不空时, 重复执行：
1. 从顶点栈中退出一个顶点, 并输出之;
2. 从AOV网络中删去这个顶点和它发出的边, 边的终顶点入度减一;
3. 如果边的终顶点入度减至0, 则该顶点进入度为零的顶点栈;
3. 如果输出顶点个数少于AOV网络的顶点个数, 则报告网络中存在有向环。
• 在算法实现时, 为了建立入度为零的顶点栈,可以不另外分配存储空间, 直接利用入度为零的顶点的count[ ]数组元素。设立一个栈顶指针top, 指示当前栈顶位置, 即某一个入度为零的顶点。栈初始化时置top = -1。
• 将顶点i 进栈时执行以下指针的修改： count[i] = top; top = i ;// top指向新栈顶i, 原栈顶元素序号在count[i]中
• 退栈操作可以写成： j = top; top = count[top];//位于栈顶的顶点记于 j, top退到次栈顶

• 代码
分析此拓扑排序算法可知，如果AOV网络有n个顶点，e条边，在拓扑排序的过程中，搜索入度为零的顶点，建立链式栈所需要的时间是O(n)。在正常的情况下，有向图有n个顶点，每个顶点进一次栈，出一次栈，共输出 n 次。顶点入度减一的运算共执行了e次。所以总的时间复杂度为O(n+e)。

用边表示活动的网络(AOE网络)

• 如果在无有向环的带权有向图中, 用有向边表示一个工程中的活动 (Activity), 用边上权值表示活动持续时间 (Duration), 用顶点表示事件 (Event), 则这样的有向图叫做用边表示活动的网络, 简称 AOE ( Activity On Edges ) 网络。

• AOE网络在某些工程估算方面非常有用。例如，可以使人们了解：
• 完成整个工程至少需要多少时间(假设网络中没有环)?
• 为缩短完成工程所需的时间, 应当加快哪些活动?

• 整个工程只有一个开始点和一个完成点，开始点（即入度为零的顶点）称为源点，结束点（即出度为零的顶点）称为汇点。

• 从源点到各个顶点、以及从源点到汇点的有向路径可能不止一条。 这些路径的长度也可能不同。 完成不同路径的活动所需的时间虽然不同, 但只有各条路径上所有活动都完成了, 整个工程才算完成。

• 因此, 完成整个工程所需的时间取决于从源点到汇点的最长路径长度, 即在这条路径上所有活动的持续时间之和。这条路径长度最长的路径就叫做关键路径(Critical Path)。

• 要找出关键路径，必须找出关键活动, 即不按期完成就会影响整个工程完成的活动。

• 关键路径上的所有活动都是关键活动。因此, 只要找到了关键活动, 就可以找到关键路径。

• 定义几个与计算关键活动有关的量：
1. 事件Vi 的最早可能开始时间Ve(i) ：是从源点V0 到顶点Vi 的最长路径长度。
2. 事件Vi 的最迟允许开始时间Vl[i]： 是在保证汇点Vn-1 在Ve[n-1] 时刻完成的前提下，事件Vi 的允许的最迟开始时间。
3. 活动ak 的最早可能开始时间Ae[k]： 设活动ak 在边<Vi, Vj>上, 则Ae[k]是从源点V0到 顶点Vi 的最长路径长度。因此，Ae[k] = Ve[i]。
4. 活动ak 的最迟允许开始时间Al[k] ：Al[k]是在不会引起时间延误的前提下, 该活动允许的最迟开始时间
Al[k] = Vl[j]-dur(<i, j>)。
其中, dur(<i, j>)是完成 ak 所需的时间。
5. 时间余量 Al[k]-Ae[k] ： 表示活动ak的最早可能开始时间和最迟允许开始时间的时间余量。Al[k] == Ae[k]表示活动 ak 是没有时间余量的关键活动。
为找出关键活动, 需要求各个活动的 Ae[k] 与 Al[k]，以判别是否 Al[k] == Ae[k]。

• 为求得Ae[k]与Al[k], 需要先求得从源点V0到各个顶点Vi 的Ve[i]和Vl[i]。

• 求Ve[i]的递推公式

• 从 Ve[0] = 0 开始，向前递推:
，S2 是所有指向Vj 的有向边<Vi,Vj>的集合。

• 从Vl[n-1] = Ve[n-1]开始，反向递推
，S1是所有源自Vj 的有向边< Vj , Vk>的集合。

• 代码
🔥
注意
• 所有顶点按拓扑有序的次序编号。
• 仅计算 Ve[i] 和 Vl[i] 是不够的，还须计算 Ae[k] 和 Al[k]。
• 不是任一关键活动加速一定能使整个工程提前。想使整个工程提前，要考虑各个关键路径上所有关键活动。
• 如果任一关键活动延迟，整个工程就要延迟。