图状结构思维导图

U621655065

2022-12-26

浏览量: 4

有向无环图

最小生成树

数据库

树图思维导图提供《图状结构》在线思维导图免费制作，点击“编辑”按钮，可对《图状结构》进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：4bedf90caa3b05a13182bb01261c6a23

思维导图大纲

图的存储结构

邻接矩阵表示法

有向图无向图的邻接矩阵

基本概念

结构体定义

网（带权图）的邻接矩阵

基本概念

创建无向网

特点

空间效率：无向图的邻接矩阵对称，可以压缩存储空间；有n个顶点的无向图需要n(n-1)/2。有n个顶点的有向图所需要的存储空间为n^2；用于稀疏图空间浪费较多

容易实现图的操作（如：求某顶点的度、判断顶点之间是都右边、找顶点的邻接点）

邻接表表示法

无向图的邻接表

图示表示

邻接表不唯一，因为各个表结点的链入顺序是任意的空间效率为O(n+2e)，适合存储稀疏图 TD(Vi)=单链表中链接的结点数

有向图的邻接表

图示表示

空间效率：O(n+e) 出度：OD(Vi)=表中Vi链接单链表中的结点数入度：ID(Vi)=表中节点邻接点域为Vi的弧的个数度：TD(Vi)=OD(Vi)+ID(Vi)

二者的联系和区别

基本概念

定义

一种数据元素间存多对多关系的数据结构

分类

有向图

若<v,w>∈VR，则<v,w>表示从v到w的一条弧，且称弧v为弧尾，称w为弧头，此时的图为有向图

无向图

若<v,w>∈VR必有<w,v>∈VR，则以无序对（v，w）代表这两个有序对，表示v，w之间有一条边，此时的图为无向图

基本术语

稀疏图

含有很少条边或者弧的图

稠密图

含有很多条边或弧的接近完全图的图

权

与图的边或弧相关的数，这些数可以表示从一个顶点到另一个顶点的距离或耗费

网

带权的图

子图

如果图G=(V,E)和G’=(V’, E’)，满足：V’ ⊆ V且E’ ⊆ E，则称G’是G的子图

邻接点

无向图：若（v，v’）是一条边则称顶点v和v’互为邻接点，称边（v，v’）与v和v’相关联

有向图：若<v，v’>是一条弧，则称顶点v邻接到v’，顶点v’邻接自顶点v，弧<v，v’>与顶点v和v’相关联

度

无向图中顶点v的度是和v相关联的边的数目，记作TD（v）

入度：有向图以顶点v为头的弧的数目称为v的入度，记作ID（v）

出度：有向图以顶点v为尾的弧的数目称为v的出度，记作OD（v）

路径

定义

无向图G=（V，{E}）中从顶点v到v’的路径是一个顶点序列，满足（Vi,j-1，Vi,j）∈E 有向图，路径也是有向的，满足< Vi,j-1，Vi,j >∈E

路径长度

路径上边或弧的数目

回路

第一个顶点和最后一个顶点相同的路径

简单路径

序列中顶点（除两端点外）不重复出现的路径

简单回路

前后两端点相同的简单路径

连通

无向图中，从顶点v到v'之间有路径则称从v到v'是连通的

连通图：无向图中任意两个顶点都是连通的

连通分量：无向图的极大连通子图

生成树

包含无向图G中的所有顶点的极小连通子图

生成树的特点

一个图可以有多个生成树

所有生成树具有以下共同特点：  生成树的顶点个数和图的顶点个数一致  生成树是图的极小连通子图  一个有n个顶点的连通图生成树有n-1条边  生成树中任意两个顶点间的路径是唯一的  在生成树中再加一条边必然形成回路

含n个顶点n-1条边的图不一定是生成树

有向树

如果一个有向图恰有一个顶点的入度为0，其余顶点的入度均为1，则是一棵有向树

有向图的生成森林：由若干棵有向树组成，含有图中全部顶点，但只有足以构成若干棵不相交的有向树的弧

图的遍历

深度优先遍历（DFS）

概念

沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点v的所在边都己被探寻过或者在搜寻时结点不满足条件，搜索将回溯到发现节点v的那条边的起始节点。整个进程反复进行直到所有节点都被访问为止。属于盲目搜索,最糟糕的情况算法时间复杂度为O(!n)。

基本思路

为了求得问题的解，先选择某一种可能情况向前探索；

在探索过程中，一旦发现原来的选择是错误的，就退回一步重新选择，继续向前探索；

如此反复进行，直至得到解或证明无解

图示操作

代码实现

广度优先遍历（BFS）

基本概念

仿照树的层序遍历，查找遍历完整张图

基本思路

在访问起止点之后，依次访问v的邻接点

然后再依次访问这些顶点中未被访问的

直到所有顶点都被访问过为止

图示思路

代码实现

采用队列的方式 1. 把根结点放到队列的末尾 2. 每次从队列的头部取出一个元素，查看这个元素所有的下一级元素，把它们放到队列的末尾。并把这个元素标记为它下一级元素的前驱 3. 找到所要找的元素时结束程序 4. 如果遍历整个树都还没有找到，则结束程序

两个算法比较

最小生成树

无向图的连通分量和生成树

连通图的生成树不一定是唯一的，不同的遍历图的方法得到不同的生成树；从不同的顶点出发可得到不同的生成树。

每连通图本身就是连通分量，其中顶点集＋遍历经过的边=生成树。

非连通图的生成森林不一定是唯一的。

非连通图各个连通分量的顶点集＋遍历时经过的边=生成森林。

Prim算法

基本概念

Prim算法通过一系列不断扩张的子树来构造一棵最小生成树。

算法思想

从图的顶点集合中任意选择的一个单项点，作为序列中的初始子树。

每一次迭代时，以一种贪心的思想来扩张当前的生成树，即把不在树的最近顶点添加到树中

当图的所有顶点都包含在所构造的树中以后，该算法就停止了。

算法优化：我们可以定义一个优先队列，队列中元素记录了节点的编号和节点和树中的顶点相连的边权，将源点压入队列。当队列非空，执行以下操作： 1.u等于队顶的节点，w等于队顶节点的最短边权。 2.遍历u的所有边，如果能找到节点v小于v的当前值，更新v，将v压入队列。

举例说明

代码实现

Kruskal算法

基本概念

Kruskal算法按照权值从小到大的顺序选择 n-1 条边，并保证这 n-1 条边不构成回路

算法思路

使用并查集，并将加权图每个顶点都看做森林，然后将图中每条邻接边的边权按照升序的方式进行排列

从排列好的邻接边表中抽取边权最小的边，写入该边的起始顶点和结束顶点，连接顶点将森林构成树

然后读取起始结束顶点的邻接边，优先抽取边权小的邻接边，继续连接顶点将森林构成树。

添加邻接边的要求是加入到图中的邻接边不构成回路（环）。如此反复进行，直到已经添加n-1条边为止。

代码实现

两个算法比较

prim算法

归并顶点，算法的时间复杂度为O（n^2），与e无关

适用于稠密网

kruskal算法

归并边，算法的时间复杂度为O（eloge），与e有关

适用于稀疏网

有向无环图

基本概念

用有向无环图来描述一个工程或系统的进行过程。一个工程可以分为若干个子工程，只要完成了这些子工程(活动），就可以导致整个工程的完成。

1) 工程能否顺利进行，即工程流程是否 “合理”，这就是拓扑排序 2) 完成整个工程所必须的最短时间，即求关键路径（AOE网）问题。

AOV网

定义：用一个有向圏表示一个工程的各子工程及其相互制约的关系，其中以顶点表示活动，弧表示活动之间的优先制约关系，称这种有向圈为顶点表示活动的网，简称AOV (Activity On Vertex network)网。

特点

若从i到j有一条有向路径，则i是j的前驱；j是i的后继。

AOV网中不允许有回路，因为如果有回路存在，则表明某项活动以自己为先决条件，显然这是荒谡的。

拓扑排序算法

算法思路

在AOV网络中选一个没有直接前驱的顶点，并输出之；

从图中删去该顶点，同时删去所有它发出的有向边;

重复以上2、3步，直到：全部顶点均已输出，拓扑有序序列形成，拓扑排序完成；若图中还有未输出的顶点，但已跳出处理福环。这说明图中还剩下一些顶点，它们都有直接前驱，再也找不到没有前驱的顶点了。这时AOV网络中必定存在有向环。

执行步骤

在有向图中选一个无前趋的顶点v，输出之；

从有向图中删除v及以v为尾的弧；

重复1、2，直接全部输出全部頂点或有向圏中不存在无前超的結点吋力止

代码实现

AOE网

解决问题：完成整项工程至少需要多少时间，影响工程进度的是哪些关键子工程？

与AOV网比较

AOV网侧重于表示活动的前后次序。

AOE网除了表示活动的先后次序外，还表示了活动的持续时间，因此可利用AOE网解决工程所需最短时间及哪些子工程拖延会影响整个工程按时完成等问题。

实际应用中采用那一种图，取決于要求解的问题。

关键路径

定义

图中的最长路径

操作思路

因此可以设置数组e(earliest)和数组l(latest)，其中e[r]和l[r]分别表示活动ar的最早开始时间和最迟开始时间。于是，当求出这两个数组之后，就可以通过判断e[r] == l[r]是否成立来确定活动r是否是关键活动。

代码操作

最短路径

基本概念

在带权有向图中A点（源点）到达B点（终点）的多条路径中，寻找一条各边权值之和最小的路径，即最短路径。

迪杰斯特拉（Dijkstra）算法

算法思路

设置两点顶点的集合 U和 T ，集合 U中存放已找到最短路径的顶点，集合 T中存放当前还未找到的最短路径的顶点。

初始状态时，集合 U中只包含源点，设为 v0

然后从集合工中选择到源点v0路径长度最短的顶点u加入到集合U中。

集合U 中每加入一个新的顶点u都要修改源点vo带集合工中剩余顶点的当前最短路径值，集合工中各顶点的新的当前最短路径长度值，为原来的当前最短路径长度值与从源点过顶点山到达该顶点的带权路径长度中的较小者。

回到3，此过程不断重复，直到集合工中的顶点全部加入到集合U中为止。

代码实现

弗洛伊德（Floyd）算法

算法思路

初始化矩阵，将所有相邻的节点对应的权值写入矩阵，不相邻的节点对应的权值初始化为inf

初始化结束后，开始进行三重循环，每层循环从第一个节点开始遍历，直至遍历到第n个节点，设最外层循环当前节点为i，中间层循环的当前节点为j，内层循环的当前节点为k，且i≠j≠k。则以节点i为中介点，以节点j为起点，节点k为目标点，判断由起点j经由中介点i到达目标点k的代价值是否小于由起点j直接到目标点k的代价值，若小于，则将从起点j到目标点k的代价值d[j][k]更新为d[j][i]+d[i][k]。三重循环结束后，路径规划结束。

路径规划结束后，图的邻接矩阵D也就更新完成了，如果从Vi到Vj有路可达，则D[i][j]=d，d表示该路的长度；否则D[i][j]=无穷大。定义一个矩阵P用来记录所插入点的信息，P[i][j]表示从Vi到Vj需要经过的点，初始化P[i][j]=j。把各个顶点插入图中，比较插点后的距离与原来的距离，D[i][j] = min( D[i][j], D[i][k]+D[k][j] )，如果D[i][j]的值变小，则P[i][j]=k。在D中包含有两点之间最短道路的信息，而在P中则包含了最短通路径的信息。

工业机器人的基本特性思维导图