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