其实在上一篇介绍树结构的时候,已经有了一些算法的相关内容介入。而在图这种数据结构下,会有更多有关图的算法,比如广度优先搜索,深度优先搜索最短路径算法等等。这是我们要介绍的最后一个数据结构。同时也是本系列最为复杂的一个。那么我们先来简单介绍一下,什么是图?
一、图的概念
简单说,图就是网络结构的抽象模型,图是一组由边连接的节点(或顶点)。任何二元关系都可以用图来表示。比如我们的地图,地铁线路图等。都是图的实际应用。
接着我们看看图的一些相关概念和术语。
一个图G = (V,E)由以下元素组成:
V:一组顶点。
E:一组边,链接V中的顶点。
在继续之前我们先来上张图,继续我们的看图说话。
请看上图,我们来解释一些概念。
1、由一条边连接在一起的顶点称为相邻顶点。比如上图中的A和B,A和C,A和D都是相邻的,但是A和E不是相邻的。
2、一个顶点的度取决于其相邻顶点的数量。也就是说,有多少个顶点与其相连,那么它的度就是多少。比如A的度是3,D的度就是4。
3、路径是顶点V1,V2.....Vn的一个连续序列,其中Vi和Vi+1是相邻的。比如上图中的ACDG,ABEI都是一个路径。
4、简单路径要求不包含重复的定点。比如ADG就是一条简单路径。
5、除去最后一个顶点(因为它和第一个顶点时相同的),环也是一个简单路径,比如ADCA。
6、如果图中不存在环。则该图是无环的。
7、如果图中每两个顶点间都存在路径,则该图是连通的。
为了便于对比,我又花了一张图。
跟第一幅图几乎是一样的,只不过我们在路径上加了点东西。
8、图可以是有向的(边有方向)或者是无向的(边没有方向)。比如上图我们在边上加了方向就变成了有向图。
9、如果在图中的每两个顶点间在双向上都存在路径,则该图是强连通的。比如上图中我们可以说C和D是强连通的。A和B不是强连通的。但是上图并不是一个强连通图。因为上图并不是每两个点都有双向的路径。
10、图还可以是未加权的或是加权的。上图边上加的数字就是加权值。(加权的意思可以简单理解为CSS选择器中的那种权重。)
二、图的表示方法
我们可以表示图的方法有很多。根据我们要解决问题的类型和图的类型。我们可以选择不同的方法来表示图。下面我们会简单介绍两种表示图的方法。
1、邻接矩阵。每一个节点都和一个整数相关联,该整数将作为数组的索引。我们用一个二维数组来表示各个顶点之间的连接情况。比如索引为i的节点和索引为j的节点相邻,则表示为arrya[i][j]=1。否则arrya[i][j]=0。
邻接矩阵看起来就是这样子的。要注意我们上面的邻接矩阵只是表示两个顶点是否相邻。我们还需要一个数组来存储所有的顶点。
但是邻接矩阵会有一些性能问题。比如我们会用很多的空间来表示一些根本就不存在的边。比如上图所有的0。再比如我们想要找到A顶点的相邻顶点,即使A顶点只有一个相邻顶点。我们也必须遍历整个数组才能找到。
2、邻接表,鉴于以上的问题。我们在本篇中所使用的图的表示方法就是邻接表。邻接表由图中每个顶点的相邻顶点列表所组成。我们可以用数组,链表,map或者hashMap来实现邻接表。
邻接表看起来就像是上图这样。
那么我们知道了图的一些基本概念和我们要使用的图的表示方法。下面我们先来完成我们Graph类的架子。