【CS.DS】数据结构 —— 图: 图的相关概念大全
文章目录
[1 图的类型](#1 图的类型)
[2 图的基本术语](#2 图的基本术语)
References
1 图的类型
图是一种数据结构，由节点（顶点）和边组成。图可以用来表示各种网络结构，如社交网络、交通网络、计算机网络等。根据边的性质，图可以分为以下几种类型：
无向图（Undirected Graph）：边没有方向，表示一种双向关系。例如，社交网络中的好友关系。
有向图（Directed Graph 或 Digraph）：边有方向，表示一种单向关系。例如，网页之间的超链接。
加权图（Weighted Graph）：边具有权重，表示边的距离、成本或容量等属性。例如，交通网络中的道路距离。
稀疏图（Sparse Graph）：边的数量较少，接近于最小值。例如，一个大城市中的少数航班连接。
稠密图（Dense Graph）：边的数量较多，接近于最大值。例如，一个完全连接的社交网络。
连通图（Connected Graph）：无向图中任意两个顶点间都有路径可达。
强连通图（Strongly Connected Graph）：有向图中任意两个顶点间都有双向路径可达。
完全图（Complete Graph）：任意两个顶点之间都有一条边。
2 图的基本术语
顶点（Vertex）：图中的一个点，表示对象或实体。
边（Edge）：连接两个顶点的线段，表示顶点之间的关系。
度（Degree） ：
无向图：顶点的度是连接该顶点的边的数量。
有向图 ：
入度（In-degree）：指向该顶点的边的数量。
出度（Out-degree）：从该顶点出发的边的数量。
路径（Path）：从一个顶点到另一个顶点的边的序列。
简单路径（Simple Path）：路径中不含重复顶点。
环（Cycle）：起点和终点相同的路径。
简单环（Simple Cycle）：环中除了起点和终点外不含重复顶点。
连通分量（Connected Component）：无向图中，所有顶点之间都有路径相连的极大子图。
强连通分量（Strongly Connected Component）：有向图中，所有顶点之间都有双向路径相连的极大子图。
子图（Subgraph）：由原图的部分顶点和边构成的图。
References
【CS.DS】数据结构 ------ 图：深入了解三种表示方法之邻接表(Adjacency List)
1000.02.CS.DS.5.1-图结构-基本概念-Created: 2024-06-19.Wednesday15:22
