王道数据结构第六章图_思维导图模板

第六章图

图

基本概念

定义：G=(V,E),顶点集V,边集E

图不可以是空图

无向图（无向边）/有向图（有向边/弧）

对于无向图：顶点v的度指依附于该顶点的边的条数，记为TD(v)

对于有向图

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

出度是以顶点v为起点的有向边的数目，记为OD(v)

顶点v的度等于其入度和出度之和TD(v)=ID(v)+OD(v)

简单图/多重图

路径：从一个顶点到另一个顶点的顶点序列

简单路径：在路径序列中，顶点不重复出现的路径称为简单路径

路径长度：路径上边的数目

回路（环）：第一个顶点和最后一个顶点相同的路径称为回路或环

简单回路：除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路称为简答回路

点到点的距离：从顶点u出发到顶点v的最短路径若存在，则此路径的长度称为从u到v的距离，若从u到v根本不存在路径，则记该距离为无穷

无向图中，若从顶点v到顶点w有路径存在，则称v和w是连通的

若图中任意两个顶点都是连通的，则称图为连通图，否则称为非连通图

有向图中，若从顶点v到顶点w既有正向路径又有逆向路径，则称v和w是强连通的

若图中任何一对顶点都是强连通的，则称此图为强连通图

子图/生成子图（子图包括所有顶点）

连通分量：无向图中的极大连通子图（必须连通且包含尽可能多的边和顶点）

强连通分量：有向图中的极大强连通子图（必须强连通且保留尽可能多的边）

连通图的生成树是包含图中全部顶点的一个极小连通子图（边尽可能的少但要保持连通）

若生成树有n个顶点，则必有n-1条边

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

边的权：边上有意义的数值

带权图：边上有权值的图

带权路径长度：当图是带权图时，一条路径上所有边的权值之和

常见考点：
对于n个顶点的无向图G，
若G是连通图，则最少有n-1条边，
若G是非连通图，则最多可能有条边
对于n个顶点的有向图G，
若G是强连通图，则最少有n条边

几种特殊的图

无向完全图：无向图中任意两个顶点之间都存在边

n个顶点对应条边

有向完全图：有向图中任意两个顶点之间都存在方向相反的两条弧

n个顶点对应条边

稀疏图/稠密图

树：不存在回路，且连通的无向图

n个顶点的树必有n-1条边

常见考点：n个顶点的图，若|E|>n-1，则图中一定存在回路

有向树：一个顶点的入度为0，其余顶点的入度均为1的有向图

有向树不是强连通图

常见考点

图的存储

邻接矩阵

无向图

第i个结点的度 = 第i行（或第i列）的非零元素个数

有向图

第i个结点的出度 = 第i行的非零元素个数

第i个结点的入度 = 第i列的非零元素个数

第i个结点的度 = 第i行、第i列的非零元素个数之和

带权图

设图G的邻接矩阵为A（矩阵元素为0/1），则的元素等于由顶点i到顶点j的长度为n的路径的数目

要点回顾

邻接表

图的邻接表表示方式并不唯一

十字链表

邻接多重表

图的基本操作

Adjacent(G,x,y)：判断图G是否存在边或(x, y)。

Neighbors(G,x)：列出图G中与结点x邻接的边。

InsertVertex(G,x)：在图G中插入顶点x。

DeleteVertex(G,x)：从图G中删除顶点x。

AddEdge(G,x,y)：若无向边(x, y)或有向边不存在，则向图G中添加该边。

RemoveEdge(G,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)或对应的权值。

Set_edge_value(G,x,y,v)：设置图G中边(x, y)或对应的权值为v。

图的遍历

广度优先遍历（BFS）

与树的广度优先遍历之间的联系

树：不存在回路，搜索相邻的结点时，不可能搜到已经访问过的结点

搜索相邻的顶点时，有可能搜到已经访问过的结点

算法实现

需要一个辅助队列

如何从一个顶点找到与之邻接的其他顶点

visited数组防止重复访问

如何处理非连通图

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

对于无向图，调用BFS函数的次数=连通分量数

复杂度分析

空间复杂度

辅助队列：

时间复杂度

访问结点的时间+访问所有边的时间

邻接矩阵存储的图：

邻接表存储的图：

广度优先生成树

根据广度优先遍历的过程得到，去掉没有被遍历的边，就生成了一棵树

基于邻接表的广度优先遍历序列和生成树不唯一

广度优先生成森林

便利非连通图

深度优先遍历（DFS）

与树的深度优先遍历之间的联系

递归地深入探索未被访问过的邻接点（类似于树的先根遍历的实现）

算法实现

如何从一个顶点找到与之邻接的其他顶点

visited数组防止重复访问

如何处理非连通图

如果是非连通图则无法访问所有结点

复杂度分析

空间复杂度

函数调用栈：

时间复杂度

访问各结点所需时间+探索各条边所需时间

邻接矩阵存储的图：

邻接表存储的图：

深度优先生成树

由深度优先遍历确定的树

基于邻接表的深度优先遍历序列和生成树不唯一

深度优先遍历非连通图可得深度优先生成森林

图的遍历和图的连通性

无向图

DFS/BFS函数调用次数=连通分量数

有向图

若从起始顶点到其他顶点都有路径，则只需调用1次DFS/BFS函数

对于强连通图，从任一顶点出发都只需调用1次DFS/BFS函数

图的应用

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

最小生成树（MST）的概念

对于一个带权连通无向图，生成树不同，每棵树的权也可能不同。
设R为G的所有生成树的集合，若T为R中边的权值之和最小的生成树
则T称为G的最小生成树（MST）

如果一个连通图本身就是一棵树，则其最小连通生成树就是它自身

只有连通图才有生成树，非连通图只有生成森林

Prim算法

从某一个顶点开始构建生成树；每次将代价最小的新顶点纳入生成树，直到所有顶点都纳入为止。

时间复杂度：

适用于边稠密图

Kruskal算法

每次选择一条权值最小的边，使这条边的两头连通（原本已经连通的就不选）直到所有结点都连通

时间复杂度：

适用于边稀疏图

考代码概率不高
要熟悉运算过程

最短路径问题

单源最短路径

BFS算法（无权图）

就是对BFS的小修改，在visit一个顶点时，修改其最短路径长度d[]，并在path[]记录前驱节点

Dijkstra算法（带权图，无权图）

算法思想

final[]：标记各顶点是否已找到最短路径

dist[]：最短路径长度

path[]：路径上的前驱

arcs[i][j]：到的弧的权值

初始：
若从开始，令final[0]=true;dist[0]=0;path[0]=-1。
其余顶点final[k]=false;disk[k]=arcs[0][k];path[k]=(acrs[0][k]==)?-1:0

n-1轮处理：
循环遍历所有顶点，找到还没确定最短路径，且dist最小的顶点，
令final[i]=true。并检查所有邻接自的顶点，
若final[j]=false且dist[i]+arcs[i][j]则令dist[j]=dist[i]+arcs[i][j];path[j]=i。

时间复杂度

总时间复杂度：

每一轮时间复杂度：

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

各顶点间的最短路径

Floyd算法（带权图，无权图）

算法思想：动态规划

Floyd算法可以用于解决负权值带权图

Floyd算法不能解决带有“负权回路”的图（有负权值的边组成回路），这种图可能没有最短路径

有向无环图（DAG）的问题

有向无环图描述表达式

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

一个算术表达式可以表示为一棵树的形式

丢弃重复部分，进行合并

做题方法

原理：顶点中不可能出现重复的操作数

方法

Step1：把各个操作数不重复的排成一排

Step2：标出各个运算符的生效顺序（先后顺序有点出入无所谓）

Step3：按顺序加入运算符，注意“分层”

分层：上层的运算符要基于下一层的运算结果来进行

Step4：从底向上逐层检查的运算符是否可以合体

拓扑排序

AOV网（用顶点表示活动的网）：
用DAG图（有向无环图）表示一个工程。
顶点表示活动，有向边表示活动必须先于进行。

AOV网一定是DAG图，不能有环

拓扑排序：
在图论中，由一个有向无环图的顶点组成的序列，当且仅当满足下列条件时，称为该图的一个拓扑排序：
1.每个顶点出现且只出现一次。
2.若顶点A在序列中排在顶点B的前面，则在图中不存在从顶点B到顶点A的路径。

简单理解：拓扑排序就是要找到做事的先后顺序

每个AOV网都有一个或多个拓扑排序

拓扑排序的实现：
1.从AOV网中选择一个没有前驱（入度为0）的顶点并输出。
2.从网中删除该顶点和所有以它为起点的有向边。
3.重复1和2，直到当前的AOV网为空或当前网中不存在无前驱的顶点为止。

indegree[]：记录当前顶点入度

print[]：记录拓扑排序序列

S：保存度为0的顶点（可用栈，也可用队列）

时间复杂度

邻接表：

邻接矩阵：

逆拓扑排序

逆拓扑排序的实现：
1.从AOV网中选择一个没有后继（入度为0）的顶点并输出。
2.从网中删除该顶点和所有以它为终点的有向边。
3.重复1和2，直到当前的AOV网为空或当前网中不存在无后继的顶点为止。

第一种算法与拓扑排序类似，自行设计代码

DFS算法

性质

拓扑排序、逆拓扑排序序列可能不唯一

若图中有环，则不存在拓扑排序序列/逆拓扑排序序列

关键路径问题

AOE网

在带权有向图中，以顶点表示事件，以有向边表示活动，以边上的权值表示完成该活动的开销（如完成活动所需的时间），称之为用边表示活动的网络，简称AOE网。

AOE网的两个性质

只有在某顶点所代表的事件发生后，从该顶点出发的各有向边所代表的活动才能开始。

只有在进入某顶点的个有向边所代表的活动都已结束时，该顶点所代表的事件才能发生。另外，有些活动是可以并行进行的。

在AOE网中仅有一个入度为0的顶点，称为开始顶点（源点），它表示整个工程的开始，也仅有一个出度为0的点，称为结束顶点（汇点），它表示整个工程的结束

从源点到汇点的有向路径可能有多条，所有路径中，具有最大路径长度的路径称为关键路径，而把关键路径上的活动称为关键活动

完成整个工程的最短时间就是关键路径的长度，若关键活动不能按时完成，则整个工程的完成时间就会延长。

一些概念

事件的最早开始时间ve(k)——决定了所有从开始的活动能够开工的最早时间

活动的最早开始时间e(i)——指该活动的起点所表示的事件的最早发生时间

事件的最迟开始时间ve(k)——它是指在不推迟整个工程完成的前提下，该事件最迟必须发生的时间

活动的最迟开始时间l(i)——它是指该活动弧的终点所表示事件的最迟发生时间与该活动所需时间之差

活动的时间余量d(i)=l(i)-e(i)——表示在不增加完成整个工程所需总时间的情况下，活动可以拖欠的时间
若一个活动的时间余量为0，则说明该活动必须要如期完成，d(i)=0即l(i)=e(i)的活动是关键活动
由关键活动组成的路径就是关键路径。

解题步骤

1.求所有事件的最早发生时间ve()

按拓扑排序序列，依次求各个顶点的ve(k):
ve(源点)=0
ve(k) = Max{ve(j)+Weight(,)}，为的任意前驱

2.求所有事件的最迟发生时间vl()

按逆拓扑排序序列，依次求各个顶点的vl(k):
vl(汇点)=ve(汇点)
vl(k) = Min{vl(j)-Weight(,)}，为的任意后继

3.求所有活动的最早发生时间e()

若边表示活动，则有e(i)=ve(k)

4.求所有活动的最迟发生时间l()

若边表示活动，则有l(i)=vl(j)-Weight()

5.求所有活动的时间余量d()

d(i)=l(i)-e(i)

6.d(i)=0的活动就是关键活动，由关键活动可得关键路径

关键活动，关键路径的特性

若关键活动的耗时增加，则整个工程的工期将延长

缩短关键活动的时间，可以缩短整个工期

当缩短到一定程度时，关键活动可能会变成非关键活动

可能有多条关键路径，只提高一条关键路径上的关键活动速度并不能缩短整个工程的工期，只有加快那些包括在所有关键路径上的关键活动才能达到缩短工期的目的

王道数据结构第六章图

模板简介

猜你喜欢

相关文章

王道数据结构 第六章 图

模板简介

猜你喜欢

相关文章

王道数据结构第六章图