数据结构与算法之-----图(基本概念)

        写在前面的话:本专栏的主要内容:数据结构与算法。

        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. 强连通分量:有向图的极大连通子图。

        图是一个复杂的数据结构,研究图的搜索方式具有非常重要的意义,下一章,我们来仔细探讨图的两种搜索方式:

                -----广度优先搜索算法和深度优先搜索算法

                              

上一篇:Linux系统概述和编程基础


下一篇:linux vim查看下一页,Linux下vi和vim的模式相互切换