数据结构-图(Graph)

https://zhuanlan.zhihu.com/p/721468950

数据结构-图（Graph）教程

一、图的基本概念

1. 什么是图？

图是一种比树更复杂的非线性数据结构，它由顶点（Vertex） 和边（Edge） 两部分组成，用于表示多对多的关系。

• 顶点：图中的基本元素，可表示具体事物（如城市、人、网络节点等）。
• 边：连接两个顶点的线，表示顶点之间的关系。

2. 图与树的区别

特性	树	图
连接性	有且仅有一条路径	可能有多条路径
环路	无环路	可能有环路
根节点	有唯一根节点	无 root 概念
边的方向	父到子（隐含方向）	可无向或有向

二、图的分类

1. 按边的方向划分

• 无向图：边没有方向，顶点A与B相连等价于B与A相连（用不带箭头的线表示）。
  例：社交网络中“朋友关系”（A是B的朋友，B也是A的朋友）。
• 有向图：边有方向，顶点A到B的边与B到A的边是两条不同边（用带箭头的线表示）。
  例：网络中的“关注关系”（A关注B，不代表B关注A）。

2. 按边的权重划分

• 无权图：边没有权重，仅表示“存在关系”。
• 带权图：边有数值权重，表示关系的强度（如距离、成本）。
  例：地图中城市之间的道路长度。

三、图的基本术语

• 顶点的度：与顶点相连的边的数量。
  • 有向图中细分：入度（指向该顶点的边数）和出度（从该顶点出发的边数）。
• 路径：从一个顶点到另一个顶点经过的边的序列。
• 环：起点和终点相同的路径（如A→B→C→A）。
• 连通图（无向图）：任意两个顶点之间都存在路径。
• 强连通图（有向图）：任意两个顶点之间双向都存在路径。
• 子图：从原图中选取部分顶点和边组成的新图。

四、图的存储方式

1. 邻接矩阵（Adjacency Matrix）

• 原理：用一个二维数组graph[n][n]表示（n为顶点数）。
  • 无向图：graph[i][j] = 1表示顶点i与j相连，0表示不相连；矩阵沿对角线对称。
  • 有向图：graph[i][j] = 1表示从i到j有边；矩阵不一定对称。
  • 带权图：用权重值代替1，用∞或0表示无连接。
• 示例：无向图的邻接矩阵（顶点0-3）

  [
    [0, 1, 1, 0],  // 0与1、2相连
    [1, 0, 0, 1],  // 1与0、3相连
    [1, 0, 0, 1],  // 2与0、3相连
    [0, 1, 1, 0]   // 3与1、2相连
  ]
  

• 优缺点：
  • 优点：查询两顶点是否相连效率高（O(1)）。
  • 缺点：空间复杂度高（O(n²)），适合顶点数少的图。

2. 邻接表（Adjacency List）

• 原理：用数组+链表（或动态数组）存储，数组索引表示顶点，每个索引对应的值是与该顶点相连的顶点列表。
• 示例：同上无向图的邻接表

  0: [1, 2]
  1: [0, 3]
  2: [0, 3]
  3: [1, 2]
  

• 优缺点：
  • 优点：空间效率高（O(n + e)，e为边数），适合稀疏图。
  • 缺点：查询两顶点是否相连需遍历链表（O(k)，k为顶点的度）。

五、图的遍历算法

遍历目的：按一定规则访问图中所有顶点，分为深度优先搜索（DFS） 和广度优先搜索（BFS）。

1. 深度优先搜索（DFS）

• 思路：从起点出发，优先探索一条路径到最深层，无法前进时回溯，继续探索其他路径（类似“走迷宫”）。
• 实现方式：递归或栈。
• 示例步骤（无向图，起点0）：
  0 → 1 → 3 → 2（递归终止，回溯完成）。

2. 广度优先搜索（BFS）

• 思路：从起点出发，优先访问所有相邻顶点（第一层），再依次访问相邻顶点的相邻顶点（第二层），以此类推（类似“水波扩散”）。
• 实现方式：队列。
• 示例步骤（无向图，起点0）：
  0 → 1 → 2 → 3（按层次依次访问）。

六、图的应用场景

1. 路径规划：地图软件中最短路径计算（如Dijkstra算法、Floyd算法）。
2. 社交网络：好友推荐（基于共同好友的图分析）。
3. 网络拓扑：计算机网络中节点连接关系的表示。
4. 依赖关系：项目管理中任务依赖关系（AOV网、AOE网）。

七、总结

• 图是由顶点和边组成的非线性结构，可表示复杂的多对多关系。
• 核心分类：无向/有向图、无权/带权图。
• 存储方式：邻接矩阵（适合稠密图）、邻接表（适合稀疏图）。
• 遍历算法：DFS（深度优先）和BFS（广度优先）是基础，支撑后续复杂应用。

掌握图的概念和算法，能有效解决现实中大量涉及关系网络的问题。