图数据结构：定义、核心特性与基础概念解析
一、什么是图数据结构？
在计算机科学中，图(Graph) 是一种非线性数据结构，用于表示对象之间的多对多关系。与线性结构(如数组、链表)和分层结构(如树)不同，图没有严格的顺序或层次限制，能够灵活地建模现实世界中复杂的关联关系。
从数学角度来看，图可以定义为一个二元组 ( G = (V, E) )，其中：
- ( V ) (Vertex) 是顶点(或节点)的非空有限集合
- ( E ) (Edge) 是边的有限集合，每条边连接两个顶点，表示它们之间的关系
二、图的核心组件
2.1 顶点(Vertex)
顶点是图的基本组成单元，用于表示实体或对象。例如，在社交网络中，顶点可以表示用户；在地图应用中，顶点可以表示城市。
2.2 边(Edge)
边是连接两个顶点的线段或弧，表示顶点之间的关系。根据边是否有方向，图可以分为两类：
有向图(Directed Graph)
边具有方向，用带箭头的线段表示。例如，在网页链接图中，边从当前页面指向链接的目标页面，表示浏览方向。
无向图(Undirected Graph)
边没有方向，用线段表示。例如，在社交网络的好友关系中，A和B是好友意味着B和A也是好友。
2.3 权重(Weight)
边可以带有权重，表示关系的强度或代价。例如，在交通网络中，权重可以表示两个城市之间的距离或旅行时间。
三、图的基本类型
3.1 简 单图与多重图
- 简单图：任意两个顶点之间最多只有一条边，且没有顶点自身连接的边(自环)
- 多重图：允许两个顶点之间存在多条边，或顶点存在自环
3.2 连通图与非连通图
- 连通图：无向图中任意两个顶点之间都存在路径
- 非连通图：无向图中存在至少两个顶点之间没有路径
3.3 强连通图与弱连通图
- 强连通图：有向图中任意两个顶点之间都存在双向路径
- 弱连通图：有向图去掉方向后是连通图
3.4 加权图与无权图
- 加权图：边带有权重的图
- 无权图：边不带权重的图，或所有边权重相同
四、图的表示方法
4.1 邻接矩阵(Adjacency Matrix)
邻接矩阵是一个 ( n \times n ) 的二维数组，其中 ( n ) 是顶点的数量。如果顶点 ( i ) 和顶点 ( j ) 之间有边，则 ( matrix[i][j] = 1 ) (无权图)或权重值(加权图)；否则为 ( 0 )。
# 无向图的邻接矩阵表示
graph = [
[0, 1, 1, 0],
[1, 0, 1, 1],
[1, 1, 0, 1],
[0, 1, 1, 0]
]4.2 邻接表(Adjacency List)
邻接表是一个数组或链表的集合，每个顶点对应一个列表，包含与该顶点直接相连的所有顶点。
# 有向图的邻接表表示
graph = {
'A': ['B', 'C'],
'B': ['C', 'D'],
'C': ['D'],
'D': ['A']
}五、图的核心算法
5.1 图的遍历
遍历是指访问图中所有顶点的过程，主要有两种方法：
深度优先搜索(DFS)
从起始顶点开始，尽可能深地访问邻接顶点，直到无法继续，然后回溯。
def dfs(graph, start, visited=None):
if visited is None:
visited = set()
visited.add(start)
print(start, end=' ')
for neighbor in graph[start]:
if neighbor not in visited:
dfs(graph, neighbor, visited)
return visited广度优先搜索(BFS)
从起始顶点开始，逐层访问所有邻接顶点，类似树的层序遍历。
from collections import deque
def bfs(graph, start):
visited = set()
queue = deque([start])
visited.add(start)
while queue:
vertex = queue.popleft()
print(vertex, end=' ')
for neighbor in graph[vertex]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
return visited5.2 最短路径算法
用于寻找两个顶点之间的最短路径：
- Dijkstra算法：用于加权图的单源最短路径，不能处理负权重
- Bellman-Ford算法：用于加权图的单源最短路径，可以处理负权重
- Floyd-Warshall算法：用于加权图的所有顶点对之间的最短路径
5.3 最小生成树
在连通加权无向图中，寻找一棵包含所有顶点且总权重最小的树：
- Kruskal算法：基于边的贪心算法，适合稀疏图
- Prim算法：基于顶点的贪心算法，适合稠密图
六、图的应用场景
6.1 社交网络
- 顶点：用户
- 边：好友关系、关注关系
- 应用：推荐系统、社区检测
6.2 交通网络
- 顶点：城市、交通枢纽
- 边：道路、铁路、航线
- 应用：路径规划、物流优化
6.3 网页链接
- 顶点：网页
- 边：超链接
- 应用：PageRank算法、搜索引擎
6.4 计算机网络
- 顶点：路由器、交换机
- 边：网络连接
- 应用：网络拓扑分析、路由算法
七、总结
图数据结构是一种强大的工具，能够建模现实世界中复杂的关联关系。理解图的核心概念、表示方法和算法对于解决许多实际问题至关重要。随着大数据和人工智能的发展，图数据结构在社交网络分析、知识图谱、推荐系统等领域的应用越来越广泛。
学习图数据结构不仅可以帮助我们更好地理解和解决复杂问题，还能培养我们的抽象思维和算法设计能力。
（此内容由 AI 辅助生成，仅供参考）