【CS.DS】数据结构 —— 图: 图的相关概念大全

1 图的类型

图是一种数据结构，由节点（顶点）和边组成。图可以用来表示各种网络结构，如社交网络、交通网络、计算机网络等。根据边的性质，图可以分为以下几种类型：

1. 无向图（Undirected Graph）：边没有方向，表示一种双向关系。例如，社交网络中的好友关系。
2. 有向图（Directed Graph 或 Digraph）：边有方向，表示一种单向关系。例如，网页之间的超链接。
3. 加权图（Weighted Graph）：边具有权重，表示边的距离、成本或容量等属性。例如，交通网络中的道路距离。
4. 稀疏图（Sparse Graph）：边的数量较少，接近于最小值。例如，一个大城市中的少数航班连接。
5. 稠密图（Dense Graph）：边的数量较多，接近于最大值。例如，一个完全连接的社交网络。
6. 连通图（Connected Graph）：无向图中任意两个顶点间都有路径可达。
7. 强连通图（Strongly Connected Graph）：有向图中任意两个顶点间都有双向路径可达。
8. 完全图（Complete Graph）：任意两个顶点之间都有一条边。

2 图的基本术语

1. 顶点（Vertex）：图中的一个点，表示对象或实体。
2. 边（Edge）：连接两个顶点的线段，表示顶点之间的关系。
3. 度（Degree）：
   • 无向图：顶点的度是连接该顶点的边的数量。
   • 有向图：
     • 入度（In-degree）：指向该顶点的边的数量。
     • 出度（Out-degree）：从该顶点出发的边的数量。
4. 路径（Path）：从一个顶点到另一个顶点的边的序列。
5. 简单路径（Simple Path）：路径中不含重复顶点。
6. 环（Cycle）：起点和终点相同的路径。
7. 简单环（Simple Cycle）：环中除了起点和终点外不含重复顶点。
8. 连通分量（Connected Component）：无向图中，所有顶点之间都有路径相连的极大子图。
9. 强连通分量（Strongly Connected Component）：有向图中，所有顶点之间都有双向路径相连的极大子图。
10. 子图（Subgraph）：由原图的部分顶点和边构成的图。

References

• 【CS.DS】数据结构 —— 图：深入了解三种表示方法之邻接表(Adjacency List)

1000.02.CS.DS.5.1-图结构-基本概念-Created: 2024-06-19.Wednesday15:22