数据结构与算法之图
寜静致逺 Lv3

图的基本概念

图由结点的有穷集合V和边的集合E组合。为了与树形结构进行区别,在图结构中常常将结点称为顶点,边是顶点的有序偶对。若两个顶点之间存在一条边,则表示这两个顶点具有相邻关系。

1.有向图和无向图

(有向图)
(无向图)

2.入度和出度
对于有向图中的一个顶点 V 来说,箭头指向 V 的弧的数量为 V 的入度(InDegree,记为 ID(V));箭头远离 V 的弧的数量为 V 的出度(OutDegree,记为OD(V))。拿图 2 中的顶点 V1来说,该顶点的入度为 1,出度为 2(该顶点的度为 3)。

3.(V1,V2) 和 <V1,V2> 的区别
无向图中描述两顶点(V1 和 V2)之间的关系可以用 (V1,V2) 来表示,而有向图中描述从 V1 到 V2 的”单向”关系用 <V1,V2> 来表示。
由于图存储结构中顶点之间的关系是用线来表示的,因此 (V1,V2) 还可以用来表示无向图中连接 V1 和 V2 的线,又称为边;同样,<V1,V2> 也可用来表示有向图中从 V1 到 V2 带方向的线,又称为弧。

4.集合 VR 的含义
并且,图中习惯用 VR 表示图中所有顶点之间关系的集合。例如,图 1 中无向图的集合 VR={(v1,v2),(v1,v4),(v1,v3),(v3,v4)},图 2 中有向图的集合 VR={<v1,v2>,<v1,v3>,<v3,v4>,<v4,v1>}。

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

6.简单路径
序列中顶点不重复出现的路径称为简单路径。

7.权和网的含义
在某些实际场景中,图中的每条边(或弧)会赋予一个实数来表示一定的含义,这种与边(或弧)相匹配的实数被称为”权”,而带权的图通常称为网。如图所示,就是一个网结构:

(带权的图存储结构)

8.子图
指的是由图中一部分顶点和边构成的图,称为原图的子图。

9.完全图
若图中各个顶点都与除自身外的其他顶点有关系,这样的无向图称为完全图(如图 a)。同时,满足此条件的有向图则称为有向完全图(如图b)

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

连通图

图中从一个顶点到达另一顶点,若存在至少一条路径,则称这两个顶点是连通着的。例如图 1 中,虽然 V1 和 V3 没有直接关联,但从 V1 到 V3 存在两条路径,分别是 V1-V2-V3 和 V1-V4-V3,因此称 V1 和 V3 之间是连通的。

(图 1 顶点之间的连通状态示意图)
无向图中,如果任意两个顶点之间都能够连通,则称此无向图为连通图。例如,图 2 中的无向图就是一个连通图,因为此图中任意两顶点之间都是连通的。
(图 2 连通图示意图)

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

强连通图

有向图中,若任意两个顶点 Vi 和 Vj,满足从 Vi 到 Vj 以及从 Vj 到 Vi 都连通,也就是都含有至少一条通路,则称此有向图为强连通图。如图 4 所示就是一个强连通图。

(图 4 强连通图)
与此同时,若有向图本身不是强连通图,但其包含的最大连通子图具有强连通图的性质,则称该子图为强连通分量。
(图 5 强连通分量)
如图 5 所示,整个有向图虽不是强连通图,但其含有两个强连通分量。

可以这样说,连通图是在无向图的基础上对图中顶点之间的连通做了更高的要求,而强连通图是在有向图的基础上对图中顶点的连通做了更高的要求。

邻接矩阵

邻接矩阵是图的顺序存储结构。由邻接矩阵的行数或列数可知图中的顶点数。

邻接表

邻接表是图的一种链式存储结构。所谓邻接表就是对图中的每个顶点i建立一个单链表,每个单链表的第一个结点存放有关顶点的信息,把这一结点看作链表的表头,其余结点存放有关边的信息。因此,连接表由单链表的表头形成的顶点表和单链表其余结点形成的边表两部分组成。一般定点表存放顶点信息和指向由第一个边结点指针,边表结点存放与当前顶点相邻顶点的序号和指向下一个边结点的指针。

十字链表

十字链表是有向图的另一种链式存储结构。我们也可以把它看成是有向图的邻接表和逆邻接表结合起来形成的一种链表。

有向图的每一条弧对应十字链表中的一个弧结点,同时有向图中的每个顶点在十字链表中对应有一个结点,叫做顶点结点

邻接多重表

深度优先遍历

广度优先遍历

生成树

所有顶点均有边连接起来,但不存在回路的图。
对连通图进行遍历,过程中所经过的边和顶点的组合可看做是一棵普通树,通常称为生成树。

(连通图及其对应的生成树)

一个图可以有许多棵不同的生成树。

所有生成树具有以下共同特点

  • 生成树的顶点个数与图的顶点个数相同;
  • 生成树是图的极小连通图,去掉一条边则非连通;
  • 一个有n个顶点的连通图的生成树有n-1条边;
  • 在生成树中再添加一条边必须形成回路。

最小生成树:

给定一个无向网络,在该网的所有生成树中,使得各边权值之和最小的那棵生成树称为该网的最小生成树,也叫最小代价生成树。

由于最小生成树本身是一棵生成树,所以需要时刻满足以下两点:

  • 生成树中任意顶点之间有且仅有一条通路,也就是说,生成树中不能存在回路;
  • 对于具有 n 个顶点的连通网,其生成树中只能有 n-1 条边,这 n-1 条边连通着 n 个顶点。

普里姆算法从顶点的角度为出发点,时间复杂度为O(n2),更适合与解决边的绸密度更高的连通网。
克鲁斯卡尔算法从边的角度求网的最小生成树,时间复杂度为O(eloge)。和普里姆算法恰恰相反,更适合于求边稀疏的网的最小生成树。

普里姆(Prim)算法

从图中任意取出一个顶点,把它当成一棵树,然后从与这棵树相接的边中选取一条最短(权值最小)的边,并将这条边及其所连接的顶点也并入这棵树中,此时得到了一棵有两个顶点的树。然后从与这棵树相连的边中选取一条最短的边,并将这条边及其所连顶点并入当前树中,得到一棵有3个顶点的树。以此类推,直到图中所有顶点都被并入树中为止,此时得到的生成树就是最小生成树。

克鲁斯卡尔(Kruskal)算法

(图一 连通图)

例如,使用克鲁斯卡尔算法找图 1 的最小生成树的过程为:

首先,在初始状态下,对各顶点赋予不同的标记(用颜色区别),如下图所示:

(1)

对所有边按照权值的大小进行排序,按照从小到大的顺序进行判断,首先是(1,3),由于顶点 1 和顶点 3 标记不同,所以可以构成生成树的一部分,遍历所有顶点,将与顶点 3 标记相同的全部更改为顶点 1 的标记,如(2)所示:

(2)

其次是(4,6)边,两顶点标记不同,所以可以构成生成树的一部分,更新所有顶点的标记为:

(3)

其次是(2,5)边,两顶点标记不同,可以构成生成树的一部分,更新所有顶点的标记为:

(4)

然后最小的是(3,6)边,两者标记不同,可以连接,遍历所有顶点,将与顶点 6 标记相同的所有顶点的标记更改为顶点 1 的标记:

(5)

继续选择权值最小的边,此时会发现,权值为 5 的边有 3 个,其中(1,4)和(3,4)各自两顶点的标记一样,如果连接会产生回路,所以舍去,而(2,3)标记不一样,可以选择,将所有与顶点 2 标记相同的顶点的标记全部改为同顶点 3 相同的标记:

(6)

当选取的边的数量相比与顶点的数量小 1 时,说明最小生成树已经生成。所以最终采用克鲁斯卡尔算法得到的最小生成树为(6)所示。

最短路径

两种常见的最短路径问题:
一、单源最短路径——用Dijkstra(迪杰斯特拉)算法
二、所有顶点间的最短路径——用Floyd(弗洛伊德)算法

Dijkstra(迪杰斯特拉)算法

Floyd(弗洛伊德)算法

  • 本文标题:数据结构与算法之图
  • 本文作者:寜静致逺
  • 创建时间:2021-01-22 17:17:43
  • 本文链接:https://hujiahao6.gitee.io/2021/01/22/图/
  • 版权声明:本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!
 评论