推荐|数据结构学习笔记（6-8）：图

附录：所有blog的链接

数据结构学习笔记（1）：基本概念
 数据结构学习笔记（2）：线性结构
 数据结构学习笔记（3-5）：树
 数据结构学习笔记（6-8）：图
 数据结构学习笔记（9-10）：排序
 数据结构学习笔记（11）：散列查找
 数据结构学习笔记（12）：综合习题选讲

第六讲图（上）

6.1 什么是图

定义：

表示多对多的关系

包含

一组顶点：通常用 $V$ （Vertex）表示顶点集合

一组边：通常用 $E$ （Edge）表示边的集合

无向边是顶点对： $(v,w)\in E$ ，其中 $v,w\in V$
有向边 $< v, w >$ 表示从 $v$ 指向 $w$ 的边（单行线）O-W
默认不考虑重边（无向边顶点相同的两条）和自回路（定点重点均是自己）

抽象数据类型定义

类型名称：图（Graph）

数据对象集： $G (V, E)$ 由一个非空的有限顶点集合 $V$ 和一个有限边集合 $E$ 组成（必须要由顶点）。

操作集：对于任意图 $\in Graph$ ，以及 $v\in V$ ， $\in E$

Graph Create（）：建立并返回空图；
Graph InsertVertex（Graph G，Vertex v）：将v插入G；
Graph InsertEdge（Graph G，Edge e）：将e插入G；
void DFS（Graph G，Vertex v）：从顶点v出发深度优先遍历图G；
void BFS（Graph G，Vertex v）：从顶点v出发宽度优先遍历图G；
void Shortestpath（Graph G，Vertex v，int Dist[]）：计算图G中顶点v到任意其他顶点的最短距离；
void MST（Graph G）：计算图c的最小生成树；
…

常见术语

有向图、无向图、网络（带权重的图）

图的表示

邻接矩阵表示法

没有自回路=>所以对角线是0

对于无向图有一半的空间被浪费=>右上角的左下角，被表示了两遍

备注：网络中有权重没有边相连的时候是否可以用0表示权重需要具体考量

优势：

直观、简单、好理解

方便检查任意一对顶点间是否存在边

方便找任一顶点的所有“邻接点”（有边直接相连的顶点）

方便计算任一顶点的“度”（从该点发出的边数为“出度”，指向该点的边数为“入度”）

无向图：对应行（或列）非0元素的个数
有向图：对应行非0元素的个数是“出度”；对应列非0元素的个数是“入度”

劣势：

浪费空间—存稀疏图（点很多而边很少）有大量无效元素对稠密图（特别是完全图）还是很合算的

浪费时间—统计稀疏图中一共有多少条边很消耗时间

邻接表表示法

优势与劣势：

方便找任一顶点的所有“邻接点”

节约稀疏图的空间，需要N个头指针+2E个结点（每个结点至少2个域）

方便计算任一顶点的“度”？

对无向图：是的
对有向图：只能计算“出度”；需要构造“逆邻接表”（存指向自己的边）来方便计算“入度

方便检查任意一对顶点间是否存在边？No

6.2 图的遍历

全部访问一遍

深度优先搜索（Depth First Search，DFS）

广度优先搜索（Breadth First Search，BFS）

图不连通的情况解决

一些概念

连通： 如果从 $V$ 到 $W$ 存在一条（无向）路径，则称 $v$ 和 $w$ 是连通的

路径： $V$ 到 $W$ 的路径是一系列顶点 ${V,v_1,v_2,…. v_n,W\}$ 的集合，其中任一对相邻的顶点间都有图中的边。路径的长度是路径中的边数（如果带权，则是所有边的权重和）。如果 $V$ 到 $W$ 之间的所有顶点都不同，则称简单路径。

回路： 起点等于终点的路径

连通图： 图中任意两顶点均连通

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

极大顶点数：再加1个其他顶点就不符合连通的定义
极大边数：包含子图中所有顶点相连的所有边

强连通： 有向图中顶点 $V$ 和 $W$ 之间存在双向路径，则称 $V$ 和 $W$ 是强连通的

强连通图： 有向图中任意两顶点均强连通

强连通分量： 有向图的极大强连通子图

ABC均有两条路径加上D就没有了