数据结构【七】:图

需要知道的图的相关基本概念


  • 无向图

  • 有向图

  • 度、出度、入度

  • 边和弧:无向图中边就叫边,有向图中边叫做弧,还有弧头和弧尾之分,带箭头一端为弧头。

  • 路径和回路:从一个顶点到另一顶点途径的所有顶点组成的序列(包含这两个顶点),称为一条路径。如果路径中第一个顶点和最后一个顶点相同,则此路径称为”回路”(或”环”)。

    • 简单路径(回路):顶点不重复的路径(回路)
  • 完全图:无向图中任意两个点之间都有边,有向图中任意两个点有互相通往对方的弧

    • 具有 n 个顶点的完全图,图中边的数量为 n(n-1)/2;而对于具有 n 个顶点的有向完全图,图中弧的数量为 n(n-1)。
  • 稀疏图和稠密图:边数e<nlogn为稀疏图反之为稠密图

  • 简单图:无重复的边或顶点到自身的边

  • 连通图:无向图中,如果任意两个顶点之间都能够连通

    • 连通分量:若无向图不是连通图,但图中存储某个极大子图符合连通图的性质,则称该子图为连通分量。
  • 强连通图:有向图中,任意两个顶点之间能够连通

    • 强连通分量:若有向图不是连通图,但图中存储某个极大子图符合强连通图的性质,则称该子图为强连通分量。
  • 网:图上的边或弧带有权则称为网。

  • 生成树:无向图中连通且n个顶点n-1条边称为生成树。有向图中一顶点入度为0其余顶点入度为1的叫有向树。一个有向图由若干棵有向树构成生成森林。

图的存储结构


1.邻接矩阵存储

(1)图象理解

(2)语言构造

根据图象理解,我们可以在类中动态定义一个一维数组存储节点,一个二维数组存储邻接矩阵

2.邻接表存储

(1)图象理解

若为有权图,则需要在结点中添加代表权值的变量

根据图象理解,我们先定义两个结构体节点,一个为邻接表的结点,一个为邻接表中存储其联通关系的链表结点。

参考文章:

数据结构—图的详细介绍

大话数据结构-图

图的遍历(DFS和BFS)


1、Depth First Search深度优先探索

所以我们DFS分两个函数主要是因为这个辅助数组一般方式下不能放入递归函数体中,不然每次都会创建

2、Breadth First Search广度优先探索

BFS可以在一个过程中完成,分两部分是为了解决多连通分量的情况,利用同DFS

注意:1、DFS和BFS的主函数其实是一样的,区别在于子过程2、判断结点信息只需要在主过程判断一次传进来的点位置就可以了,因为子过程调用一定是正确的存在的点位置

#### 3、补充

无论是BFS还是DFS,设n个点e个边,用邻接矩阵作存储结构,查找每一个顶点的邻接点所需时间为O(n),遍历图的时间复杂度为O(n2)。用邻接表作存储结构,查找所有的邻接点所需时间为O(e),每个顶点仅被访问1次即所需时间为O(n)遍历图的时间复杂度为O(n+e) 。

- 利用 DFS 或 BFS 可以获取图的生成树

推荐阅读

图的遍历之 深度优先搜索和广度优先搜索

最小生成树


Kruskal算法

Prim算法

推荐阅读

最小生成树-Prim算法和Kruskal算法

最短路径


1、求一点到其他点的最短路径(单源最短路径)

①Dijkstra算法

复杂度O(n2)

注意:Dijkstra算法不能允许权值为负

推荐阅读

深入理解 Dijkstra 算法实现原理

最短路径问题—Dijkstra算法详解

②bellman-ford算法

注意:bellman-ford算法允许权值为负

3、求任意两点的最短路径

①Floyd算法

傻子也能看懂的弗洛伊德算法(转)

复杂度O(n3)

注意: 通常可以在任何图中使用,包括有向图、带负权边的图。但是不能有带负权的边组成的回路

AOV(Activity On Vertices)网络和拓扑排序


1、AVO网络

活动网络可以用来描述生产计划、施工过程、生产流程、程序流程等工程中各子工程的安排问题。 一般一个工程可以分成若干个子工程,这些子工程称为活动(Activity)。完成了这些活动,整个工程就完成了。

我们可以用上图的有向图来表示课程之间的先修关系。在这种有向图中,顶点表示课程学习活动,有向边表示课程之间的先修关系。例如顶点C1到C8有一条有向边,表示课程C1必须在课程C8之前先学习完。

实际上,在这种有向图中,用顶点表示活动,用有向边表示活动u必须先于活动v进行。这种有向图叫做活动网络(Activity on Vertices),记做AOV网络。

前驱与后继:在AOV网络中,如果存在有向边,则称活动u必须在活动v之前进行,并称u是v的直接前驱,v是u的直接后继。如果存在有向路径,则称u是v的前驱,v是u的后继。

有向环与有向无环图:从前驱与后继的传递性和反自反性可以看出,AOV网络中不能出现有向回路(或称为有向环)。不含有向回路的有向图称为有向无环图(DAG, Directed Acyclic Graph)。

在AOV网络中如果出现了有向回路,则意味着某项活动以自己作为先决条件,这是不对的。

2、拓扑排序

1、判断有向无环图的方法是对AOV网络构造它的拓扑有序序列(Topological Order Sequence);

2、构造这种AOV网络全部顶点的拓扑有序序列的运算称为拓扑排序,即将各个顶点排列成一个线性有序的序列,使得AOV网络中所有存在的前驱和后继关系都能得到满足。

3、一个AOV网络的拓扑有序序列可能不是唯一的;

4、拓扑排序实现方法:

(1)从AOV网络中选择一个入度为0(即没有直接前驱)的顶点并输出;

(2)从AOV网络中删除该顶点及该顶点发出的所有边;

(3)重复步骤(1)和(2),直至找不到入度为0的顶点。

经过上述步骤后,有两种结果:(1)所有的顶点都被输出,也就是整个拓扑排序完成了;(2)仍有顶点没有被输出,只剩下入度不为0的顶点,即存在有环图。

摘选自:

AOV网络和Kahn算法拓扑排序

AOV网络与拓扑(一)

AOE(Activity On Edge)网络与关键路径


1、AOE网络

AOE网的基础概念

定义:如果在无环的带权有向图中用有向边表示一个工程中的活动用边上的权值表示活动的持续时间用顶点表示事件则这样的有向图叫做用边表示活动的网络,简称AOE网络

一定要注意:AOV网中,点代表活动,AOE网中边代表活动两者是不同的。

实践和活动的理解,AOE网中边为活动,点为事件,可理解事件是一个“检查点”,它是一种“状态”,只有“检查”到通向该事件的活动全部完成的状态,才能进入下面的活动

  • AOE网中没有入边的顶点称为始点
  • AOE网中没有出边的顶点称为终点

AOE网的性质

1、只有进入某顶点的各活动都结束,该顶点所代表的事件才能发生

2、只有某顶点所代表的事件发生后,从该顶点出发的各活动才能开始

AOE网的应用

AOE在工程方面非常有用:

例如:

(1)完成整个工程至少需要多少时间(假设没有环);

(2)为缩短完成工程所需时间,应当加快那些活动

因为在工程当中,很多活动是并行的,所以有些活动是导致工期长短的关键活动,不能拖延,而有些活动是可以在一定范围内延迟的,这是计算关键路径的原因!

2、关键路径

关键路径的相关概念

从源点到各个顶点,以至从源点到汇点的有向路径可能不止一条。这些路径的长度也可能不同,完成不同路径的活动所需时间不同,但只有各条路径上所有活动都完成了,整个工程才完成。完成整个工程所需时间取决于从源点到汇点的最长路径长度,即在该路径上所有活动的持续时间之和,给路径称为关键路径

为了找出关键路径,必须找出关键活动,即不按期完成就会影响整个工程完成的活动

关键路径上的所有活动都是关键活动。

四个和计算关键路径相关的量

  • 事件最早可能开始时间Ve[k]:求法为源点到该顶点的最大长度,需要正向计算取大得出
  • 事件最迟允许开始时间Vl[k]:需要逆向计算取小得到
  • 活动最早开始时间e[i]:活动代表的是边,它的最早开始时间和它作为某个点出度的事件的最早开始时间相同
  • 活动的最晚开始时间l[i]:通过该边作为入度指向的事件的最晚触发事件逆向计算得到

计算关键路径

计算各个活动的时间余量l[k]-e[k],时间余量为0即(l[k]=e[k])者为关键活动

多个或一个活动的完成才能决定一个事件的触发,它取决于触发事件的活动中最长的一个,我们从始点开始计算每个事件的最早开始时间,也就是计算每个点相对始点的最大路径,一直计算到终点,就计算出了完成工程的最早时间,通过工程完成的最早时间我们能逆推每个事件完成的最晚时间,然后通过每个事件得出每个工程的最晚开始时间

**通过最大路径计算得到每个事件的最早发生时间-->最终得到工程完成最早时间(终点事件的触发时间)-->逆推每个事件的最晚触发时间-->通过每个事件的最晚触发时间能逆推每个活动的最晚开始时间-->比较每个活动的最早开始时间(由相关量性质可知,计算过事件的最早发生时间,活动的最早发生时间也就确定了)和最晚开始时间,没有时间余量的活动为关键活动-->解决为缩短工期能够加快那些活动的问题(只有加快关键活动才能加快进程,但是值得注意的是,我们只能在现实中尽快督促完成,若是理想化直接提前很长时间完成关键活动,实际上AOE网就会改变,关键路径也就不一定是原样了)**

例:

第一步:

事件a最早发生时间:0 同时得到:活动(a,b)最早发生时间=活动(a,c)最早发生时间=事件a最早发生时间=0

事件b最早发生时间:4 同时得到:活动(b,d)最早发生时间=事件b最早发生时间=4

事件c最早发生时间:3 同时得到:活动(c,d)最早发生时间=事件c最早发生时间=3

事件d最早发生时间:8

第二步(没有体现出一个事件引起多个活动的情况的最晚时间,但是我们要知道肯定是取最晚时间中最早的那个):

事件d最晚发生时间:8

事件b最晚发生时间:6

事件c最晚发生时间:3

第三步:

活动(b,d)最晚发生时间:6

活动(c,d)最晚发生时间:3

活动(a,b)最晚发生时间:2

活动(a,c)最晚发生时间:0

第四步:

活动(a,c)最晚发生时间-活动(a,c)最早发生时间=0-0=0

活动(a,b)最晚发生时间-活动(a,b)最早发生时间=2-0=2

活动(c,d)最晚发生时间-活动(c,d)最早发生时间=3-3=0

活动(b,d)最晚发生时间-活动(b,d)最早发生时间=6-4=2

所以,关键路径为a->c->d,关键活动为(a,c)、(c,d)

注意:1、关键路径可能有多条2、并不是改变任何一个关键活动的时间都可以改变总时间

-----------------------本文结束 感谢阅读-----------------------
坚持原创技术分享,您的支持将鼓励我继续创作!恰饭^.^~