数据结构与算法之-----图（基本概念）

本文主要是介绍数据结构与算法之-----图（基本概念），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

【

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

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

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

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

这篇关于数据结构与算法之-----图（基本概念）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！