图的基本概念

定义：

• 图G由顶点集V和边集E组成，记为G = (V, E)，其中V(G)表示图G中顶点的有限非空集；
• E(G)表示图G中顶点之间的关系（边）集合。
• 若V = {v1, v2, … , vn}，则用|V|表示图G中顶点的个数，也称图G的阶，E = {(u, v) | u∈V, v∈V}，用|E|表示图G中边的条数。
• 注意：线性表可以是空表，树可以是空树，但图不可以是空，即V一定是非空集

无向图、有向图：

无向图：

• 若E是无向边（简称$）的有限集合时，则图G为无向图。
• 边是顶点的无序对，记为(v, w)或(w, v)，因为(v, w) = (w, v)，其中v、w是顶点。可以说顶点w和顶点v互为邻接点。
• 边(v, w)依附于顶点w和v，或者说边(v, w)和顶点v、w相关联。

有向图：

• 若E是有向边（也称!）的有限集合时，则图G为有向图。
• 弧是顶点的有序对，记为<v, w>，其中v、w是顶点，v称为弧尾，w称为弧头，<v, w>称为从顶点v到顶点w的弧，也称v邻接到w，或w邻接自v。
• 注意：<v, w> ≠ <w, v>

简单图、多重图：

数据结构课程只探讨“简单图”

简单图：

• 不存在重复边
• 不存在顶点到自身的边

多重图：

• 图G中某两个结点之间的边数多于一条又允许顶点通过同一条边和自己关联，则G为多重图

顶点的度、入度、出度：

• 对于无向图：
  • 顶点v的度是指依附于该顶点的边的条数，记为TD(v)。
  • 在具有n个顶点、e条边的无向图中，无向图的全部顶点的度的和等于边数的2倍
• 对于有向图：
  • 入度是以顶点v为终点的有向边的数目，记为ID(v)；
  • 出度是以顶点v为起点的有向边的数目，记为OD(v)。
  • 顶点v的度等于其入度和出度之和，即TD(v) = ID(v) + OD(v)。

顶点-顶点的关系描述：

• 路径：顶点vp到顶点vq之间的一条路径是指顶点序列，
• 回路：第一个顶点和最后一个顶点相同的路径称为回路或环
• 简单路径：在路径序列中，顶点不重复出现的路径称为简单路径。
• 简单回路：除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路称为简单回路。
• 路径长度：路径上边的数目
• 点到点的距离：从顶点u出发到顶点v的最短路径若存在，则此路径的长度称为从u到v的距离。若从u到v根本不存在路径，则记该距离为无穷（∞）。
• 无向图中，若从顶点v到顶点w有路径存在，则称v和w是连通的
• 有向图中，若从顶点v到顶点w和从顶点w到顶点v之间都有路径，则称这两个顶点是强连通的

连通图、强连通图：

• 若图G中任意两个顶点都是连通的，则称图G为连通图，否则称为非连通图。
• 对于n个顶点的无向图G，
  • 若G是连通图，则最少有n-1条边
  • 若G是非连通图，则最多可能有条边
• 若图中任何一对顶点都是强连通的，则称此图为强连通图。
• 对于n个顶点的有向图G，
• 若G是强连通图，则最少有n条边（形成回路）

研究图的局部——子图：

• 设有两个图G = (V, E)和G¢ = (V', E')，若V¢是V的子集，且E'是E的子集，则称G'是G的子图
• 若有满足V(G') = V(G)的子图G'，则称其为G的生成子图
• 注意：并非任意挑几个点、几条边都能构成子图

连通分量：

• 无向图中的极大联通子图称为连通分量
• 子图必须连通，且包含尽可能多的顶点和边

强连通分量：

• 有向图中的极大强联通子图成为有向图的强连通分量
• 子图必须强连通，同时保留尽可能多的边

生成树：

• 连通图的生成树是包含图中全部顶点的一个极小连通子图
• 边尽可能的少，但要保持连通
• 若图中顶点数为n，则它的生成树含有n-1条边。对生成树而言，若砍去它的一条边，则会变成非连通图，若加上一条边则会形成一个回路。

生成森林：

在非连通图中，连通分量的生成树构成了非连通图的生成森林。

边的权、带权图/网：

• 边的权：在一个图中，每条边都可以标上具有某种含义的数值，该数值称为该边的权值。
• 带权图/网——边上带有权值的图称为带权图，也称网。
• 带权路径长度——当图是带权图时，一条路径上所有边的权值之和，称为该路径的带权路径长度

几种特殊形态的图：

• 无向完全图：无向图中任意两个顶点之间都存在边
• 有向完全图：有向图中任意两个顶点之间都存在方向相反的两条弧
• 边数很少的图称为稀疏图
• 反之称为稠密图
• 没有绝对的界限，一般来说|E| < |V|log|V|时，可以将G视为稀疏图
• 树：不存在回路，且连通的无向图
• 有向树：一个顶点的入度为0、其余顶点的入度均为1的有向图，称为有向树
  • n个顶点的树，必有n-1条边。
  • n个顶点的图，若|E|>n-1，则一定有回路

邻接矩阵法

定义：

• 无向图：
  • 第i个结点的度=第i行（或第i列）的非零元素个数
• 有向图：
  • 第i个结点的出度=第i行的非零元素个数
  • 第i个结点的入度=第i列的非零元素个数
  • 第i个结点的度=第i行、第i列的非零元素个数之和
• 邻接矩阵法求顶点的度/出度/入度的时间复杂度为O(|V|)

邻接矩阵法存储带权图（网）：

邻接矩阵法的性能分析：

• 空间复杂度：O(|V|^2) ——只和顶点数相关，和实际的边数无关
• 适合用于存储稠密图
• 无向图的邻接矩阵是对称矩阵，可以压缩存储（只存储上三角区/下三角区）

邻接矩阵法的性质：

邻接表法

为什么要使用邻接表：

• 邻接矩阵是使用数组实现的顺序存储，空间复杂度高，不适合存储稀疏图
• 邻接表是顺序+链式存储

定义：

• 其实这和树的孩子表示法是类似的，孩子表示法：顺序存储各个结点，每个结点中保存孩子链表头指针
• 边结点的数量是2|E|，整体空间复杂度为O(|V| + 2|E|)
• 边结点的数量是|E|，整体空间复杂度为O(|V| + |E|)
• 只要确定了顶点编号，图的邻接矩阵表示方式唯一，图的邻接表表示方式并不唯一

邻接矩阵和邻接表的对比：

十字链表、邻接多重表

关系：

• 十字链表储存有向图
• 邻接多重表储存无向图

十字链表存储有向图：

• 空间复杂度：O(|V|+|E|)
• 如何找到指定顶点的所有出边？顺着绿色线路找
• 如何找到指定顶点的所有入边？顺着橙色线路找

邻接矩阵、邻接表存储无向图：

• 邻接表每条边对应两份冗余信息，删除顶点、删除边等操作时间复杂度高
• 临接矩阵空间复杂度高O(|V|2)

临接多重表储存无向图：

• 空间复杂度：O(|V|+|E|)
• 删除边、删除结点等操作很方便，只需要让各指针指向下一个对应的指向即可

总结：

图的基本操作

• Adjacent(G,x,y)：判断图G是否存在边<x, y>或(x, y)。
• Neighbors(G,x)：列出图G中与结点x邻接的边。
• InsertVertex(G,x)：在图G中插入顶点x。
• DeleteVertex(G,x)：从图G中删除顶点x。
• AddEdge(G,x,y)：若无向边(x, y)或有向边<x, y>不存在，则向图G中添加该边。
• RemoveEdge(G,x,y)：若无向边(x, y)或有向边<x, y>存在，则从图G中删除该边。
• FirstNeighbor(G,x)：求图G中顶点x的第一个邻接点，若有则返回顶点号。若x没有邻接点或图中不存在x，则返回-1。
• NextNeighbor(G,x,y)：假设图G中顶点y是顶点x的一个邻接点，返回除y之外顶点x的下一个邻接点的顶点号，若y是x的最后一个邻接点，则返回-1。
• Get_edge_value(G,x,y)：获取图G中边(x, y)或<x, y>对应的权值。
• Set_edge_value(G,x,y,v)：设置图G中边(x, y)或<x, y>对应的权值为v。
• 注意：上面的操作都只针对邻接矩阵和邻接表

图的广度优先遍历（BFS）

树和图的广度优先遍历：

• 树的广度优先遍历：通过根结点，可以找到下一层的结点2，3，4.通过234又可以找到再下一层的结点5678
  • 若树非空，则根结点入队
  • 若队列非空，队头元素出队并访问，同时将该元素的孩字依次入队
  • 重复第二步直到队列为空
• 图的广度优先遍历类似于树的广度优先遍历（层序遍历）
• 区别：
  • 树不存在“回路”，搜索相邻的结点时，不可能搜到已经访问过的结点
  • 图搜索相邻的顶点时，有可能搜到已经访问过的顶点

代码实现：

• 找到与一个顶点相邻的所有顶点
  • FirstNeighbor(G,x)：求图G中顶点x的第一个邻接点，若有则返回顶点号。若x没有邻接点或图中不存在x，则返回-1。
  • NextNeighbor(G,x,y)：假设图G中顶点y是顶点x的一个邻接点，返回除y之外顶点x的下一个邻接点的顶点号，若y是x的最后一个邻接点，则返回-1。
  • 使用上面两个基本操作
• 标记哪些顶点被访问过
  • 
  • 都初始化为false
• 需要一个辅助队列

遍历序列的可变性：

• 同一个图的邻接矩阵表示方式唯一，因此广度优先遍历序列唯一
• 同一个图邻接表表示方式不唯一，因此广度优先遍历序列不唯一

算法存在的问题和解决方案：

如果是非连通图，则无法遍历完所有结点

• 空间复杂度：最坏情况，辅助队列大小为 O(|V|)
• 邻接矩阵存储的图：
  • 访问 |V| 个顶点需要O(|V|)的时间
  • 查找每个顶点的邻接点都需要O(|V|)的时间，而总共有|V|个顶点
  • 时间复杂度= O(|V|^2)
• 邻接表存储的图：
  • 访问 |V| 个顶点需要O(|V|)的时间
  • 查找各个顶点的邻接点共需要O(|E|)的时间
  • 时间复杂度= O(|V|+|E|)

广度优先生成树：

• 广度优先生成树由广度优先遍历过程确定。
• 由于邻接表的表示方式不唯一，因此基于邻接表的广度优先生成树也不唯一
• 对非连通图的广度优先遍历，可得到广度优先生成森林

图的深度优先遍历（DFS）

树和图的深度优先遍历：

• 树的深度优先遍历（先根、后根）：
  • 从根结点出发，能往更深处走就尽量往深处走。
  • 每当访问一个结点的时候，要检查是否还有与当前结点相邻的且没有被访问过的结点，如果有的话就往下一层钻。
• 图的深度优先遍历类似于树的先根遍历。
• 图的深度优先遍历是递归实现的，广度优先办理是队列实现的

图的深度优先遍历：

算法存在的问题和解决方案：

如果是非连通图，则无法遍历完所有结点

复杂度分析：

• 空间复杂度：
  • 来自函数调用栈，最坏情况，递归深度为O(|V|)
  • 最好情况，O(1)
• 时间复杂度：
  • 时间复杂度=访问各结点所需时间+探索各条边所需时间
  • 邻接矩阵存储的图：
    • 访问 |V| 个顶点需要O(|V|)的时间
    • 查找每个顶点的邻接点都需要O(|V|)的时间，而总共有|V|个顶点
    • 时间复杂度= O(|V|^2)
  • 邻接表存储的图：
    • 访问 |V| 个顶点需要O(|V|)的时间
    • 查找各个顶点的邻接点共需要O(|E|)的时间
    • 时间复杂度= O(|V|+|E|)

深度优先序列：

• 和图的邻接表是一个原理，树中各个孩子结点在邻接表中出现的顺序是可变的
• 因此如果采用这种数据结构存储树，那么可能会有不同的遍历序列

深度优先生成树：

• 同一个图的邻接矩阵表示方式唯一，因此深度优先遍历序列唯一，深度优先生成树也唯一
• 同一个图邻接表表示方式不唯一，因此深度优先遍历序列不唯一，深度优先生成树也不唯一
• 对无向图进行BFS/DFS遍历

图的遍历与图的连通性：

• 调用BFS/DFS函数的次数=连通分量数
• 对于连通图，只需调用1次 BFS/DFS
• 对有向图进行BFS/DFS遍历
• 调用BFS/DFS函数的次数要具体问题具体分析，若起始顶点到其他各顶点都有路径，则只需调用1次BFS/DFS 函数
• 对于强连通图，从任一结点出发都只需调用1次 BFS/DFS

最小生成树

生成树：

• 连通图的生成树是包含图中全部顶点的一个极小连通子图。
• 若图中顶点数为n，则它的生成树含有n-1条边。对生成树而言，若砍去它的一条边，则会变成非连通图，若加上一条边则会形成一个回路

最小生成树（最小代价树）：

• 对于一个带权连通无向图G = (V, E)，生成树不同，每棵树的权（即树中所有边上的权值之和）也可能不同
• 设R为G的所有生成树的集合，若T为R中边的权值之和最小的生成树，则T称为G的最小生成树（Minimum-Spanning-Tree, MST）
• 最小生成树可能有多个，但边的权值之和总是唯一且最小的
• 最小生成树的边数 = 顶点数 - 1
• 砍掉一条则不连通，增加一条边则会出现回路
• 如果一个连通图本身就是一棵树，则其最小生成树就是它本身
• 只有连通图才有生成树，非连通图只有生成森林

Prim 算法（普里姆）：

算法思想：

• 从某一个顶点开始构建生成树；
• 每次将代价最小的新顶点纳入生成树，直到所有顶点都纳入为止。
• 时间复杂度：O(|V|^2)，适合用于边稠密图

数据结构：

实现步骤：

• 从V0开始，总共需要 n-1 轮处理
• 循环遍历所有个结点，找到lowCost最低的，且还没加入树的顶点，isJoin对应结点标记为true
• 再次循环遍历，更新还没加入的各个顶点的lowCost值
• 重复上面步骤，直到所有结点都加入树，生成的树即为最小生成树

Kruskal 算法（克鲁斯卡尔）

算法思想：

• 每次选择一条权值最小的边，使这条边的两头连通（原本已经连通的就不选）
• 直到所有结点都连通
• 时间复杂度：O( |E|log2|E| )，适合用于边稀疏图

数据结构：

让各条边按照权值顺序排序

实现步骤：

• 共执行 e 轮，每轮判断两个顶点是否属于同一集合
• 检查第e条边的两个顶点是否连通（是否属于同一个集合）
• 若不联通则连起来
• 若联通则不操作
• 重复上面的步骤直到所有边都被遍历过

最短路径问题之BFS算法

介绍：

• 无权图可以视为一种特殊的带权图，只是每条边的权值都为1
• BFS一般只适用于无权图的最短路径问题

代码实现：

• d数组表示u到各个结点的最短路径
• path数组表示该结点回到u结点的最短前驱结点
• 由此生成的生成树同时也反应了起点到任意结点的距离

最短路径问题之Dijkstra算法

BFS算法的局限性：

• 带权路径长度——当图是带权图时，一条路径上所有边的权值之和，称为该路径的带权路径长度
• BFS算法求单源最短路径只适用于无权图，或所有边的权值都相同的图

算法思想：

• 初始：从V0开始，初始化三个数组信息
• 循环遍历所有结点，找到还没确定最短路径，且dist 最小的顶点Vi，令final[i]=ture。
• 检查所有邻接自 Vi 的顶点，若其 final 值为false，则更新 dist 和 path 信息
• 重复上述步骤，知道所有结点的final都标记为true

代码实现思路：

• 初始：
  • 若从V0开始，令 final[0]=ture; dist[0]=0; path[0]=-1。
• n-1轮处理
  • 循环遍历所有顶点，找到还没确定最短路径，且dist 最小的顶点Vi，令final[i]=ture。
  • 并检查所有邻接自Vi 的顶点，对于邻接自Vi 的顶点 Vj ，若 final[j]==false 且 dist[i]+arcsi < dist[j]，则令 dist[j]=dist[i]+arcsi; path[j]=i。
  • 注：arcsi表示Vi 到Vj 的弧的权值
• 时间复杂度：O(n2)即O(|V|2)

用于负权值带权图：

Dijkstra 算法不适用于有负权值的带权图

最短路径问题之Floyd算法

算法思想：

• Floyd算法：求出每一对顶点之间的最短路径
• 使用动态规划思想，将问题的求解分为多个阶段
• 对于n个顶点的图G，求任意一对顶点 Vi —> Vj 之间的最短路径可分为如下几个阶段：
  • 初始：不允许在其他顶点中转，最短路径是？
  • 0：若允许在 V0 中转，最短路径是？
  • 1：若允许在 V0、V1 中转，最短路径是？
  • 2：若允许在 V0、V1、V2 中转，最短路径是？
  • …
  • n-1：若允许在 V0、V1、V2 …… Vn-1 中转，最短路径是？

实现步骤：

代码实现：

注意点：

• Floyd算法可以用于负权图
• Floyd 算法不能解决带有“负权回路”的图（有负权值的边组成回路），这种图有可能没有最短路径（每走一圈路径越小）

总结：

有向无环图（DAG图）的描述表达式

定义：

若一个有向图中不存在环，则称为有向无环图，简称DAG图（Directed Acyclic Graph）

例子：

转换前：

转换后：

解题方法：

• 把各个操作数不重复地排成一排
• 标出各个运算符的生效顺序（先后顺序有点出入无所谓）
• 按顺序加入运算符，注意“分层”
• 从底向上逐层检查同层的运算符是否可以合体

拓扑排序

AOV网：

• AOV网(Activity On Vertex NetWork，用顶点表示活动的网)
• 用DAG图（有向无环图）表示一个工程。顶点表示活动，有向边<Vi, Vj>表示活动Vi必须先于活动Vj进行

拓扑排序：

• 拓扑排序：在图论中，由一个有向无环图的顶点组成的序列，当且仅当满足下列条件时，称为该图的一个拓扑排序：
  • 每个顶点出现且只出现一次。
  • 若顶点A在序列中排在顶点B的前面，则在图中不存在从顶点B到顶点A的路径。
• 或定义为：
  • 拓扑排序是对有向无环图的顶点的一种排序，它使得若存在一条从顶点A到顶点B的路径，则在排序中顶点B出现在顶点A的后面。
• 每个AOV网都有一个或多个拓扑排序序列。
• 简单来说拓扑排序就是找到做事的先后顺序
• 拓扑排序的实现：
  • 从AOV网中选择一个没有前驱（入度为0）的顶点并输出。
  • 从网中删除该顶点和所有以它为起点的有向边。
  • 重复前面的步骤直到当前的AOV网为空或当前网中不存在无前驱的顶点为止。

代码实现：

• 时间复杂度：O(|V|+|E|)
• 若采用邻接矩阵，则需O(|V|^2)

逆拓扑排序：

• 对一个AOV网，如果采用下列步骤进行排序，则称之为逆拓扑排序：
  • 从AOV网中选择一个没有后继（出度为0）的顶点并输出。
  • 从网中删除该顶点和所有以它为终点的有向边。
  • 重复上面步骤直到当前的AOV网为空。
• 用邻接表实现会更简单一些
• 使用逆邻接表：邻接表的顶点对应储存的信息是指向该顶点的边的信息
• 使用深度优先算法实现逆拓扑排序，顶点输出的序列就是逆拓扑排序序列

• DFS实现逆拓扑排序：在顶点退栈前输出

关键路径

AOE网：

• 在带权有向图中，以顶点表示事件，以有向边表示活动，以边上的权值表示完成该活动的开销（如完成活动所需的时间）
• 称之为用边表示活动的网络，简称AOE网 (Activity On Edge NetWork)
• AOE网具有以下两个性质：
  • 只有在某顶点所代表的事件发生后，从该顶点出发的各有向边所代表的活动才能开始；
  • 只有在进入某顶点的各有向边所代表的活动都已结束时，该顶点所代表的事件才能发生。
  • 另外，有些活动是可以并行进行的

关键路径：

• 从源点到汇点的有向路径可能有多条，所有路径中，具有最大路径长度的路径称为关键路径，而把关键路径上的活动称为关键活动
• 完成整个工程的最短时间就是关键路径的长度，若关键活动不能按时完成，则整个工程的完成时间就会延长
• 事件vk的最早发生时间ve(k)：决定了所有从vk开始的活动能够开工的最早时间
• 活动ai的最早开始时间e(i)：指该活动弧的起点所表示的事件的最早发生时间
• 事件vk的最迟发生时间vl(k)：它是指在不推迟整个工程完成的前提下，该事件最迟必须发生的时间。
• 活动ai的最迟开始时间l(i)：它是指该活动弧的终点所表示事件的最迟发生时间与该活动所需时间之差。
• 活动ai的时间余量d(i)=l(i)-e(i)，表示在不增加完成整个工程所需总时间的情况下，活动ai可以拖延的时间
• 若一个活动的时间余量为零，则说明该活动必须要如期完成，d(i)=0即l(i) = e(i)的活动ai是关键活动，
• 由关键活动组成的路径就是关键路径

求关键路径的步骤：

• 求所有事件的最早发生时间 ve( )
  • 按拓扑排序序列，依次求各个顶点的 ve(k):
  • ve(源点) = 0
  • ve(k) = Max{ve(j) + Weight(vj, vk)}, vj为vk 的任意前驱
• 求所有事件的最迟发生时间 vl( )
  • 按逆拓扑排序序列，依次求各个顶点的 vl(k):
  • vl(汇点) = ve(汇点)
  • vl(k) = Min{vl(j) - Weight(vk, vj)} , vj为vk的任意后继
• 求所有活动的最早发生时间 e( )
  • 若边<vk, vj>表示活动ai，则有e(i) = ve(k)
• 求所有活动的最迟发生时间 l( )
  • 若边<vk, vj>表示活动ai，则有l(i) = vl(j) - Weight(vk, vj)
• 求所有活动的时间余量 d( )
  • d(i) = l(i) - e(i)
• d(i)=0的活动就是关键活动, 由关键活动可得关键路径

关键活动、关键路径的特性：

• 若关键活动耗时增加，则整个工程的工期将增长
• 缩短关键活动的时间，可以缩短整个工程的工期
• 当缩短到一定程度时，关键活动可能会变成非关键活动
• 可能有多条关键路径，只提高一条关键路径上的关键活动速度并不能缩短整个工程的工期，只有加快那些包括在所有关键路径上的关键活动才能达到缩短工期的目的。

笔记完整PDF

百度网盘提取码：l3ja