图的开端

地图盘根错节，错综复杂，不同的道路相互连接，我们可以自由地从这些道路通过，从一个地点到达另一个地点。当然除了地图，我们的计算机网络、你的人际关系网等等，这些都可以用图结构来表示。

图也是由多个结点连接而成的，但是一个结点可以同时连接多个其他结点，多个结点也可以同时指向一个结点，跟我们之前讲解的树结构不同，它是一种多对多的关系：

它比树形结构更加复杂，没有明确的层次关系，结点与结点之间的连接关系更加自由，图结构是任意两个数据对象之间都有可能存在某种特定关系的数据结构。

基本概念

图（Graph）一般由两个集合共同构成，一个是非空但是有限的顶点集合V（Vertex），另一个是描述顶点之间连接关系的边集合E（Edge，边集合可以为空集，比如只有一个顶点的情况下）一个图实际上正是由这些结点（顶点）和对应的边组成的。因此，图可以表示为：$G=(V,E)$

无向图

比如一个图我们可以表示为，集合$V={A,B,C,D}$，集合$E={(A,B),(B,C),(C,D),(D,A),(C,A)}$，图有两种基本形式，一种是上面那样的有向图（有向图表明了方向，从哪个点到哪个点），还有一种是无向图（无向图仅仅是连接，并不指明方向），比如我们上面这样表示就是一个无向图：

每个结点的度就是与其连接的边数，每条边是可以包含权值的，当前也可以不包含。

有向图

当然我们也可以将其表示为有向图，集合$V={A,B,C,D}$，集合$E={<A,B>,<B,C>,<C,D>,<D,A>,<C,A>}$注意有向图的边使用尖括号<>表示。比如上面这个有向图，那么就长这样：

两者区别

如果是无向图的一条边(A,B)，那么就称A、B互为邻接点；如果是有向图的一条边<A,B>，那么就称起点A邻接到终点B。

有向图的每个结点分为入度和出度，其中入度就是与顶点相连且指向该顶点的边的个数，出度就是从该顶点指向邻接顶点的边的个数。

简单图

只要我们的图中不出现自回路边或是重边，那么我们就可以称这个图为简单图，比如上面两张图都是简单图。而下面的则是典型的非简单图了，其中图一出现了自回路，而图二出现了重边：

完全图

如果在一个无向图中，任意两个顶点都有一条边相连，则称该图为无向完全图：

同样的，在一个有向图中，如果任意两顶点之间都有由方向互为相反的两条边连接，则称该图为有向完全图：

连通图与强连通图

图通过边将顶点相连，这样我们就可以从一个顶点经过某条路径到达其他顶点了，比如我们现在想要从下面的V5点到达V1点：

那么我们可以有很多种路线，比如经过V2到达，经过V3到达等：

在一个无向图中，如果从一个顶点到另一个顶点有路径，那么就称这两个顶点是连通的。

• 如果图中任意两点都是连通的，那么我们就称这个图为连通图
• 对于有向图，如果图中任意顶点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，它也是连通图，并且包含了极大顶点数和边，所以说是连通分量。

• 原图为连通图，那么连通分量就是其本身，有且仅有一个。
• 原图为非连通图，那么连通分量会有多个。
  对于极小连通子图，我们会在后面的生成树部分进行讲解。