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

【数据结构】6——图1，概念

news 2025/2/23 23:23:56

数据结构6——图1，概念

由顶点（Vertex）和边（Edge）组成的集合。顶点表示图中的点，而边表示顶点之间的连接。记为 G = (V, E）

基本组件包括：
顶点（Vertex）：图中的节点或点。每个顶点代表一个对象。
边（Edge）：连接两个顶点的线段，表示它们之间的关系。边可以是有向的或无向的。
权重（Weight）：有些图的边附带权重，表示边的成本、距离或其他量度。

邻接：有边连接的两个节点的关系
（i，j）没有先后顺序
<i，j>有先后顺序
关联：边和相连的节点的关系
顶点的度：关联边的数目
路径（Path）：图中从一个顶点到另一个顶点所经过的顶点序列。
简单路径（Simple Path）：路径中所有的顶点都不重复。
环（Cycle）：路径的起点和终点相同，并且至少经过一个其他顶点。若图中存在环，称为有环图；否则称为无环图。
强连通图（Strongly Connected Graph）：对于有向图，如果对于每一对顶点 u 和v，都存在从 u 到v 和从 v 到 u 的路径，则该图是强连通的。
生成树（Spanning Tree）：一个无环的子图，包含图中的所有顶点，且是连通的。
生成森林（Spanning Forest）：由多个生成树组成的集合，每个生成树包含图中一部分顶点。
子图（Subgraph）：图中的一部分顶点和边的集合，这些顶点和边也构成一个图。

无向图（Undirected Graph）：图中的边没有方向，即如果顶点A与顶点B之间有一条边，那么它表示A和B之间是相互连接的。
有向图（Directed Graph）：图中的边有方向，称为弧（Arc）。如果顶点A与顶点B之间有一条有向边，它表示从一个顶点指向另一个顶点的单向连接。
加权图（Weighted Graph）：图中的边被赋予了权重（Weight），这些权重可以表示距离、成本、时间等。
无权图（Unweighted Graph）：图中的边没有权重，或者所有边的权重相同。
简单图（Simple Graph）：图中不包含重复的边，且不允许顶点与自己相连（自环）。
多重图（Multigraph）：图中可以有多条边连接相同的一对顶点。
完全图（Complete Graph）：图中的每对顶点之间都恰好有一条边。
稀疏图（Sparse Graph）：边的数量远小于顶点对的数量。边很少
密集图（Dense Graph）：边的数量接近顶点对的最大数量。
连通图（Connected Graph）：在无向图中，如果任意两个顶点之间都存在路径，则称该图为连通图。在有向图中，如果任意两个顶点之间都存在方向路径，则称该图为强连通图。
网：边带权值的图

邻接矩阵（Adjacency Matrix）
定义：一个二维数组 matrix[i][j] 表示顶点 i 和顶点 j 之间的边。如果 matrix[i][j] 非零，则存在边。
优点：快速查询是否存在边，适用于稠密图。
缺点：空间复杂度为 O(V^2)，其中 V 是顶点数量，适用于大部分稠密图。

假设有一个无向图，包含 4 个顶点（A, B, C, D）和以下边：
A - B
A - C
B - C
C - D

    A  B  C  D
A [ 0, 1, 1, 0 ]
B [ 1, 0, 1, 0 ]
C [ 1, 1, 0, 1 ]
D [ 0, 0, 1, 0 ]

邻接表（Adjacency List），不唯一
定义：每个顶点维护一个列表，列出与其相邻的所有顶点。l链表
优点：节省空间，适用于稀疏图。
缺点：查询边的操作较慢，空间复杂度为 O(V + E)，其中 E 是边的数量。

A: B -> C
B: A -> C
C: A -> B -> D
D: C

[(A, B), (A, C), (B, C), (C, D)]