数据结构-图的相关定义

发表于 分类于

图是一种比树形结构更复杂的非线性结构。在图结构中，允许多个结点之间相关，称为「多对多」关系。本文整理关于图的基本定义以及图的相关术语。

图的定义

在图中，通常将数据元素称为顶点(Vertex)，顶点之间的关系称为边(Edge)。

图(Graph)由有限点集\(V\)和有限边集\(E\)组成，记为 \[ G = (V, E) \]

顶点总数\(|V|\)记为\(n\)，边的总数\(E\)记为\(e\)。

  1. 有向图

用\(<v, w>\)表示从顶点\(v\)指向顶点\(w\)的有向边，也称为弧(Arc)，\(v\)为起点，\(w\)为终点，起点与终点次序不能颠倒。当图中的边均为有向边，则称图为有向图(Digraph)。

  1. 无向图

若边集\(E\)是对称的，即当\(<v,w>\in E\) ，有\(<w,v>\in E\)，则称为无向图。此时用无序对\((v,w)\)代替有序对\(<v,w>\)和\(<w,v>\)，称为无向边，简称边。

  1. 子图

若图\(G = (V, E), G' = (V', E')\)，当\(V'\subseteq V, E' \subseteq E\)，则称\(G'\)为\(G\)的子图。

  1. 完全图

    包含所有可能的边的图称为完全图。

    • 无向完全图包含\(n(n-1)/2\)条边。
    • 有向完全图包含\(n(n - 1)\)条弧。

  2. 邻接顶点

    • 在无向图中，若存在边\((v, w)\)，则称\(v\)和\(w\)互为邻接顶点(Adjacent Verices)，或称\(v\)和\(w\)相邻接。
    • 在有向图中，若存在弧\(<v, w>\)，则称\(w\)是\(v\)的邻接顶点，但\(v\)未必是\(w\)的邻接顶点。

  3. 度

    在图中，顶点的度(Degree)指依附于该顶点的边数。

    对于有向图，又分为出度(OutDegree)和入度(InDegree)。

    • 出度：以该顶点为起点的弧的数目。
    • 入度：以该顶点为终点的弧的数目。
    • 有向图顶点的度为出度和入度之和。

  4. 权

    当图中的边或弧具有附加属性信息时，将此信息称为权(Weight)。

    带权的图称为带权图，简称为网(Network)。

  5. 路径

    如果顶点序列\((v_1, v_2, \cdots, v_n)\)从\(v_i\)到\(v_{i+1}(1 \le i <n)\)的边（弧）均存在，则称顶点序列\((v_1, v_2, \cdots, v_n)\)构成一条长度为\(n-1\)的路径。

    • 路径长度：路径包含的边数。
    • 简单路径：路径上的顶点各不相同。
    • 回路：一条路径将某个顶点连接到自身。

  6. 连通图和强连通图

    • 连通图

      在无向图中，若顶点\(v\)到顶点\(w\)有路径，则称\(v\)和\(w\)是连通的。若图中任意两个顶点都是连通的，则称该图为连通图(Connected Graph)。

      • 连通分量(Connected Component)：无向图中的极大连通子图。

    • 强连通图

      在有向图中，若图中任意两个顶点\(v\)和\(w\)，既有\(v\)到\(w\)的路径，又有\(w\)到\(v\)的路径，则称该图为强连通图(Strongly Connected Graph)。

      • 强连通分量(Strongly Connected Component)：有向图中的极大强连通子图。

  7. 生成树

    连通图的生成树(Spanning Tree)是含有所有顶点且只有\(n-1\)条边的连通子图。

参考资料

  • 《数据结构》（高教版，吴伟民，李小妹）