幕雪

图数据结构基本概念、不同表示法与核心操作详解

图数据结构是什么？

图数据结构是一种非线性数据结构，它由一组节点（或称为顶点，Vertex）以及连接这些节点的边（Edge）组成。它用于表示对象之间的复杂关系和连接。与树数据结构不同，图中的节点可以有任意数量的连接，并且可以包含循环（Cycle）。

图的基本构成要素

  • 顶点 (Vertex / Node)：图中的基本元素，代表一个实体或对象。
  • 边 (Edge / Link)：连接图中的两个顶点的线。边代表顶点之间的关系。

图有哪些类型？

根据边是否具有方向、是否包含权重以及其他属性，图可以分为多种类型：

  • 无向图 (Undirected Graph)：边没有方向，如果存在从顶点 A 到顶点 B 的边，则也存在从 B 到 A 的边，它们是同一条边。
  • 有向图 (Directed Graph / Digraph)：边具有方向，从顶点 A 到顶点 B 的边不意味着存在从 B 到 A 的边。方向很重要。
  • 加权图 (Weighted Graph)：图的边被赋予一个数值，称为权重（Weight）或成本（Cost），通常表示距离、时间或容量等。
  • 无权图 (Unweighted Graph)：图的边没有关联的权重，所有边的成本都被视为相等（通常是 1）。
  • 简单图 (Simple Graph)：不包含自环（连接顶点自身的边）或平行边（连接同一对顶点的多条边）的图。
  • 多重图 (Multigraph)：允许存在平行边的图。
  • 连通图 (Connected Graph)：在无向图中，如果任意两个顶点之间都存在一条路径，则称该图是连通的。
  • 强连通图 (Strongly Connected Graph)：在有向图中，如果任意一对顶点 (u, v)，都存在从 u 到 v 的路径以及从 v 到 u 的路径，则称该图是强连通的。
  • 非循环图 (Acyclic Graph)：不包含任何循环的图。有向非循环图（DAG）是其中一个重要的类型，广泛用于表示依赖关系或流程。

图数据结构如何表示？（内存中如何存储？）

在计算机内存中存储图主要有两种常用的方法，它们各有优缺点，适用于不同的场景。

邻接矩阵 (Adjacency Matrix)

使用一个二维数组（或矩阵）来表示图。假设图有 V 个顶点，则使用一个 V × V 的矩阵。

  • 对于无权图：矩阵 `adj[i][j]` 的值为 1 表示顶点 i 和顶点 j 之间存在一条边，为 0 表示不存在边。对于无向图，矩阵是对称的，即 `adj[i][j] = adj[j][i]`。
  • 对于加权图：矩阵 `adj[i][j]` 的值为顶点 i 到顶点 j 的边的权重。如果不存在边，则可以使用一个特殊的值（如 0 或无穷大，取决于上下文）来表示。

邻接矩阵的优点：

  • 检查任意两个顶点之间是否存在边的时间复杂度是 O(1)。
  • 添加或删除边的时间复杂度也是 O(1)。

邻接矩阵的缺点：

  • 空间复杂度非常高，为 O(V²)，其中 V 是顶点数。即使图非常稀疏（边很少），也需要这么大的空间。
  • 查找一个顶点的所有邻居需要遍历该顶点的整行或整列，时间复杂度是 O(V)。

邻接表 (Adjacency List)

使用一个数组或列表，其中数组的每个索引代表图中的一个顶点。数组的每个元素又是一个列表（或链表、动态数组等），存储与该顶点直接相连的所有顶点。

  • 对于无权图：列表存储相邻顶点的索引。
  • 对于加权图：列表存储相邻顶点及其对应边的权重组成的对或结构。
  • 对于有向图：如果存在从 i 到 j 的有向边，则只在顶点 i 的列表中添加 j。
  • 对于无向图：如果存在顶点 i 和 j 之间的边，则需要在 i 的列表中添加 j，同时在 j 的列表中添加 i。

邻接表的优点：

  • 空间复杂度相对较低，为 O(V + E)，其中 V 是顶点数，E 是边数。对于稀疏图（E 远小于 V²）来说，这比邻接矩阵节省大量空间。
  • 查找一个顶点的所有邻居（即遍历其邻接列表）的时间复杂度取决于该顶点的度（连接的边数），通常是 O(degree(V))。

邻接表的缺点：

  • 检查任意两个顶点之间是否存在边需要遍历其中一个顶点的邻接列表，时间复杂度是 O(degree(V))，最坏情况下是 O(V)。
  • 添加或删除边的时间复杂度通常是 O(degree(V))，因为可能需要在列表中查找并删除顶点。

何时选择哪种表示法？

选择邻接矩阵还是邻接表取决于图的特性和需要执行的操作频率。

  • 对于密集图（边数 E 接近 V²）且需要频繁检查任意两点之间是否存在边：邻接矩阵可能是更好的选择，因为 O(V²) 的空间浪费不多，而检查边的 O(1) 优势明显。
  • 对于稀疏图（边数 E 远小于 V²）且需要频繁遍历一个顶点的邻居：邻接表是更好的选择，因为它节省空间，并且遍历邻居的速度更快。

在实际应用中，特别是处理大型图（如社交网络），通常使用邻接表或其变种，因为现实世界的图往往非常稀疏。

如何执行图的基本操作？

基于上述表示法，可以实现图的各种基本操作：

添加顶点

向图中加入一个新的顶点。

  • 邻接矩阵：需要增加矩阵的维度。如果动态调整大小，可能需要复制整个矩阵（成本较高）。如果预先分配足够大的矩阵，则只需标记一个新的“可用”行/列（O(1)）。
  • 邻接表：在表示顶点的数组/列表中添加一个新的空列表即可（通常是 O(1) 或平摊 O(1)）。

删除顶点

从图中移除一个顶点及其所有关联的边。

  • 邻接矩阵：将对应行和列全部清零或标记为无效。如果需要压缩空间，成本很高（O(V²)）。
  • 邻接表：移除对应顶点的列表，并在所有其他顶点的邻接列表中移除对该被删除顶点的引用。这可能需要遍历所有其他顶点的列表，成本较高（最坏 O(V+E)）。

添加边

在两个现有顶点之间建立连接。

  • 邻接矩阵：直接在矩阵对应的 `adj[i][j]` 位置设置值（1 或权重）。O(1)。对于无向图，还需要设置 `adj[j][i]`。
  • 邻接表：在顶点 i 的列表中添加顶点 j。对于无向图，还要在顶点 j 的列表中添加顶点 i。如果需要检查是否已存在边以避免平行边，时间取决于列表查找（O(degree)）。如果不检查，通常是 O(1)。

删除边

移除两个顶点之间的连接。

  • 邻接矩阵：直接在矩阵对应的 `adj[i][j]` 位置设置值（0 或表示无连接的值）。O(1)。对于无向图，还需要设置 `adj[j][i]`。
  • 邻接表：在顶点 i 的列表中找到并移除顶点 j。对于无向图，还要在顶点 j 的列表中找到并移除顶点 i。这需要列表查找和删除操作，时间取决于列表实现和度（O(degree)）。

查找顶点的所有邻居

获取与给定顶点直接相连的所有顶点。

  • 邻接矩阵：遍历该顶点对应的行（或列）。时间复杂度为 O(V)。
  • 邻接表：直接访问该顶点对应的列表并遍历其元素。时间复杂度为 O(degree(V))。

如何遍历图？（两种主要方法）

图的遍历是指系统地访问图中的所有顶点和边，且每个顶点和边只被访问一次（或按特定规则访问）。最常见的两种遍历方法是广度优先搜索和深度优先搜索。

广度优先搜索 (Breadth-First Search, BFS)

BFS 从起始顶点开始，先访问其所有直接邻居，然后访问这些邻居的所有未访问过的邻居，依此类推，层层向外扩展。它使用一个队列 (Queue) 来管理待访问的顶点。

基本思想：

  1. 从起始顶点开始，将其标记为已访问并加入队列。
  2. 当队列不为空时，取出队头顶点。
  3. 访问该顶点的所有未访问过的邻居。将这些邻居标记为已访问并加入队列。
  4. 重复步骤 2 和 3 直到队列为空。

BFS 常用于查找无权图中的最短路径、查找连通分量或爬虫等。时间复杂度通常是 O(V + E)。

深度优先搜索 (Depth-First Search, DFS)

DFS 从起始顶点开始，沿着一条路径尽可能深入地访问，直到不能再深入为止，然后回溯到上一个顶点，继续探索其他路径。它可以使用递归或栈 (Stack) 来实现。

基本思想：

  1. 从起始顶点开始，将其标记为已访问。
  2. 访问该顶点的第一个未访问过的邻居。
  3. 递归地对这个邻居顶点执行 DFS。
  4. 如果没有未访问过的邻居，则回溯到上一个顶点。
  5. 重复直到所有可达顶点都被访问。

DFS 常用于检测图中是否存在循环、查找连通分量、拓扑排序等。时间复杂度通常是 O(V + E)。

如何解决一些复杂的图问题？

图数据结构是解决许多复杂计算问题的基础。通过在图上运行特定的算法，可以找出顶点之间的关系、最优路径等。

如何寻找最短路径？

在加权图或无权图中，寻找两个顶点之间路径上总权重（或边数）最小的路径。

  • 无权图：可以使用 BFS 来找到最短路径，因为它按层扩展，第一次到达目标顶点时，路径就是最短的。
  • 非负权加权图：常用的算法是 Dijkstra（迪杰斯特拉）算法。它从源点开始，逐步扩展最短路径树，直到到达目标顶点或覆盖所有顶点。
  • 包含负权边的加权图：如果图中不包含负权循环，可以使用 Bellman-Ford（贝尔曼-福特）算法。如果存在负权循环，则可能没有最短路径。
  • 所有顶点对之间的最短路径：Floyd-Warshall（弗洛伊德-沃舍尔）算法或多次运行 Dijkstra/Bellman-Ford 算法。

如何检测图中是否存在循环？

循环是一条从某个顶点出发，经过一系列边最终回到该顶点的路径。

  • 对于无向图：可以使用 DFS。如果在 DFS 过程中，遇到一个已经访问过的顶点，且该顶点不是当前顶点的直接父节点，则说明存在循环。
  • 对于有向图：也可以使用 DFS。如果在 DFS 过程中，遇到一个当前正在递归栈中的顶点（即正在被访问但尚未完成其所有子树访问的顶点），则说明存在循环。这需要一个额外的状态来标记“正在访问中”的顶点。

如何找到图的连通分量？

在无向图中，连通分量是指一个最大的子图，其中任意两个顶点都是连通的。在有向图中，有强连通分量的概念（任意两点之间互相可达）。

  • 可以使用 BFS 或 DFS。从一个未访问过的顶点开始进行遍历（BFS 或 DFS），所有在这次遍历中访问到的顶点就构成一个连通分量。重复此过程，直到所有顶点都被访问过。

如何找到最小生成树？

对于一个连通的无向加权图，最小生成树（Minimum Spanning Tree, MST）是图的一个子图，它是一棵树（包含原图的所有顶点，没有循环），并且所有边的权重之和最小。

  • 常用的算法有 Prim（普里姆）算法和 Kruskal（克鲁斯卡尔）算法。Prim 算法逐步从一个顶点开始扩展最小生成树，而 Kruskal 算法按边的权重从小到大选择边，同时避免形成循环。

图数据结构在哪里被使用？（实际应用场景）

图数据结构因其强大的建模能力，在众多领域都有广泛的应用。

  • 社交网络：
    用户是顶点，用户之间的关系（关注、好友等）是边。用于分析社交关系、推荐好友、社区检测等。
  • 地图与导航系统：
    地点（城市、路口）是顶点，道路是边，道路的长度、通行时间或交通状况是边的权重。用于计算两点之间的最短路径、规划路线。
  • 推荐系统：
    用户、物品（商品、电影）是顶点，用户对物品的行为（购买、浏览、评分）是边，边可能带有权重表示行为强度。用于发现用户兴趣、进行个性化推荐。
  • 知识图谱：
    实体（人、地点、概念）是顶点，实体之间的关系是边（如“出生在”、“首都”）。用于组织和查询结构化知识，支持问答系统和语义搜索。
  • 软件依赖管理：
    软件包或模块是顶点，依赖关系是边（例如“A 依赖于 B”）。用于确定安装顺序、检测循环依赖。
  • 计算机网络：
    计算机或路由器是顶点，网络连接是边。用于路由协议、网络拓扑分析。
  • 生物信息学：
    蛋白质、基因是顶点，它们之间的相互作用是边。用于分析分子网络、基因调控。
  • 电路设计：
    电子元件是顶点，连接导线是边。用于电路分析和布局。
  • 项目管理：
    任务或活动是顶点，任务之间的先后依赖关系是边。用于关键路径分析。

这些只是图数据结构应用的一小部分例子，其灵活性使得它能够表示和解决各种复杂的互连问题。

图数据结构