数据结构（四）图
图(Graph)
图也是由多个结点连接而成的，但是一个结点可以同时连接多个其他结点，多个结点也可以同时指向一个结点，跟我们之前讲解的树结构不同，它是一种多对多的关系：
它比树形结构更加复杂，没有明确的层次关系，结点与结点之间的连接关系更加自由，图结构是任意两个数据对象之间都有可能存在某种特定关系的数据结构。
基本概念
在了解之前，最好优先学习一下离散数学。
如果离散数学已经有一定基础的话，本段可以跳过。
图一般由两个集合共同构成，一个是非空但是有限的顶点集合V（Vertex），另一个是描述顶点之间连接关系的边集合E（Edge，边集合可以为空集，比如只有一个顶点的），一个图实际上正是由这些结点（顶点）和对应的边组成的。因此，图可以表示为：$G=
学过离散数学的我们可以很清楚的知道。一个图我们可以表示为，集合$V={A,B,C,D,E}$，集合$E=\{(A,B),(B,C),(C,D),(D,A),(C,A)\}$，图有两种基本型式，有向图和无向图。
每个结点的度就是与其连接的边数，每条边是可以包含权值的，当前也可以不包含。
当然我们也可以将其表示为有向图，集合$V={A,B,C,D,E}$，集合$E=\{(A,B),(B,C),(C,D),(D,A),(C,A)\}$注意有向图的边使用尖括号<>表示。比如上面这个有向图，那么就长这样：
如果是无向图的一条边(A,B)，那么就称A、B互为邻接点；如果是有向图的一条边
只要我们的图中不出现自回路边或是重边，那么我们就可以称这个图为简单图，比如下面两张图都是简单图。而下面的则是典型的非简单图了，其中图一出现了自回路，而图二出现了重边：
如果在一个无向图中，任意两个顶点都有一条边相连，则称该图为无向完全图：
同样的，在一个有向图中，如果任意两顶点之间都有由方向互为相反的两条边连接，则称该图为有向完全图：
图通过边将顶点相连，这样我们就可以从一个顶点经过某条路径到达其他顶点了，比如我们现在想要从下面的V5点到达V1点：
那么我们可以有很多种路线，比如经过V2到达，经过V3到达等：
在一个无向图中，如果从一个顶点到另一个顶点有路径，那么就称这两个顶点是连通的。可以看到，要从V5到达V1我们可以有很多种选择，从V5可以到达V1（当然也可以反着来），所以，我们称V5和V1连通的。特别的，如果图中任意两点都是连通的，那么我们就称这个图为连通图。对于有向图，如果图中任意顶点A和B，既有从A到B的路径，也有B到A的路径，则称该有向图是强连通图。
对于图$G=(V,E)$和$G’=(V’,E’)$，若满足$V’$是$V$的子集，并且$E’$是$E$的自己，则称$G’$是$G$的子图。
其中右边的图就满足上述性质，所以说右边的图是左边图的子图。
无向图的极大连通子图称为连通分量，有向图的极大连通子图称为强连通分量。那么什么是极大连通子图呢？首先连通子图就是原图的子图，并且子图也是连通图，同时应该具有最大的顶点数，即再加入原图中的其他顶点会导致子图不连通，拥有极大顶点数的同时也要包含依附于这点顶点所有的边才行，比如：
可以看到右侧图1、2、3都是左图的子图，但是它们并不都是原图的连通分量，首先我们来看图1，它也是一个连通图，并且包含极大顶点数和所有的边（也就是原图内部的这一块）所以说它是连通分量，我们接着来看图2，它虽然也是连通图，但是并没有包含极大顶点数（最多可以吧D也给加上，但是这里没加）所以说并不是。最后来看图3，它也是连通图，并且包含了极大顶点数和边，所以说是连通分量。
- 原图为连通图，那么连通分量就是其本身，有且仅有一个。
- 原图为非连通图，那么连通分量会有多个。
对于极小连通子图，我们会在后面的生成树部分进行讲解。
