回顾：数据的逻辑结构

• 集合：数据元素间除“同属于一个和集合”外，无其他关系

• 线性结构：一个对一个，如线性表、栈、队列

• 树形结构：一个对多个，如树

• 图形结构：多个对多个

图的定义和基本术语

图的定义和术语

• 图：G=(V, E) // Grahp = (Vertex, Edge)
• V：顶点（数据元素）的有穷非空集合；
• E：边的有穷集合。

• 无向图：每条边都是无方向的

• 有向图：每条边都是有方向的

• 完全图：任意两个点都有一条边相连

• 稀疏图：有很少边或弧的图（)

• 稠密图：有很多边或弧的图

• 网：边/弧带权的图

• 邻接：有边/弧相连的两个顶点之间的关系。
1. 存在()，则称 和 互为邻接点
2. 存在，则称 邻接到 ， 邻接与

• 关联（依附）：边/弧与顶点的关系
• 存在，则称该边/弧关联于 和

• 顶点的度：与该顶点相关联的边的数目，记作TD(v)

• 在有向图中，顶点的度等于该顶点的入度和出度之和

• 顶点v的入度是以v为终点的有向边的条数，记作ID(v)

• 顶点v的入度是以v为始点的有向边的条数，记作OD(v)

• 路径：接续的边构成的顶点序列。

• 路径长度：路径上边或弧的数目/权值之和。

• 回路（环）：第一个顶点和最后一个顶点相同的路径。

• 简单路径：除路径起点和终点可以相同外，其余顶点均不相同的路径。

• 简单回路（简单环）：除路径起点和终点相同外，其余顶点均不相同的路径。

• 连通图（强连通图）：在无（有）向图 G = (V, {E}) 中，若对任何两个顶点 v、u 都存在从 v 到 u 的路径，则称 G 是连通图（强连通图）。

• 劝和网：图中边或弧所具有的相关数称为权。表明从一个顶点到另一个顶点的距离或耗费。带权的图称为网。

• 子图：设有两个图 G = (V, {E})、G1 = (V1, {E1})，若 ，，则称G1是G的子图。

• 连通分量（强连通分量）

• 极小连通子图：该子图是G的连通子图，在该子图中删除任何一条边，子图不再连通。

• 生成树：包含无向图G所有顶点的极小连通子图。

• 生成森林：对非连通图，由各个连通分量的生成树的集合。

图的类型定义

图的抽象类型定义

基本操作 P

图的存储结构

邻接矩阵

1、 数组（邻接矩阵）表示法

• 建立一个顶点表（记录各个顶点信息）和一个邻接矩阵（表示各个顶点之间关系）。

• 无向图的邻接矩阵表示法

特别：完全图的邻接矩阵中，对角元素为0，其余1。

• 有向图的邻接矩阵表示法

• 网（即有权图）的邻接矩阵表示法

• 邻接矩阵的存储表示：用两个数组分别存储顶点表和邻接矩阵

2、采用邻接矩阵表示法创建无向图

• 补充算法：在图中查找顶点

• 邻接矩阵——有什么好处？

• 邻接矩阵——有什么缺点？

1. 不便于增加和删除顶点

2. 浪费空间——存稀疏图（点很多而边很少）有大量无效元素
• 对稠密图（特别是完全图）还是很合算的

3. 浪费空间——统计稀疏图中一共有多少条边

邻接表

1、邻接表表示法（链式）

• 无向图

• 有向图

特点（邻接表）

1. 顶点 的出度为第 i 个单链表中的结点个数

2. 顶点 的入度为整个单链表中邻接点域值是 i-1 的结点个数

3. 空间复杂度为 O(n+e)

特点（逆邻接表）

1. 顶点 的入度为第 i 个单链表中的结点个数

2. 顶点 的出度为第 i -1个单链表中的结点个数

• 顶点的结点结构

• 弧（边）的结点结构

• 图的结构定义

• 邻接表操作举例说明

2、采用邻接表表示法创建无向网

• 算法思想
1. 输入总顶点数和总边数
2. 建立顶点表，依次输入点的信息存入顶点表中，使每个表头结点的指针域初始化为NULL
3. 创建邻接表，依次输入每条边依附的两个顶点，确定两个顶点的序号 i 和 j ，建立边结点，将此边结点分别插入到 和 对应的两个边链表的头部

邻接表特点

1. 方便找任一顶点的所有“邻接点”

2. 节约稀疏图的空间
• 需要N个头指针+2E个结点（每个结点至少两个域）

3. 方便计算任意顶点的“度”？
• 对无向图：是
• 对有向图：只能计算“出度”；需要构造“逆邻接表”（存指向自己的边）来方便计算“入度”

4. 不方便检查任意一对顶点间是否存在边

邻接矩阵与邻接表表示法的关系

1. 联系：邻接表中每个链表对应于临街矩阵中的一行，链表中结点个数等于一行中非零元素的个数

2. 区别
• 对应任一确定的无向图，邻接矩阵是唯一的（行列号和顶点编号一致），但邻接表不唯一（链接次序与顶点编号无关）
• 邻接矩阵空间的复杂度为 ，而邻接表的空间复杂度为

3. 用途：邻接矩阵多用于稠密图；而邻接表多用于稀疏图

十字链表

• 十字链表是有向图的另一种链式存储结构。我们也可以把它看成是将有向图的邻接表和逆邻接表结合起来形成的一种链表。

• 有向图的每一条弧对应十字链表中的一个弧结点，同时有向图中的每个顶点在十字链表中对应有一个结点，叫做顶点结点。

邻接多重表

• 邻接多重表是无向图的另一种链式存储结构。

优点：容易求得顶点和边的信息。 缺点：某些操作不方便（如：删除一条边需找表示此边的两个结点）

图的遍历

• 遍历的定义：从已给的连通图中某一顶点出发，沿着一些边访遍图中所有的顶点，且使每个顶点仅被访问一次，就叫做图的遍历，它是图的基本运算。

遍历实质：找每个顶点的邻接点的过程。

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

怎么样避免重复访问？ 解决思路：设置辅助数组 visited[n]，用来标记每个被访问过的顶点。 1、初识状态 visited[i] 为 0； 2、顶点 i 被访问，改 visited[i] 为 1，防止被多次访问。

• 图常用的遍历
1. 深度优先搜索（Depth_First Search——DFS）
2. 广度优先搜索（Breadth_First Search——BFS）

深度优先遍历（DFS）

• 方法

深度优先搜索遍历算法的实现

• 邻接矩阵表示的无向图深度遍历实现

• 算法：采用邻接矩阵表示图的深度优先搜索遍历

DFS算法效率分析

• 用邻接矩阵来表示图，遍历图中每一个顶点都要从头扫描该顶点所在行，时间复杂度为 。

• 用邻接表来表示图，虽然有 2e 个表结点， 但只需扫描 e 个结点即可完成遍历，加上访问 n 个头结点的时间，时间复杂度为 。

• 非连通图的遍历

广度优先搜索（BFS）

• 方法：从图中的某一结点出发，首先依次访问该结点的所有邻接点 再按这些顶点被访问的先后次序依次访问与他们相邻接的所有未被访问的顶点，重复此过程，直到所有顶点均被访问为止。

• 连通图

• 非连通图

广度优先搜索遍历算法的实现

• 邻接表表示的无向图广度遍历实现

• 算法：按广度优先非递归遍历连通图G

BFS算法效率分析

• 如果使用邻接矩阵，则BFS对于每一个被访问到的顶点，都要循环检测矩阵中的整整一行（n个元素），总的时间代价为 。

• 用邻接表来表示图，虽然有 2e 个表结点，但只需扫描 e 个结点即可完成遍历，加上访问 n 个头结点的时间，时间复杂度为 。

DFS与BFS算法效率比较

• 空间复杂度相同，都是 （借用了堆栈或队列）；

• 时间复杂度只与存储结构（邻接矩阵或邻接表）有关，而与搜索路径无关。

图的应用

概念回顾

• 生成树：所有顶点均由边连接在一起，但不存在回路的图。

一个图可以有许多棵不同的生成树 所有生成树具有以下共同特点 1、生成树的顶点个数与图的顶点个数相同； 2、生成树是图的极小连通子图，去掉一条边则非连通； 3、一个有n个顶点的连通图的生成树有n-1条边； 4、在生成树中再加一条边必然形成回路； 5、生成树中任意两个顶点间的路径是唯一的。

💡

含n个顶点n-1条边的图不一定是生成树

 

• 无向图的生成树

最小生成树

• 最小生成树：给定一个无向网络，在该网的所有生成树中，使得各边权值之和最小的那棵生成树称为该网的最小生成树，也叫最小代价生成树。

构造最小生成树 Mininum Spanning Tree

• 构造最小生成树的算法很多，其中多数算法都利用MST的性质。

• MST性质：设 是一个连通图， U 是顶点集 V 的一个非空子集。若边 (u, v) 是一条具有最小权值的边，其中 ，，则必存在一棵包含边 (u, v) 的最小生成树。

• 算法思想

• 算法思想

两种算法比较

最短路径

• 在有向图中源点到达终点的多条路径中，寻找一条各边权值之和最小的路径，即最短路径。

最短路径与最小生成树不同，路径上不一定包含n个顶点，也不一定包含n-1条边。

• 第一类问题：两点间最短路径

• 第二类问题：某源点到其他各点最短路径

一、单源最短路径——用Dijistra（迪杰斯特拉）算法

• Dijistra（迪杰斯特拉）算法

按路径长度递增次序产生最短路径

二、所有顶点间的最短路径——用Floyd（弗洛伊德）算法

• Floyd（弗洛伊德）算法
1. 逐个顶点试探
2. 从 到 的所有可能存在的路径中
3. 选出一条长度最短的路径

有向无环图及其应用

• 有向无环图：无环的有向图，简称 DAG 图（Directed Acycline Graph）

AOV网：拓扑排序

• 用一个有向图表示一个工程的及其相互制约的关系，其中以顶点表示活动，弧表示活动之间的优先制约关系，称这种有向图为顶点表示活动的网，简称 AOV 网（Activity On Vertex network）。

• 拓补排序的方法

拓扑排序的重要应用

• 检验 AOV 网中是否存在环方法：对有向图构造其顶点的拓扑有序序列，若网中所有顶点都在它的拓扑有序序列中，则该 AOV 网必定不存在环。