前言

写在前面的话：数据结构与算法。

对于初识数据结构的小伙伴们，鉴于后面的数据结构的构建会使用到同tag前面的内容，包括具体数据结构的应用，所使用到的数据结构，也是自己构建的，未使用系统的库文件，因此，建议这类小伙伴们按顺序进行学习；

对于想查询有关资料的小伙伴们，可以选择性地浏览。希望大家都能有所收获～

图的基本概念

这一章，我们来看一种新的数据结构-----图。

图是离散数学分支的内容，对图的描述，可以用一个有序二元组(V,E)表示，其中V称为顶集(Vertices Set)，E称为边集(Edges set)，E与V不相交。它们亦可写成V(G)和E(G)。其中，顶集的元素被称为顶点(Vertex)，边集的元素被称为边(edge)。图可记为 G 。

关于图中涉及的许多概念，读者可以查询有关资料深入了解。

在此只浅显列举部分：

阶（Order）：图G中点集V的大小称作图G的阶。

子图（Sub-Graph）：当图G'=(V',E')其中V‘包含于V，E’包含于E，则G'称作图G=(V,E)的子图。每个图都是本身的子图。

生成子图（Spanning Sub-Graph）：指满足条件V(G') = V(G)的G的子图G'。

导出子图（Induced Subgraph）：以图G的顶点集V的非空子集V1为顶点集，以两端点均在V1中的全体边为边集的G的子图，称为V1导出的导出子图；以图G的边集E的非空子集E1为边集，以E1中边关联的顶点的全体为顶点集的G的子图，称为E1导出的导出子图。

度（Degree）：一个顶点的度是指与该顶点相关联的边的条数，顶点v的度记作d(v)。

入度（In-degree）和出度（Out-degree）：对于有向图来说，一个顶点的度可细分为入度和出度。一个顶点的入度是指与其关联的各边之中，以其为终点的边数；出度则是指以该顶点为起点的边数。

自环（Loop）：若一条边的两个顶点为同一顶点，则此边称作自环。

路径（Path）：从u到v的一条路径是指一个序列v0,e1,v1,e2,v2,...ek,vk，其中ei的顶点为vi及vi - 1，k称作路径的长度。如果它的起止顶点相同，该路径是“闭”的，反之，则称为“开”的。

简单路径(simple path)：路径中除起始与终止顶点可以重合外，所有顶点两两不等。

连通：在无向图中，如果从顶点vi到顶点vj有路径，则称vi和vj连通。

连通图：无向图中任意两个顶点之间都连通。

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

强连通图：在有向图中，对于每一对顶点vi和vj，从vi到vj和从vj到vi都有路径。

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

图作为一种复杂的数据结构，研究图的搜索方式具有非常重要的意义，下一章，我们来探讨图的两种搜索方式。