当前位置：首页 > news >正文

图（Java语言实现）

news 2025/8/21 12:11:29

一、图的概念

顶点（Vertex）：图中的数据元素，我们称之为顶点，图至少有一个顶点（非空有穷集合）。
边（Edge）：顶点之间的关系用边表示。

1.图（Graph）

图 G 由顶点集 V 和边集 E 组成，记为 $G = (V, E)$ ，其中V(G)表示图G中顶点的有限非空集； $E (G)$ 表示图 G 中顶点之间的关系（边）集合。若 $V = \{ v_1 , v_2 , … , v_n \}$ ，则用 $∣ V ∣$ 表示图 G 中顶点的个数，也称图G的阶（Order）， $\{ (u, v) | u \in V, v \in V \}$ ，用 $∣ E ∣$ 表示图 G 中边的条数

注意：线性表可以是空表，树可以是空树，但图不可以是空，即V一定是非空集

在这里插入图片描述
上图所示为一张图（Graph），元素A、B、C、D、E、F分别为图的顶点（Vertex），两个元素之间的关系（连线）成为图的边（Edge）。

上面的图可以表示为：

$G = (V, E)$
$V = \{A, B, C, D, E, F\}$
$E =\{ (A, B), (A, C), (A, D), (B, E), (B, F), (C, E), (D, F) \}$
图的阶数 $∣ V ∣ = 6$
图的边的条数 $∣ E ∣ = 7$ 。

2.无向图（Undirected Graph）与有向图（Directed Graph）

（1）无向图（Undirected Graph）

若 E 是无向边（简称边）的有限集合时，则图 G 为无向图。边是顶点的无序时，记为 $(v, w)$ 或 $(w, v)$ ，因为 $(v, w) = (w, v)$ ，其中v、w是顶点。可以说顶点 w 和顶点 v 互为邻接点。边 $(v, w) $依附于顶点 w 和 v ，或者说边 $(v, w)$ 和顶点 v 、w 相关联。

简单来说，边没有方向的图就是无向图。
在这里插入图片描述
上图可表示为：

$G_u = (V_u , E_u )$
$V_u = \{A, B, C, D, E\}$
$E_u = \{(A, B), (B, D), (B, E), (C, D), (C, E), (D, E)\}$

（2）有向图（Directed Graph）

若 E 是有向边（也称弧（Arcs））的有限集合时，则图 G 为有向图。弧是顶点的有序对，记为 $< v, w >$ ，其中 v 、 w 是顶点， v 称为弧尾， w 称为弧头， $< v, w >$ 称为从顶点v到顶点w的弧，也称v邻接到 w ，或 w 邻接自 v 。 $< v, w > \neq = < w, v >$

简单来说，边有方向的图就是有向图。
在这里插入图片描述
上图可表示为：
$G_d = (V_d , E_d )$
$V_d = \{A, B, C, D, E\}$
$E_d = \{<A, B>, <A, C>, <A, D>, <A, E>, <B, A>, <B, C>, <B, E>, <C, D>\}$

3. 简单图（Simple Graph）与多重图（Multi Graph）

（1）简单图（Simple Graph）

不存在重复边并且不存在顶点到自身的边的图称为简单图

在这里插入图片描述

（2）多重图（Multi Graph）

允许两个结点之间的边数多于一条，又允许顶点通过同一条边和自己关联的图多重图。
在这里插入图片描述

4. 顶点的度（Degree）

度（Degree）：顶点v的度是指依附于该顶点的边的条数，记为TD(v)。
入度（Indegree）：入度是有向图中以顶点 v 为终点的有向边的数目，记为ID(v)；
出度（Outdegree）：出度是有向图中以顶点 v 为起点的有向边的数目，记为OD(v)。

在有向图中，顶点 v 的度等于其入度和出度之和，即
$T D (v) = I D (v) + O D (v)$ 。

度在有向图和无向图中都存在，而入度和出度只存在于无向图中。

5. 描述顶点关系的几个概念

路径（path）：顶点 v_p 到顶点 v_q 之间的一条路径是指顶点序列 ${v_p, v_{i1}, v_{i2},... ,v_{im-1},v_{im},v_q\}$ 。
回路（circuit）：第一个顶点和最后一个顶点相同的路径称为回路或环。
简单路径（Simple Path）：在路径序列中，顶点不重复出现的路径称为简单路径。
简单回路（Simple Circuith）：除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路称为简单回路或环（Cycle）。
路径长度（Path Length）：路径上边的数目。
点到点的距离（Distance）：从顶点 u 出发到顶点v的最短路径若存在，则此路径的长度称为从 u 到 v 的距离。若从 u 到 v 根本不存在路径，则记该距离为无穷（∞）。
连通（connected）：无向图中，若从顶点 v 到顶点 w 有路径存在，则称 v 和 w 是连通的
强连通（Strongly Connected）：有向图中，若从顶点 v 到顶点 w 和从顶点 w 到顶点 v 之间都有路径，则称这两个顶点是强连通。
弱连通（Weakly Connected）：若一张有向图的边替换为无向边后，所得到的图称为原图的基图。如果一个有向图的基图是连通图，则称原来这张有向图是弱连通。

6.连通图（Connected Graph）与强连通图（Strongly Connected Graph）

连通图（Connected Graph）：若图 G 中任意两个顶点都是连通的，则称图 G 为连通图，否则称为非连通图。
强连通图（Strongly Connected Graph）：若有向图中任何一对顶点都是强连通的，则称此图为强连通图。
弱连通图（Weakly Connected Graph）：将有向图的所有的有向边替换为无向边，所得到的图称为原图的基图。如果一个有向图的基图是连通图，则有向图是弱连通图。

7. 子图（SubGraph）与生成子图（Spanning SubGraph）

设有两个图 $G = (V, E)$ 和 $G^{'} = (V^{'}, E^{'})$ ，若 $V^{'}$ 是 $V$ 的子集，且 $E^{'}$ 是 $E$ 的子集，则称 $G^{'}$ 是 $G$ 的子图。

若有满足 $V (G^{'}) = V (G)$ 的子图 $G^{'}$ ，则称其为 G 的生成子图。

在这里插入图片描述

8. 连通分量（Connected Component）

连通分量（Connected Component）：无向图中的极大连通子图称为连通分量。
强连通分量（Strongly Connected Component）：有向图中极大强连通子图称为强连通分量。
弱连通分量（Weakly Connected Component）：将有向图的所有的有向边替换为无向边，所得到的图称为原图的基图。一个有向图的基图的极大连通子图称为弱连通分量。
在这里插入图片描述