图_计算机数据结构考研
2020-07-07 13:38:42 1 举报AI智能生成
图_计算机数据结构考研
作者其他创作
大纲/内容
版权∈ 本人所有
严禁擅自转载和商用 受法律保护
严禁擅自转载和商用 受法律保护
更新记录
2020.5.22 开坑
图
定义
图G 由 顶点集V 和 边集E 组成
简单图
不存在重复边 不存在顶点到自身的边
简单路径
路径序列中 顶点不重复
简单回路
除起始和终点外 其余顶点不重复出现
带权图/网
边上带有权值的图
稀疏图和稠密图
边数定义 |E|<|V| log|V|
无向图
(v,w)表示边 (v,w)=(w,v)
顶点v的度
依附于顶点边的条数 TD(v)
连通
两个顶点间存在路径
连通分量
无向图中的极大连通子图
子图必须连通 且 包含尽可能多的顶点和边
生成森林
非连通图中 连通分量的生成树构成非连通图的生产森林
无向完全图
任意两个顶点间都存在边
n个顶点 C2n条边
有向图
<v,w>表示边 <v,w> ≠ <w,v>
入度
以顶点v为终点 ID(v)
出度
以顶点v为起点 OD(v)
强连通
两个顶点之间相互有路径
强连通分量
有向图中极大强连通子图
生成树
包含图中全部顶点的一个极小连通子图
边尽可能少 但保持连通
n个顶点 n-1条边
有向完全图
任意两个顶点都有方向相反的两条弧
n个顶点 2C2n条边
树和有向树
连通图 VS 强连通图
子图
有向图和无向图均可
有向图和无向图均可
图的存储
邻接矩阵
无向图 —— 1代表有边连接
有向图 —— 1代表有指向该方向的边连接
有向图 —— 1代表有指向该方向的边连接
0 或 ∞ 表示不存在边
表示方式唯一
表示方式唯一
空间复杂度 O (|V|²) ——只和顶点数相关
适合稠密图
对称矩阵的压缩
性质
邻接表
表示方式不唯一
十字链表
找出边和入边都很容易 橙色找入边 绿色找出边
只能用于有向图
空间复杂度 O(|V|+|E|)
只能用于有向图
空间复杂度 O(|V|+|E|)
邻接多重表
只能用于无向图
基本操作【邻接矩阵 & 邻接表】
邻接矩阵
是否存在边、获取边的权值、设置边的权值【更优秀】
有向图 O(1)
无向图 O(1)
列出邻接边
无向图 O(V)
有向图 O(V)
插入新顶点x
无向图/无向图 O(1)
删除顶点x
无向图 O(V)
有向图 O(V)
增加一条边
有/无向图 O(1)
判断找到顶点的第一个邻接点
有/无向图 O(V)
NextNeighbor
无向图 O(V)
邻接表
是否存在边、获取边的权值、设置边的权值
有向图 O(V)
无向图 O(V)
列出邻接边
无向图 O(V) 【更优秀】
有向图 出边O(V) 入边O(E)
插入新顶点x
无向图/无向图 O(1)
删除顶点x
无向图 O(E)
有向图 出边O(V) 入边O(E)
增加一条边
有/无向图 O(1)
判断找到顶点的第一个邻接点
无向图 O(1)
有向图 出边O(1) 入边O(E)
NextNeighbor
无向图 O(1)
应用
广度优先算法BFS
要点
① 找到与一个顶点相邻的所有顶点 【FirstNeighbor NextNeighbor】
② 标记哪些顶点被访问过
③ 需要一个辅助队列
④ 处理非连通图
广度优先树
邻接矩阵 唯一
邻接表 不唯一
广度优先森林
对于非连通的BFS 可以生成
BFSTraverse 处理非连通图 对于无向图，调用BFS函数次数=连通分量数
复杂度=访问结点时间+访问所有边的时间
空间复杂度O(V) 邻接矩阵时间O(V²) 邻接表时间O(V+E)
复杂度=访问结点时间+访问所有边的时间
空间复杂度O(V) 邻接矩阵时间O(V²) 邻接表时间O(V+E)
深度优先算法DFS
类似树的先根遍历
遍历序列
邻接矩阵表示唯一 DFS遍历序列唯一
邻接表表示不唯一 DFS遍历序列不唯一
深度优先森林
对于非连通的DFS 可以生成
DFSTraverse 处理非连通图 无向图调用DFS函数次数=连通分量数
空间复杂度 O(V) ——来自递归工作栈
邻接矩阵时间O(V²) 邻接表时间O(V+E)
空间复杂度 O(V) ——来自递归工作栈
邻接矩阵时间O(V²) 邻接表时间O(V+E)
最小生成树/最小代价树 MST
生成树 —— 包括图中全部顶点的一个极小连通子图 若顶点n 则生成树边n-1
带权连通无向图 可能会有多个但权值之和总是唯一最小
Prim算法 / 普里姆算法
任一顶点开始，纳入最小代价顶点 ，直到所有点纳入
时间复杂度 O(V²) 适合稠密图
Kruskal算法 /克鲁斯卡尔
每次选择一条权值最小的边 使两个顶点连通
时间复杂度 O(Elog2E) 适合稀疏图
最短路径问题
单源最短路径
BFS算法 无权图
小修改BFS
在visit一个顶点时修改其最短路径长度d[] 并在path[]记录前驱结点
在visit一个顶点时修改其最短路径长度d[] 并在path[]记录前驱结点
Dijkstra算法 带权图/无权图
dist 若没有边到达该点设为∞
path记录前驱结点 此时V0为0
时间复杂度O(n²)=O(V²)
不适用带有负权值的带权图
path记录前驱结点 此时V0为0
时间复杂度O(n²)=O(V²)
不适用带有负权值的带权图
① 遍历结点 找到还没确定最短路径且dist最小的顶点令final[i]=ture
② 一直重复①
② 一直重复①
各顶点间最短路径
Floyd算法 带权图/无权图
动态规划 问题求解分为多个阶段
n轮递推
不适用带有负权回路的图
不适用带有负权回路的图
有向无环图DAG
描述表达式 求出多少顶点
拓扑排序
AOV网 —— 用顶点表示活动的网 肯定是DAG 无环
含义
找到做事的先后顺序
实现
AOV网可能有多个拓扑排序序列
存在回路不能拓扑排序
存在回路不能拓扑排序
邻接表 indegree记录当前顶点入度 print记录拓扑序列
邻接矩阵 时间复杂度O(V²) 邻接表 时间复杂度 O(V+E)
邻接矩阵 时间复杂度O(V²) 邻接表 时间复杂度 O(V+E)
逆拓扑排序
实现
DFS算法实现 在顶点退栈时输出
关键路径
AOE网
顶点表示事件 边表示活动及权值
结束顶点 —— 汇点
开始顶点 —— 源点
开始顶点 —— 源点
性质
含义
最大路径长度的路径【整个工程完成的最短时间】
实现
特性
若关键活动耗时增加/缩短 则工程工期增长/缩短
若关键活动缩短到一定程度，关键活动可能会变成非关键活动
提高一个关键活动速度可能无助于整个工期
章节技巧
线性表可以是空表 树可以是空树 图一定是非空集
(逆)拓扑排序序列可不唯一 若图中有环则不存在(逆)拓扑排序序列
图的遍历和图的连通性
有向图
强连通图 从任一结点出发都只需调用一次BFS/DFS函数
若起点顶点到其他各顶点都有路径，则只需调用一次BFS/DFS函数
无向图
DFS/BFS函数调用次数=连通分量数
有向图 VS 无向图
邻接矩阵 VS 邻接表
邻接多重表 VS 十字链表
0 条评论
下一页
