数据之间的关系有三种

一对一——线性表

一对多——树

多对多——图

图中存储的各个数据元素被称为顶点而不是节点

各个顶点之间的关系也不一定是双向的(箭头带方向和不带方向)

所以图又可以细分为有向图和无向图


图的基本常识

弧头(终端点):有向图中箭头指向的顶点

弧尾(初始点):有向图中没有箭头的顶点

入度:有向图中箭头指向某一顶点的弧的数量

出度:有向图中箭头远离某一顶点的弧的数量

(V1,V2) 和 <V1,V2> 的区别:

无向图中描述两顶点(V1 和 V2)之间的关系可以用 (V1,V2) 来表示

而有向图中描述从 V1 到 V2 的”单向”关系用 <V1,V2> 来表示

由于图存储结构中顶点之间的关系是用线来表示的

因此 (V1,V2) 还可以用来表示无向图中连接 V1 和 V2 的线,又称为边

同样<V1,V2> 也可用来表示有向图中从 V1 到 V2 带方向的线,又称为弧

集合VR:图中所有顶点关系的集合

路径和回路

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

若路径中各顶点都不重复,此路径又被称为”简单路径”

若回路中的顶点互不重复,此回路被称为”简单回路”(或简单环)

在有向图中,每条路径或回路都是有方向的

权:给每条边或弧赋予一个有意义的实数来表示一定的含义

网:带权的图

子图:由图中一部分顶点和边构成的图


完全图:若图中各个顶点都与除自身外的其他顶点有关系,这样的无向图称为完全图

(个人理解:所有能连的边或所有能连的弧都存在)

具有 n 个顶点的完全图,图中边的数量为 n(n-1)/2

而对于具有 n 个顶点的有向完全图,图中弧的数量为 n(n-1)

稀疏图和稠密图:这两种图是相对存在的,即如果图中具有很少的边(或弧)

此图就称为”稀疏图”;反之,则称此图为”稠密图”

稀疏和稠密的判断条件是:e<nlogn

其中 e 表示图中边(或弧)的数量,n 表示图中顶点的数量

如果式子成立,则为稀疏图;反之为稠密图


连通图(无向图的一种)

两个顶点间存在路径我们可以说他们两个顶点是连通

而对于无向图,如果任意两个顶点都是连通的,那么这个无向图就被称为连通图

若无向图不是连通图,但图中存储某个子图符合连通图的性质,则称该子图为连通分量

连通分量的提出是以”整个无向图不是连通图”为前提的

因为如果无向图是连通图,则其无法分解出多个最大连通子图

因为图中所有的顶点之间都是连通的

强连通图(有向图的一种)

有向图中,若任意两个顶点 Vi 和 Vj,满足从 Vi 到 Vj 以及从 Vj 到 Vi 都连通

也就是都含有至少一条通路,则称此有向图为强连通图

与此同时,若有向图本身不是强连通图

但其包含的最大连通子图具有强连通图的性质

则称该子图为强连通分量


生成树

对连通图进行遍历,过程中所经过的边和顶点的组合可看做是一棵普通树,通常称为生成树

a是一张连通图,b是对应的生成树

一张连通图往往有几种不同的生成树

连通图的生成树必须满足以下条件:

  • 包含连通图中的所有顶点
  • 任意两顶点之间有且只有一条通路

因此生成树中 边的数量 = 顶点数 – 1

生成森林

生成树是对应连通图来说,而生成森林是对应非连通图来说的

非连通图可以分解为多个连通分量,每个连通分量都有生成树

那么多棵生成树就组成了生成森林


图的顺序存储结构

图结构虽然是一种多对多关系,但仍然可以使用数组来存储图

存储时我们需要有两个数组

一个存放图中顶点本身的数据(一维数组)

一个存储各顶点之间的关系(二维数组)

不同类型的图存储的方式不同

根据图有无权可以分为两类:图(不带权)和网(带权)

在使用二维数组存储图中顶点之间的关系时,如果顶点之间存在边或弧

在相应位置用 1 表示,反之用 0 表示

如果使用二维数组存储网中顶点之间的关系,顶点之间如果有边或者弧的存在

在数组的相应位置存储其权值,反之用 0 表示


图的邻接表存储法

在图中如果两个顶点相互连通,则称他们互为邻接点

邻接指的是图中顶点之间有边或者弧的存在

给图中所有顶点每个顶点建立一个链表

用节点存储这个顶点,用剩下的节点存储各自的邻接点

一般的节点是这样划分的data存放数据,next链接下一个节点

如果遇到网,则需要加一个数据域来存放权

邻接表计算顶点的出度和入度

出度可以直接计算链表中节点的数量得到

入度比较复杂有两种方式:

1.遍历整个邻接表中的节点,统计数据域与该顶点所在数组位置下标相同的节点数量就是入度

2.建立一个逆邻接表,该表中的各顶点链表专门用于存储以此顶点为弧头的所有顶点在数组中的位置下标。


图的十字链表存储法

与邻接表不同,十字链表法仅适用于存储有向图和有向网

改善了邻接表计算图中顶点入度的问题

首元节点(a1)和其它节点的节点结构不一样

首元节点如下

  • firstin 指针用于连接以当前顶点为弧头的其他顶点构成的链表
  • firstout 指针用于连接以当前顶点为弧尾的其他顶点构成的链表
  • data 用于存储该顶点中的数据

其它节点如下

  • tailvex 用于存储以首元节点为弧尾的顶点位于数组中的位置下标
  • headvex 用于存储以首元节点为弧头的顶点位于数组中的位置下标
  • hlink 指针:用于链接下一个存储以首元节点为弧头的顶点的节点
  • tlink 指针:用于链接下一个存储以首元节点为弧尾的顶点的节点
  • info 指针:用于存储与该顶点相关的信息,例如量顶点之间的权值


图的邻接多重表存储法

适用于无向图的存储

可看作是邻接表和十字链表的结合

为图中的各个顶点建立一张链表

存储各顶点的节点作为各链表的首元节点

同时为了便于管理将各个首元节点存储到一个数组中

data:存储此顶点的数据

firstedge:指向同该顶点有直接关联的存储其他顶点的节点

mark:标志域,用于标记此节点是否被操作过,例如在对图中顶点做遍历操作时,为了防止多次操作同一节点,mark 域为 0 表示还未被遍历;mark 为 1 表示该节点已被遍历

ivex 和 jvex:数据域,分别存储图中各边两端的顶点所在数组中的位置下标

ilink:指针域,指向下一个存储与 ivex 有直接关联顶点的节点

jlink:指针域,指向下一个存储与 jvex 有直接关联顶点的节点

info:指针域,用于存储与该顶点有关的其他信息,比如无向网中各边的权

存储的结构如下


图的遍历

深度优先搜索(DFS)

类似于树的先序遍历

从图中的一个顶点出发,每次遍历当前访问顶点的临界点

一直到访问的顶点没有未被访问过的临界点为止

然后采用依次回退的方式,查看来的路上每一个顶点是否有其它未被访问的临界点

访问完成后,判断图中的顶点是否已经全部遍历完成

如果没有,以未访问的顶点为起始点,重复上述过程

是一个不断回溯的过程

上图的遍历顺序就是 1 2 4 8 5 3 6 7

广度优先搜索

类似于树的层次遍历

从图中的某一顶点出发,遍历每一个顶点时,依次遍历其所有的邻接点

然后再从这些邻接点出发,同样依次访问它们的邻接点

按照此过程,直到图中所有被访问过的顶点的邻接点都被访问到

上图的遍历顺序就是 1 2 3 4 5 6 7 8

在程序中需要借助队列这一数据结构来帮助完成计算


前面我们提到过生成树和生成森林的概念

对无向图进行遍历的时候

遍历过程中所经历过的图中的顶点和边的组合就是图的生成树或者生成森林

我们刚刚提到了两种遍历的方法,因此衍生出了两种不同的生成树

我们对上面提到的例子的边赋予记号

深度优先时可以得到的遍历顺序如下

深度优先生成树如下

同理,广度优先生成树就长下面这样


我们前面讲树的时候提到过带权问题

图同样有这类问题的存在

假入几座城市的电网有很多种修法

我们可以转化为一个图的带权问题

求生成树权值和的最小值

我们会使用权值为7的两种方案

也就是求最小生成树

通常我们会使用下面的两种算法

普里姆算法(Prim)

把顶点分成两类

一类是被划到生成树里的顶点——A类

一类是没有划到生成树的顶点——B类

一开始大家肯定都是B类,所以随便选一个

现在图上就会有A类和B类的区别了

现在开始找A类到B类权值最小的边

也就是A类里A到B类里BCD三个顶点里面权最小的那条边

连起来后顶点B就从B类划到A类去了

以此类推

经过几次寻找A类到B类权值最小的边直到所有的顶点都划到A类

这棵树就是这张图的最小生成树了

普利姆算法适合解决稠密的网,算法的时间运行复杂度为n^2

克鲁斯卡尔算法(Kruskal)

和普里姆相反适合解决稀疏的网的问题

将所有边按照权值的大小进行升序排序,然后从小到大一一判断

如果这个边不会与之前选择的所有边组成回路,就可以作为最小生成树的一部分

反之,舍去。直到具有 n 个顶点的连通网筛选出来 n-1 条边为止

筛选出来的边和所有的顶点构成此连通网的最小生成树

以上题为例

把所有的权值列一个集合2、2、3、3、4

四个顶点需要三条边,同时又要满足条件

那先找集合里最小的权2

然后把这个2移出集合

再找移除2后集合里最小的权2

然后把2移出集合

此时因为集合里有两个3,所以你有两种选择使其权值最小


最短路径

树里貌似也提到过这个东西

一个顶点到另外一个顶点所经过的边数就是路径

那么最短路径就如同字面意思

如果是带权图的话,那么最短路径的权的和就是最短路径长度

狄克斯特拉算法(Dijkstra)

用来解决有向图的最短路径问题(当然无向图一样可以用这个方法计算)

如果要找V0到其它顶点的最短路径

先做统计,能直接到的权值就是需要花费的值,不能直接到的通通按无穷大处理

0到2和0到5和0到4三条是直接到达的,就分别花费10和100和30,剩下的全是无穷大

第一步:先找花费最小的

这里花费最小的就是0到2了没啥好说的

第二步:谁小从谁走,然后加上第一步的权值

2成为了新的起点,2到除0以外的其它顶点计算花费

这里能直接到达的顶点花费需要加上0到2的权值

不能直接到达的顶点还是全按无穷大来处理

2能直接到达的就只有3,现在的权值和就为10+50 = 60

更新权值后和第一步剩余的两个权值比较,60,30,100

此时我们发现30是里面最小的,所以我们切换顶点到4

第三步:重复第二步

4只有一条通路20可以到达3

更新后的权值是30+20=50

和第二步更新的权值60还有第一步剩余的未更新的权值100进行比较

此时仍然还是最小,所以就继续从3出发

第四步:重复第二步

3就一条通路10到达5

更新后的总权值是60并且也没有其它新的点可以走了

遍历到这里就结束了,你发现只有1和0还没有通路

此时把0到1当作无穷大进行处理

所以最后0到各顶点的最短路径分别如下

总结一下就是不断更新点的过程

这个东西理解起来会稍微有点绕

所以可以用表格来帮助理解


弗洛伊德算法(Floyd)

另外一种计算顶点间最短路径的方法

使用了动态规划的思想

和迪杰斯特拉算法的时间复杂度都是一样的(n^3)

但是实现形式会比较的直白一点

弗洛伊德算法中认为最短路径只有两种情况

一是 直接从A到B的弧的权值是A到B的最短路径

二是 A到B经过的弧的权值的和是A到B的最短路径

所以A到B的最短路径就把所有顶点都拿出来判断

Dis(A,K)+ Dis(K,B)< Dis(A,B)

拿出所有的顶点 K,判断经过顶点 K 是否存在一条可行路径比直达的路径的权值小

如果式子成立,说明确实存在一条权值更小的路径,此时只需要更新记录的权值和即可

当任意两个顶点都比较过了最终更新后的权值就是最短路径

我们还是可以用刚刚那题来举例

0到1,没有任何一条可以找到的通路,直接当无穷大处理

0到2,只有10一条通路,最后值就是10

0到3,10+50和30+20两条通路,那肯定是50的比较小

0到4,只有30一条通路,最后值就是30

0到5,100/30+60/30+20+10/10+50+10,最后值是60

这是用最白的白话来讲弗洛伊德算法所做的事情

但是实际上程序里并不能这么直观的理解


拓扑排序

拓扑序列是一个有向无环图的所有顶点的线性序列

有向无环图就是图中没有回路的图

在一个有向图中找一个拓扑序列的过程称为拓扑排序

在有向无环图中,弧的方向代表着顶点之间的先后次序

例如从 V1 指向 V2 的弧表示在进行排序时 V1 在前, V2 在后

拓扑排序需要遵循两个原则:

  • 在图中选择一个没有前驱的顶点 V
  • 从图中删除顶点 V 和所有以该顶点为尾的弧

所以上图有两种拓扑排序

1 2 3 4

1 3 2 4

在现实生活中,我们常常会遇到一些带有先前条件的问题

完成某一件事需要先把另一件事完成

例如你只有先往水壶里倒水才能烧水

像这样用来表示某种活动间的优先关系的有向图简称为AOV网

顶点代表了活动,弧表示活动之间的优先关系


AOE网

和AOV的区别在于多了权

顶点表示事件,弧表示活动,权表示活动所需要的时间

入度为0的点为开始事件(源点)

出度为0的点为结束事件(汇点)

从源点到汇点的所有路径中具有最大路径长度的路径称为关键路径

AOE和AOV都是用来工程建模的

但是两者其实大有不同

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注