首页  思维导图  详情

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|

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|

weight{get; set;}

O(1)

O(1)~O(|V|)

遍历

广度优先BFS

树的BFS=层序遍历：Compare

需要一个辅助队列

实现

设置一个辅助队列Q

设置数组isVisited[]标记访问过的顶点

Graph::void BFS()

foreach (i in graph) {isVisited[i]=false;}

Q.Clear();

foreach (i in graph) if(!isVisited[i])

i.visit();

isVisited[i]=true;

Q.Enque(i);

While (!Q.isEmpty)

foreach (w in head .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;}

foreach (i in graph) if(!isVisited[i])

//单次只能遍历一个连通区域，非连通图需要利用isVisited[]寻找其他的非连通区域

i.visit();

isVisited[i]=true;

foreach (v in i.Neighbors()) 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

遍历该点所有后继j， 若其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中转最短

空间复杂度，时间复杂度：性能分析

寻找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;

for(左叶子→右叶子；叶子→根；){ if(Same(A,B)){B.parent.B=A; Free(B)} }

DAG拓扑排序 (AOV网)

以DAG表示含有多个活动的工程，某些活动i必须先于活动j完成，以有向边<i,j>记之。 这种网络称为AOV网

输出拓扑排序序列 序列是不唯一的 且序列的前后元素间 在原图中不总有弧

选择一个入度为0(即无前驱)的结点并输出

删除(isVisit记录)他及以他为起点的有向边

重复以上步骤直到AOV网

为空：排序完成

不为空且不存在无前驱顶点：排序失败，有回路

需要遍历出边，考察不同数据结构的特性：性能分析

反向输出，从出度为0的开始，操作类似：逆拓扑排序

关键路径 (AOE网)

以边表示活动，顶点表示“活动已完成”的事件

性质

只有顶点代表的事件发生后，从顶点出发的边代表的活动才能开始

只有顶点入边事件全部完成后，从顶点代表的事件才能发生

关键路径

具有最大长度的路径

完成工程的最短时间

关键活动

决定完成工程的最短时间的边

成员

事件发生的最早时间

不影响工期的情况下，事件发生的最迟时间

活动开始的最早时间

该弧终点的事件最迟发生的事件与该活动所需时间的差额：活动开始的最迟时间

：时间余量

方法

求

概念与性质

定义

包含顶点集V和边集E组成一个图G

任意一条边必须连接两个顶点，且是V中的顶点

V不能为空，但是E可以为

分类

按边种类

有向图

边称为有向边，也称弧

弧头：弧终点

弧尾：弧始点

无向图

边称为无向边，简称边

按连接方式

简单图

不存在重复边

不存在顶点到其自身的边

多重图

无向/有向完全图：任意两个顶点均存在边/双向的两条弧

有条边或条弧

按连通性

连通图：任意一对顶点连通

至少具有条边

强连通图：任意一对顶点均强连通

至少条边(形成回路)

非连通图：存在顶点与其他顶点不连通

最多有条边

按边数

稀疏图：边少

稠密图：边多

成员

度D：连接顶点的边数 (有向图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)

删边

方便

删结点

大量移动数据

邻接表 (不唯一)

结构

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|)

适合稀疏图

方法

求出度：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

空间复杂度O(|V|+|E|)

方法

求出度：

找到firstOutArc指针指向的弧，再按其nextArcCotail指针寻找

求入度：

找到firstInArc指针指向的弧，再按其nextArcCohead指针寻找

邻接多重表 无向图

结构

typedef {T data, ArcNode* firstEdge} vNode<T>

typedef {int iVex, int jVex, float weight, ArcNode* nextEdgeCo_i, ArcNode* nextEdgeCo_j} ArcNode

//注 i,j相同，顺序不同的边是同一条边。

空间复杂度O(|V|+|E|)

方法

删除结点i

删除结点i，删除i指向的边，逐次删除边的共i指针指向的边

 收藏

立即使用

OpenGL渲染管线入门

 收藏

立即使用

OS-5-IO管理

 收藏

立即使用

OS-4-文件管理

 收藏

立即使用

OS-3-内存管理

EricSolshkov

职业：暂无

去主页





0 条评论

下一页

为你推荐

查看更多



reporte_cartas_ds_ent

图6

reporte_ds