Skip to content

图结构

· 3 min

图是网络结构的抽象模型，由一组 边 和 顶点 组成。下图就是一个典型的图结构：

image-20250303201821109

相关术语

  1. 顶点：图里面一个一个数据元素被称之为 顶点。之前在线性表中称之为元素，树里面称之为节点。

    另外，线性表可以没有元素（空表），树里面可以没有节点（空树），但是在图结构中不能够没有顶点。

  2. 相邻顶点：由一条边连接在一起的两个顶点，称之为相邻顶点。

  3. 度：一个顶点的相邻顶点的数量。

  4. 路径：指的是一连串顶点序列。其中有一个概念称之为 简单路径，指的就是 不包含 重复顶点的路径。

  5. 环：从某一个顶点出发，最后回到该顶点，形成了一个闭环。环也会算作是一个简单路径。

无向图和有向图

  1. 无向图：顾名思义就是 顶点之间是没有方向的
image-20250303200232935

由于是无方向的，因此连接 A 和 D 的边，可以表示为 (A, D)，也可以写成(D, A)。对于无向图来讲，G = (V,{E})，其中顶点集合 V = {A,B,C,D}，边集合 E = {(A,B), (B,C), (C,D), (D,A), (A,C)}

在无向图中，如果每一个顶点都和其他所有顶点相连，则称该无向图为 无向完全图。如下图所示：

image-20250303211346799

一个含有 n 个顶点的无向完全图拥有

n∗(n−1)2\frac{n*(n-1)}{2}

条边。例如上面的无向完全图有 4 个顶点，根据公式计算出拥有 6 条边。

  1. 有向图：顶点之间 有明确的方向
image-20250303201206757

有向图是有方向的，使用 尖括号 来表示，尖括号中的第一个节点表示 tail，第二个节点表示 head。例如上图为 G = (V,{E})，其中顶点集合 V = {A,B,C,D}，边集合 E = {<A,D>, <B,A>, <C,A>, <B,C>}。

在有向图中，如果 任意两个顶点之间都存在方向相反的指向，称之为 有向完全图。例如下图就是一个有向完全图：

image-20250312125950523

加权图

图还可以是加权的。如下图所示，加权图的 边被赋予了权值。

image-20250303205916275

子图

假设有两个图，一个图是 G = (V, {E})，另一个图是 G' = (V', {E'})，如果

V′⊆VE′⊆E\begin{aligned} V' &\subseteq V \\ E' &\subseteq E \end{aligned}

那么我们称 G’ 为 G 的子图。

举个例子：

image-20250312131312298

-EOF-