数据结构-图的相关定义

发表于 分类于

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

图的定义

在图中，通常将数据元素称为顶点(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$条边的连通子图。

参考资料

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