数据结构之图结构

前言

图结构是处理复杂关系数据的关键工具，从社交网络中的人际关系分析，到交通网络的路径规划，再到搜索引擎的网页链接分析，都发挥着不可或缺的作用。本文我将初步探讨图结构的基本概念、存储方式、遍历算法以及实际应用场景，并结合代码示例，带你初步进入这一重要的数据结构。

一、图结构的基本概念

1.1 图的定义

图（Graph）是由顶点（Vertex）集合 $V$ 和边（Edge）集合 $E$ 组成的二元组，记为 $G=(V,E)$。顶点用于表示数据对象，边则表示顶点之间的关系。根据边是否有方向，图可分为无向图和有向图：

• 无向图：边没有方向，例如表示城市之间的道路连接，道路是双向通行的。在无向图中，若顶点 $u$ 和 $v$ 之间有边相连，则这条边可表示为 $(u,v)$，且 $(u,v)$ 与 $(v,u)$ 表示同一条边。
  

• 有向图：边具有方向，比如社交网络中用户之间的关注关系，关注是单向的。在有向图中，从顶点 $u$ 到顶点 $v$ 的边表示为 $⟨u,v⟩$，它与 $⟨v,u⟩$ 是不同的边。

• 

1.2 图的相关术语

• 顶点的度：在无向图中，顶点的度是指与该顶点相连的边的数量；在有向图中，顶点的度分为入度和出度，入度是指以该顶点为终点的边的数量，出度是指以该顶点为起点的边的数量。

• 边的权值：有些图的边会附带一个数值，称为权值，用于表示顶点之间关系的某种度量，如距离、成本等。这样的图称为带权图。

• 路径：由一系列顶点和连接这些顶点的边组成的序列。如果路径的起点和终点相同，则称为回路或环。

• 连通图：在无向图中，如果任意两个顶点之间都存在路径，则称该图为连通图；在有向图中，如果对于任意两个顶点 $u$ 和 $v$，都存在从 $u$ 到 $v$ 和从 $v$ 到 $u$ 的路径，则称该图为强连通图。

二、图的存储方式

2.1 邻接矩阵

邻接矩阵是一种用二维数组来表示图的存储方式。对于具有 $n$ 个顶点的图，其邻接矩阵是一个 $n\times n$ 的矩阵 $A$。在无向图中，如果顶点 $i$ 和 $j$ 之间有边相连，则 $A[i][j]=A[j][i]=1$；否则 $A[i][j]=A[j][i]=0$。在带权图中，若顶点 $i$ 和 $j$ 之间有边相连，且边的权值为 $w$，则 $A[i][j]=A[j][i]=w$；若没有边相连，通常用一个特殊值（如无穷大）表示。

# 无向图的邻接矩阵示例
graph = [[0, 1, 1, 0],[1, 0, 0, 1],[1, 0, 0, 1],[0, 1, 1, 0]
]

邻接矩阵的优点是实现简单，便于判断两个顶点之间是否有边相连，并且可以快速获取顶点的度；缺点是空间复杂度较高，为 $O(n^2)$，对于边数较少的稀疏图，会造成大量的空间浪费。

2.2 邻接表

邻接表是一种链式存储结构，它为图中的每个顶点建立一个单链表，链表中的节点表示与该顶点相邻的顶点及其相关信息（如边的权值）。在无向图中，每个顶点的链表中存储其所有相邻顶点；在有向图中，每个顶点的链表存储以该顶点为起点的所有边的终点顶点。

# 无向图的邻接表示例
graph = {0: [1, 2],1: [0, 3],2: [0, 3],3: [1, 2]
}

邻接表的优点是空间效率高，适用于存储稀疏图，空间复杂度为 $O(n+e)$（$n$ 为顶点数，$e$ 为边数）；缺点是判断两个顶点之间是否有边相连需要遍历链表，时间复杂度较高，为 $O(d)$（$d$ 为顶点的度）。

三、图的遍历算法

3.1 深度优先搜索（DFS）

深度优先搜索类似于树的先序遍历，它从图的某个顶点出发，沿着一条路径尽可能深地访问顶点，直到无法继续，然后回溯到上一个顶点，继续探索其他路径，直到访问完所有可达顶点。DFS 可以使用递归或栈来实现。

# 使用递归实现无向图的DFS
def dfs(graph, vertex, visited):visited.add(vertex)print(vertex)for neighbor in graph[vertex]:if neighbor not in visited:dfs(graph, neighbor, visited)graph = {0: [1, 2],1: [0, 3],2: [0, 3],3: [1, 2]
}
visited = set()
dfs(graph, 0, visited)

DFS 的时间复杂度在邻接矩阵表示下为 $O(n^2)$，在邻接表表示下为 $O(n+e)$。它常用于寻找图中的连通分量、拓扑排序等场景。

3.2 广度优先搜索（BFS）

广度优先搜索类似于树的层序遍历，它从图的某个顶点出发，先访问该顶点的所有相邻顶点，然后再依次访问这些相邻顶点的未访问过的相邻顶点，以此类推，直到访问完所有可达顶点。BFS 通常使用队列来实现。

# 无向图的BFS实现
from collections import dequedef bfs(graph, start):visited = set()queue = deque([start])visited.add(start)while queue:vertex = queue.popleft()print(vertex)for neighbor in graph[vertex]:if neighbor not in visited:queue.append(neighbor)visited.add(neighbor)graph = {0: [1, 2],1: [0, 3],2: [0, 3],3: [1, 2]
}
bfs(graph, 0)

BFS 的时间复杂度同样在邻接矩阵表示下为 $O(n^2)$，在邻接表表示下为 $O(n+e)$。它常用于寻找最短路径（在无权图中）、最小生成树等问题。

四、图结构应用场景

4.1 社交网络分析

在社交网络中，用户可以看作图的顶点，用户之间的关注、好友关系等可以看作边。通过图结构可以分析用户的社交圈子、影响力，例如找出某个用户的所有好友及其好友的好友，或者计算用户之间的最短社交距离。

4.2 路径规划

在交通网络中，城市或地点是顶点，道路是边，边的权值可以是距离、通行时间等。利用图的最短路径算法（如迪杰斯特拉算法、弗洛伊德算法），可以实现导航系统中的路径规划功能，帮助用户找到从起点到终点的最优路线。

4.3 任务调度

在项目管理中，任务可以看作顶点，任务之间的依赖关系看作边。通过图的拓扑排序算法，可以确定任务的执行顺序，确保在执行某个任务之前，其依赖的任务已经完成，从而合理安排项目进度。

4.4 网络通信

在计算机网络中，节点和连接可以用图来表示。通过图的分析可以优化网络拓扑结构，检测网络中的故障节点或链路，提高网络的可靠性和效率。

总结

图结构作为一种强大的数据结构，能够有效表示和处理复杂的关系型数据。从基本概念到存储方式，从遍历算法到实际应用，图结构涵盖了丰富的知识和广泛的应用场景。掌握图结构的相关知识，不仅有助解决算法中的复杂问题，还能在实际软件开发、数据分析等领域发挥重要作用。本文只是初始图结构，最小生成树最短路径等问题篇幅有限，感兴趣的请进我主页算法专题查看。

That’s all, thanks for reading!
觉得有用就点个赞、收进收藏夹吧！关注我，获取更多干货～