算法 图相关知识

算法——图

图结构

图的基本概念

图是由顶点的非空集合V(有n>0个顶点组成)与边的集合E(顶点之间的关系)构成,常用G表示,可形式化定义如下:G=(V,E)
如果图中的边集E中每一条边都没有方向性,则该图为无向图;如果E中的边具有方向性,则表示该图为有向图。无序图的边表示为无序偶对(Vi, Vj), 所以(Vi, Vj)和(Vj, Vi)是同一条边。
有向图的表示的是顶点的有序偶对,边$\langle$Vi, Vj$\rangle$和$\langle$Vj, Vi$\rangle$是两条不一样的边。


  1. 一个顶点的度指依附于某顶点V的边的条数,通常记为TD(V)
  2. 路径
    顶点的路径是指一个顶点Vi到另一个顶点Vj之间所经过的存在边的顶点的序列。
    举例来说,如果存在顶点序列 V1, V2, V3, V4, …, Vm,使得顶点偶对(Vi, Vi+1) $\in$ (i=1, 2, 3, …, m–1),则称该顶点序列为顶点V1到Vm之间的一条路径。如果V1=Vm,则该路径成为回路或环。
  3. 子图
    图G=(V, E)和G’=(V’, E’),如果存在V’$\in$V 且 E’ $\in$ E,则称G’为G的一个子图
  4. 图的连通
    在无向图中,如果顶点Vi到Vj(i!=j)存在路径,则称Vi和Vj是连通的。如果某无向图中任意两个顶点都是连通的,则称该无向图是连通图,否则为非连通图。无向图中的极大连通子图为该图的连通分量。
    在有向图中,如果任意两个不同的顶点都是连通的,则称该有向图为强连通图,其极大连通子图为强连通分量。

    无向图和有向图

图的存储结构

图主要有邻接表存储结构和邻接矩阵存储结构两种。

邻接矩阵存储

邻接矩阵存储(数组存储法),核心思想是使用两个数组存储一个图。具体定义如下:一个具有n个顶点的图,将每个顶点存储在数组Vertex[0…n-1]中,另定义一个二维数组E[0…n-1][0…n-1]存储相邻顶点见的关系,该二维矩阵称为邻接矩阵。
在数组Vertex中的下标来表示一个顶点,则邻接数组元素E[i][j]就表示Vi和Vj之间的关系,如果存在边,则为1,如不存在则为0。
无向图的矩阵是一个对称矩阵,矩阵中的值表示两者之间有直接边可到达。如果是有权图则数组存储权值,无边的顶点之间权值为$\infty$.
邻接矩阵不适合存储稀疏图,会有很多存储空间是空值,浪费空间。

图a使用邻接矩阵表示:

图的邻接矩阵存储

邻接表存储

邻接表存储利用链表的优势,解决了邻接矩阵不适合存储稀疏图的问题。
邻接表存储法为每个顶点建立一条线性链表,如果图中有n个顶点,则其邻接表结构有n个线性表组成,每个链表设置一个头结点,称为顶点结点。
每一个链表中的结点称为边结点。

图b使用邻接表表示:

图的邻接表存储

图的遍历

深度优先遍历

图的深度优先遍历(Deepth First Search,DFS),从顶点v出发,首先将顶点v自己标记为已到达顶点,然后选择一个和v邻近的顶点u,如果u不存在则停止遍历,如果顶点存在则将u顶点标记为已到达,选择一个顶点u的未到达顶点w开始新一轮DFS。

广度优先遍历

图的广度优先遍历,从顶点v出发,访问v之后依次访问v的各个未被访问的邻接点,然后从这些邻接点出发访问其它未被访问过的点,直到所有点访问完成。

示例代码 https://github.com/CaseZheng/Study/tree/master/Algorithm/Chart

图的高级算法

拓扑排序

拓扑排序是有向无环图的重要应用,将单向连接的事件按照其关系方向排列成一个具有先后顺序的线性结构。

  1. 偏序。偏序是一种非自反性的传递关系。用R表示元素间的关系,偏序的定义是非自反性,即不存在sRs的关系,如果sRt表示存在s到t的关系R,则必不存在tRs,说明偏序具有非对称性。如果存在关系sRt,tRu,则必存在sRu,说明偏序具有关系传递性。拓扑排序是在有向无环图这种偏序关系上的一种算法。
  2. 全序。全序关系T是一个偏序,并且对于集合中所有的元素s$\neq$t,sTt和tTs只能取其一。
  3. 有向无环图(DAG图)。一种特殊的有向图,从该图的任一结点出发,经过若干条边,无法回到该顶点。这样的图是无环的。

拓扑排序是在有向无环图上进行的操作,对于一个有向无环图G,拓扑排序将图G的所有顶点排成一个线性序列,使图中任意一对顶点v和u,满足如果图中存在关系v->u,则排序后顶点v必在u的左边。

示例代码 https://github.com/CaseZheng/Study/tree/master/Algorithm/Chart

最小生成树

算法描述:最小生成树是指在一个具有N个顶点的带权连通图G中,如果存在某个子图G’,其包含图G的所有顶点和一部分边,且不形成回路,并且子图G’的个边权值最小,则称图G’是图G的最小生成树。

最小生成树

  1. 最小生成树不能有环
  2. 最小生成树不一定唯一,在一个图中最小生成树可以有一个或多个
  3. 最小生成树边的个数等于顶点数减一,即|E|=|V|-1
  4. 最小生成树的边的权值最小

Kruskal算法

核心思想:在带权连通图中,不断地在边集中找到最小的边,如果该边满足得到最小生成树的条件,就将其构造,直到最后得到一颗最小生成树。

Prim算法

核心思想:在带权连通图中,图的顶点集合为V,从图中某个顶点v开始,得到集合U={v},重复执行下述操作:在所有u$\in$U,w$\in$V-E的边(u,w)$\in$E中找到最小的边,将(u,w)这条边加入到已找到的边集合,并将点w加入到集合U中,当U=C时,就找到了最小生成树。

参考书籍

  1. 妙趣横生的算法(C++语言实现)