DS-6-图
2021-07-30 11:59:17 1 举报AI智能生成
数据结构 第六章 图 知识点梳理
作者其他创作
大纲/内容
方法
基本操作
时间复杂度
邻接矩阵
邻接表
bool Adjacent(vNode* i, vNode* j)
O(1)
O(1)~O(|V|)
UDG::vNode[] Neighbors(vNode* i)
O(|V|)
O(1)~O(|V|)
DG::vNode[] Neighbors(vNode* i)
O(|V|)
Out：O(1)~O(|V|)
In：O|E|
In：O|E|
bool Insert(vNode* x)
O(1)
O(1)
UDG::bool Insert(arcNode edge)
O(1)
O(1)
DG::bool Insert(arcNode arc)
O(1)
O(1)
UDG::bool Delete(vNode* i)
O(|V|)
O(1)~O(|E|)
DG::bool Delete(vNode* i)
O(|V|)
Out：O(1)~O(|V|)
In：O|E|
In：O|E|
weight{get; set;}
O(1)
O(1)~O(|V|)
遍历
广度优先BFS
树的BFS=层序遍历：Compare
需要一个辅助队列
实现
设置一个辅助队列Q
设置数组isVisited[]标记访问过的顶点
Graph::void BFS()
foreach (i in graph)
{isVisited[i]=false;}
{isVisited[i]=false;}
Q.Clear();
foreach (i in graph)
if(!isVisited[i])
if(!isVisited[i])
i.visit();
isVisited[i]=true;
Q.Enque(i);
While (!Q.isEmpty)
foreach (w in head
.Neighbors())
if(!isVisited[w])
.Neighbors())
if(!isVisited[w])
w.visit();
isVisited[w]=true;
Q.Enque(w);
Q.Deque(head);
//单次只能遍历一个连通区域，非连通图需要利用isVisited[]寻找其他的非连通区域
性能分析
空间复杂度
worst(星型)，best(链表)
时间复杂度
邻接矩阵,邻接表
顶点visit()次数+边Neighbor()次数：思路
BFS生成树
可以根据遍历过程构造一棵BFS生成树
用邻接表表示的图，不唯一
非连通图构造出的是BFS生成森林
深度优先DFS
树的DFS=先根遍历：Compare
实现
设置数组isVisited[]标记访问过的顶点
Graph::void DFS()
foreach (i in graph)
{isVisited[i]=false;}
{isVisited[i]=false;}
foreach (i in graph)
if(!isVisited[i])
if(!isVisited[i])
//单次只能遍历一个连通区域，非连通图需要利用isVisited[]寻找其他的非连通区域
i.visit();
isVisited[i]=true;
foreach (v in i.Neighbors())
if(!isVisited[v])
{DFS(v);}
if(!isVisited[v])
{DFS(v);}
性能分析
空间复杂度(递归深度)
worst(链表)，best(星型)
时间复杂度
邻接矩阵,邻接表
顶点visit()次数+边Neighbor()次数：思路
DFS生成树
可以根据遍历过程构造一棵DFS生成树
用邻接表表示的图，不唯一
非连通图构造出的是DFS生成森林
遍历轮数
无向图
连通分量数
有向图
1次~强连通分量数
最小生成树MST
(最小代价)
(最小代价)
性质
生成树：V'=V，不存在回路，且连通的无向图
是图，不是树，不区分根结点
可能不唯一，且和权必相等
若一个连通图已经是一棵树，则其MST是它本身
Prim算法
选点
选点
从某个顶点开始构建
选出将树中顶点连接的所有边中
代价最小的边所指向的新顶点
代价最小的边所指向的新顶点
将其纳入生成树，
直到所有顶点均纳入
直到所有顶点均纳入
：时间复杂度
适用于边稠密图
Kruskal算法
选边
选边
在所有边中每次选择一条权值最小的
如果边的两端点有未连通的
则连通此边，否则选择次小的
则连通此边，否则选择次小的
重复，直到所有顶点均连通
：时间复杂度
适用于边稀疏图
判断是否连通需要了解“并查集”之概念
最短路径问题
单源
BFS算法(无权)
执行一次BFS就可得到每一个顶点的最小距离
需要d[]，path[]保存该顶点的最短距离以及前驱顶点
d[]，path[]分别初始化为∞、-1
可以通过BFS生成树直接得到d[],path[]
Dijkstra算法(通用)
需要final[]，d[]，path[]保存该顶点是否找到最小路径，最短路径长度以及前驱顶点
初始化
final[] = self ? true : false;
dist[] = self ? 0 : (this.next ? next.dist : ∞);
path[] = this.next ? 0 : ∞;
while (final[*]==false)
找到 final[i] = FALSE 的顶点中dist[i]最小的
设final[i]=true
设final[i]=true
遍历该点所有后继j，
若其dist[j]>dist[i]+weight[i,j]，
则令其dist[j]=dist[i]+weight[i,j]，
并设path[j]=i，否则不操作
若其dist[j]>dist[i]+weight[i,j]，
则令其dist[j]=dist[i]+weight[i,j]，
并设path[j]=i，否则不操作
性能分析
时间复杂度
双重循环
存在负权值的图可能会导致算法失效：NOTE
Dijkstra的成就
goto有害论：OS，虚拟存储技术
信号量机制PV原语：OS，进程同步
银行家算法：OS，死锁
解决哲学家进餐问题：OS，死锁
Dijkstra算法：DS
任意顶点对
Floyd算法(通用)
动态规划算法
动态规划算法
计算不允许中转的距离矩阵
遍历全部顶点
计算在顶点中转的距离矩阵
若经中转距离小于当前距离，则将当前距离改为中转距离
并将path中对应位置改为i，以表明该路径经i中转最短
并将path中对应位置改为i，以表明该路径经i中转最短
空间复杂度，时间复杂度：性能分析
寻找i到j路径时，若，表明该路径经k中转最短，化为递归问题
允许负权值。但负权值边不能参与成环
有向无环图(DAG)
描述表达式
描述表达式
叶子结点必不重复
用于合并表达式的重复部分
bool Same(A,B);
if(A.op!=B.op) return false;
if(AB为叶子) return (A==B);
if(Same(A.lc,B.lc) 且 Same(A.rc,B.rc)) return true;
if(AB为叶子) return (A==B);
if(Same(A.lc,B.lc) 且 Same(A.rc,B.rc)) return true;
for(左叶子→右叶子；叶子→根；){
if(Same(A,B)){B.parent.B=A; Free(B)}
}
if(Same(A,B)){B.parent.B=A; Free(B)}
}
DAG拓扑排序
(AOV网)
(AOV网)
以DAG表示含有多个活动的工程，某些活动i必须先于活动j完成，以有向边<i,j>记之。
这种网络称为AOV网
这种网络称为AOV网
输出拓扑排序序列
序列是不唯一的
且序列的前后元素间
在原图中不总有弧
序列是不唯一的
且序列的前后元素间
在原图中不总有弧
选择一个入度为0(即无前驱)的结点并输出
删除(isVisit记录)他及以他为起点的有向边
重复以上步骤直到AOV网
为空：排序完成
不为空且不存在无前驱顶点：排序失败，有回路
需要遍历出边，考察不同数据结构的特性：性能分析
反向输出，从出度为0的开始，操作类似：逆拓扑排序
关键路径
(AOE网)
(AOE网)
以边表示活动，顶点表示“活动已完成”的事件
性质
只有顶点代表的事件发生后，从顶点出发的边代表的活动才能开始
只有顶点入边事件全部完成后，从顶点代表的事件才能发生
关键路径
具有最大长度的路径
完成工程的最短时间
关键活动
决定完成工程的最短时间的边
成员
事件发生的最早时间
不影响工期的情况下，事件发生的最迟时间
活动开始的最早时间
该弧终点的事件最迟发生的事件与该活动所需时间的差额：活动开始的最迟时间
：时间余量
方法
求
概念与性质
定义
包含顶点集V和边集E组成一个图G
任意一条边必须连接两个顶点，且是V中的顶点
V不能为空，但是E可以为
分类
按边种类
有向图
边称为有向边，也称弧
弧头：弧终点
弧尾：弧始点
无向图
边称为无向边，简称边
按连接方式
简单图
不存在重复边
不存在顶点到其自身的边
多重图
无向/有向完全图：任意两个顶点均存在边/双向的两条弧
有条边或条弧
按连通性
连通图：任意一对顶点连通
至少具有条边
强连通图：任意一对顶点均强连通
至少条边(形成回路)
非连通图：存在顶点与其他顶点不连通
最多有条边
按边数
稀疏图：边少
稠密图：边多
成员
度D：连接顶点的边数
(有向图TD(v)=ID+OD)
(有向图TD(v)=ID+OD)
入度ID(v)：以顶点v为终点
出度OD(v)：以顶点v为起点
路径
顶点到的顶点序列(含端)(不唯一)
有向图中路径必须遵循弧的方向
回路/环：两端相同的路径
简单路径：除了端点外，其余顶点不重复
长度：路径上边的数目
距离：两个顶点最短路径的长度，不存在则为
子图
取出V和E的子集V',E'，能构成一个图G'，则，G'是G的子图
生成子图：当V'=V
生成树：连通且不存在回路的无向图
有向树：1个顶点ID=0，其余ID=1的有向图(非强连通)
强连通分量
(有向图)
(有向图)
极大强连通子图
必须强连通
包含尽可能多的顶点
包含尽可能多的边
有向图中的极大强连通子图称强连通分量(不唯一)
连通分量
(无向图)
(无向图)
极大连通子图
必须连通
包含尽可能多的顶点
包含尽可能多的边
无向图中的极大连通子图称连通分量
生成树
包含全部顶点的一个极小连通子图
不是树，不区分根节点
生成树：V'=V，不存在回路，且连通的无向图
包含n-1条边
加边必成回路
减边必非连通
最小生成树MST：在带权的图中才有MST
有向树：1个顶点ID=0，其余ID=1的有向图
拓扑序列
(有向无环图)
(有向无环图)
派生
带权图/网：每条边带权
带权路径长度：路径上的权之和
DAG图
AOV网：(Activity on Vertices)
AOE网：(Activity on Edges)
存储
邻接矩阵
无向图
有向图
带权图(自定义方式表示)
空间复杂度
太高！
太高！
适合稠密图
边数=2|E|
可以应用对称矩阵压缩
约定：元素代表的边方向均为行号列号
对于不带权的图，，可表示顶点到顶点长度为的路径数
方法
求入度：时间复杂度O(n)
求出度：时间复杂度O(n)
求出度：时间复杂度O(n)
删边
方便
删结点
大量移动数据
邻接表
(不唯一)
(不唯一)
结构
typedef {Sqlist<vNode<T>> vertices, int vexNum, int arcNum} map<T>
typedef {T data, ArcNode* firstArc} vNode<T>
typedef {int tailVertex, ArcNode* nextArc} ArcNode
无向图：边数=2|E|，空间复杂度O(|V|+2|E|)
有向图：边数=|E|，空间复杂度O(|V|+|E|)
有向图：边数=|E|，空间复杂度O(|V|+|E|)
适合稀疏图
方法
求出度：O(n)
求入度：O(|V||E|) 太高！
删结点/边：极为不便
派生：逆邻接表
十字链表
有向图
有向图
结构
typedef {Sqlist<vNode<T>> vertices, int vexNum, int arcNum} map<T>
typedef {T data, ArcNode* firstInArc, ArcNode* firstOutArc} vNode<T>
typedef {int tailVex, int headVex, float weight, ArcNode* nextArcCohead,
ArcNode* nextArcCotail} ArcNode
ArcNode* nextArcCotail} ArcNode
空间复杂度O(|V|+|E|)
方法
求出度：
找到firstOutArc指针指向的弧，再按其nextArcCotail指针寻找
求入度：
找到firstInArc指针指向的弧，再按其nextArcCohead指针寻找
邻接多重表
无向图
无向图
结构
typedef {Sqlist<vNode<T>> vertices, int vexNum, int arcNum} map<T>
typedef {T data, ArcNode* firstEdge} vNode<T>
typedef {int iVex, int jVex, float weight, ArcNode* nextEdgeCo_i,
ArcNode* nextEdgeCo_j} ArcNode
ArcNode* nextEdgeCo_j} ArcNode
//注 i,j相同，顺序不同的边是同一条边。
空间复杂度O(|V|+|E|)
方法
删除结点i
删除结点i，删除i指向的边，逐次删除边的共i指针指向的边
职业：暂无
0 条评论
下一页
