图 (数据结构)

图可以定义为由顶点和连接这些顶点的边组成的集合。图可以看作是循环树，其中顶点（节点）之间保持任何复杂的关系，而不是父子关系。

定义

图 G 可以定义为有序集 G(V, E)，其中 V(G) 表示顶点集，E(G) 表示用于连接这些顶点的边集。

图 G(V, E) 包含 5 个顶点（A、B、C、D、E）和六条边（(A,B)、(B,C)、(C,E)、(E,D)、(D,B)、(D,A)），如下图所示。

有向图和无向图

图可以是定向的或无方向的。然而，在无向图中，边不与方向相关联。上图显示了一个无向图，因为它的边没有附加任何方向。如果顶点 A 和 B 之间存在边，则可以从 B 到 A 以及从 A 到 B 遍历这两个顶点。

在有向图中，边构成一个有序对。边表示从某个顶点 A 到另一个顶点 B 的特定路径。顶点 A 称为起始节点，顶点 B 称为终止节点。

下图显示了一个有向图。

图论术语

路径

路径可以定义为从起始节点 U 到达某个终止节点 V 所遵循的节点序列。

闭合路径

如果起始节点与终止节点相同，则路径称为闭合路径。如果 V₀=V_N，则路径为闭合路径。

简单路径

如果图的所有节点都不同，但 V₀=V_N 除外，则称该路径 P 为闭合简单路径。

环

循环可以定义为除了第一个和最后一个顶点之外，没有重复边或顶点的路径。

连通图

连通图是指任意两个顶点 (u, v) 之间都存在路径的图。连通图中没有孤立节点。

完全图

完全图是指每个节点都与其他所有节点相连的图。完全图包含 n(n-1)/2 条边，其中 n 是图中的节点数。

加权图

在加权图中，每条边都分配有某些数据，例如长度或权重。边 e 的权重可表示为 w(e)，它必须是正值 (+) ，表示遍历该边的成本。

有向图

有向图是图中的每条边都与某个方向相关联，并且只能沿指定方向遍历的图。

循环

与相同端点相关联的边称为环。

相邻节点

如果两个节点 u 和 v 通过边 e 相连，则节点 u 和 v 称为邻居或相邻节点。

节点度

节点的度是与该节点相连的边的数量。度为 0 的节点称为孤立节点。