06_图(Graph)

图的定义

图（Graph）是由顶点的有穷非空集合和顶点之间的集合组成，通常表示为：G(V,E)，其中，G表示一个图，V是图G中顶点集合，E是图G中边的集合。

对于图的定义，需要注意的地方

线性表中把数据元素叫元素，树中将数据元素叫结点，在图中数据元素，则称之为顶点（Vertex）
在图结构中，不允许没有顶点
线性表中，相邻的数据元素之间具有钱性关系，树结构中，相邻两层的结点具有层次关系，而圈中，任意两个顶点之间都可能有关系，顶点之间的逻辑关系用边来表示，边集可以是空的。

各种图定义

无向边：若顶点 $V_i$ 到 $V_j$ ，之间的边没有方向，则称这条边为无向边( Edge) ，用无序偶对( $V_i$ ， $V_j$ ) 来表示。

无向图 $G_1$ ， $G_1=(V_1,{E_1})$ ，其中顶点集合 $V_1$ ={A，B，C，D} ;边集合 $E_1$ ={ ( A,B) ,(B,C) , (C,D),( D,A) , ( A,C) }
有向边：若从顶点 $V_i$ 到 $V_j$ 的边有方向，则称这条边为有向边，也称为弧( Arc )。用有序偶< $V_i$ ， $V_j$ >来表示, $V_i$ 称为弧尾( Tail ) ， $V_j$ 称为弧头( Head) 。

连接顶点 A 到 D 的有向边就是弧，A 是弧尾，D 是弧头， <A, D>表示弧，注意不能写成<D, A>。

向图 $G_2$ ， $G_2=(V_2,{E_2})$ ，其中顶点集合 $V_2$ ={A，B，C，D} ;边集合 $E_2$ ={ <A,D> ,<B,C> , <C,A>, < B,A> }

无向边用小括号"()'" 表示，而有向边则是用尖括号"<>"表示。

在图中，若不存在顶点到其自身的边，且同一条边不重复出现，则称这样的图为简单图。

在无向图中，如果任意两个顶点之间都存在边，则称该图为无向完全图。含有n个顶点的无向完全图有 $n (n - 1) /2$ 条边

在有向图中，如果任意两个顶点之间都存在方向互为相反的两条弧，则称该图为有向完全图。

含有 n 个顶点的有向完全图有 $n (n - 1)$ 条边

有很少条边或弧的图称为稀疏圈，反之称为稠密图。

假设有两个图 $G=(V\{E\})$ 和 $G’=(V’\{E’\})$ ，如果 $V’\subseteq V$ 且 $E’\subseteq E$ ，则称 $G ’$ 为 $G$ 的子图(Subgraph)

图的顶点和边的关系

对于无向图 $G=(V\{E\})$ ，如果边 $(v,v')\in E$ ，则称顶点 $v$ 和 $v^{'}$ 互为邻接点(Adjacent)，即 $v$ 和 $v^{'}$ 邻接。边 $(v, v^{'})$ 依附( incident) 于顶点 $v$ 和 $v^{'}$ ，或者说边的与顶点 $v$ 和 $v^{'}$ 相关联。顶点 $v$ 的度(Degree ) 是和 $v$ 相关联的边的数目，记为 $T D (v)$ 。

无向图 $G=(V\{E\})$ 中从顶点 $v$ 到顶点 $v^{'}$ 的路径（Path）是一个顶点序列 $v=v_{i,0},v_{i,1},...,v_{i,m})$ ，其中 $(v_{i,j-1},v_{i,j}) \in E , 1 \leq j \leq m$ 。

对于有向图 $G=(V\{E\})$ ，如果弧 $<v,v'>\in E$ ，则称顶点 $v$ 邻接到顶点 $v^{'}$ ，顶点 $v^{'}$ 邻接至顶点 $v$ 。弧 $< v, v^{'} >$ 与顶点 $v$ 和 $v^{'}$ 相关联。以顶点 $v$ 为头的弧的数目称为 $v$ 的入度（InDegree），记为 $I D (v)$ 。以顶点 $v$ 为尾的弧的数目称为 $v$ 的出度（OutDegree），记为 $O D (v)$

有向图 $G=(V\{E\})$ ，路径是有向的，顶点序列应满足 $<v_{i,j-1},v_{i,j}> \in E , 1 \leq j \leq m$ 。

路径长度是路径上的边或弧的数目。

第一个顶点到最后一个顶点相同的路径称为回路或环(Cycle)。序列中顶点不重复出现的路径称为简单路径。除了第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路，称为简单回路或简单环。

连通图相关术语

在无向图 $G$ 中，如果从顶点 $v$ 到顶点 $v^{'}$ 又路径，则称 $v$ 和 $v^{'}$ 是连通的。如果对于图中任意两个顶点 $v_1、v_j、\in E$ ， $v_i$ 和 $v^{'}$ 都是连通的，则称 $G$ 是连通图（Connected Graph）。

无向图中的极大连通子图称为连通分量

要是子图
子图要是连通的
连通子图包含有极大顶点数
具有极大顶点的连通子图包含依附于这些顶点的所以边

在有向图 $G$ 中，如果对于每一对 $v_i、v_j \in V、v_i \neq v_j$ ，从 $v_i$ 到 $v_j$ 和 $v_j$ 到 $v_i$ 都存在路径，则称 $G$ 是强连通图。有向图中的极大强连通子图称做有向图的强连通分量。

图的存储结构

邻接矩阵

图的邻接矩阵（Adjacency Matrix）存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息，一个二维数组（称为邻接矩阵）存储图中的边或弧的信息。

设图 G 有 n 个顶点，则邻接矩阵是一个 n X n 的方阵，定义为：
$\begin{cases}1，若(v_i,v_j) \in E 或者<v_i,v_j> \in E \\0，反之 \end{cases}$

无向图

在这里插入图片描述

顶点数组为 $vertex[4] =\{v_0,v_1,v_2,v_3\}$ ，边数组 arc[4][4] 为上图中的矩阵，对于矩阵的主对角钱的值，即arc[0][0]、arc[1][1]、全arc[2][2]、arc[3][3]为 0 是因为不存在顶点到自身的边。arc[0][1]=1 是因为 $v_0$ 到 $v_1$ 的边存在，而 arc[1][3] =0 是因为 $v_1$ 到 $v_3$ 的边不存在。并且由于是无向图， $v_1$ 到 $v_3$ 的边不存在，意味着 $v_3$ 到 $v_1$ 的边也不存在。所以无向固的边数组是一个对称矩阵。

判定任意两顶点是否有边无边就非常容易
某个顶点的度，其实就是这个顶点 $v_i$ 在邻接矩阵中第i行（或者i列）的元素和
求顶点 $v_i$ 的所有邻接点就是将矩阵中第i行元素扫描一遍，arc[i][j]为1的就是邻接点

有向图

在这里插入图片描述

顶点数组为 $vertex[4] =\{v_0,v_1,v_2,v_3\}$ ，弧数组 arc[4][4] 为上图中的矩阵。主对角线上数值依然为0。但因为是有向图，所以矩阵并不对称。

有向图讲究入度和出度，顶点 $v_1$ 的入度为1，正好是第 $v_1$ 列各数之和，顶点 $v_1$ 的出度为2，即第 $v_1$ 行的各个数之和。

网

网的概念，也就是每条边上带有权的图叫做网。
$arc[i][j]=\begin{cases}W_{ij}，若(v_i,v_j)\in E 或者<v_i,v_j> \in E \\0，若i=j\\ \infty ，反之 \end{cases}$
这里的 $W_{ij}$ 表示 $v_i,v_j)$ 或者 $v_i,v_j>$ 上的权值。 $\infty$ 表示一个计算机允许的大于所以边上权值的值。

在这里插入图片描述

邻接表

邻接矩阵是不错的一种图存储结构，但对于边数相对顶点较少的图，这种结构是存在对存储空间的极大浪费的。

邻接表的处理办法：

图中顶点用一个一维数组存储，当然，顶点也可以用单链表来存储，不过数组可以较容易地读取顶点信息，更加方便。另外，对于顶点数组中，每个数据元素还需要存储指向第一个邻接点的指针，以便于查找该顶点的边信息。
图中每个顶点 $v_i$ 的所有邻接点构成一个线性表，由于邻接点的个数不定，所以用单链表存储，无向图称为顶点 $v_i$ 的边表，有向图则称为顶点 $v_i$ 作为弧尾的出边表。