【
写在前面的话:本专栏的主要内容:数据结构与算法。
1.对于初识数据结构的小伙伴们,鉴于后面的数据结构的构建会使用到专栏前面的内容,包括具体数据结构的应用,所使用到的数据结构,也是自己构建的,未使用系统的库文件,因此,建议这类小伙伴们从本专栏的总揽按顺序进行学习;
2.对于想查询有关资料的小伙伴们,可以选择性地浏览。希望小伙伴们都能有所收获~
】
上一篇笔者介绍了二叉树。这一章,我们来看一种新的数据结构-----图。
图是离散数学的内容,对图的描述,可以用一个有序二元组(V,E)表示,其中V称为顶集(Vertices Set),E称为边集(Edges set),E与V不相交。它们亦可写成V(G)和E(G)。其中,顶集的元素被称为顶点(Vertex),边集的元素被称为边(edge)。图可记为 G 。
关于图中涉及的许多概念,读者可以查询有关资料深入了解。
在此只浅显列举部分:
1. 阶(Order):图G中点集V的大小称作图G的阶。
2. 子图(Sub-Graph):当图G'=(V',E')其中V‘包含于V,E’包含于E,则G'称作图G=(V,E)的子图。每个图都是本身的子图。
3. 生成子图(Spanning Sub-Graph):指满足条件V(G') = V(G)的G的子图G'。
4. 导出子图(Induced Subgraph):以图G的顶点集V的非空子集V1为顶点集,以两端点均在V1中的全体边为边集的G的子图,称为V1导出的导出子图;以图G的边集E的非空子集E1为边集,以E1中边关联的顶点的全体为顶点集的G的子图,称为E1导出的导出子图。
5. 度(Degree):一个顶点的度是指与该顶点相关联的边的条数,顶点v的度记作d(v)。
6. 入度(In-degree)和出度(Out-degree):对于有向图来说,一个顶点的度可细分为入度和出度。一个顶点的入度是指与其关联的各边之中,以其为终点的边数;出度则是指以该顶点为起点的边数。
7. 自环(Loop):若一条边的两个顶点为同一顶点,则此边称作自环。
8. 路径(Path):从u到v的一条路径是指一个序列v0,e1,v1,e2,v2,...ek,vk,其中ei的顶点为vi及vi - 1,k称作路径的长度。如果它的起止顶点相同,该路径是“闭”的,反之,则称为“开”的。
9. 简单路径(simple path):路径中除起始与终止顶点可以重合外,所有顶点两两不等。
10. 连通:在无向图中,如果从顶点vi到顶点vj有路径,则称vi和vj连通。
11. 连通图:无向图中任意两个顶点之间都连通。
12. 连通分量:无向图的极大连通子图。
13. 强连通图:在有向图中,对于每一对顶点vi和vj,从vi到vj和从vj到vi都有路径。
14. 强连通分量:有向图的极大连通子图。
图是一个复杂的数据结构,研究图的搜索方式具有非常重要的意义,下一章,我们来仔细探讨图的两种搜索方式:
-----广度优先搜索算法和深度优先搜索算法