图论基础和表示

目录

1. 图的基本概念
2. 图的表示方法
   • 邻接矩阵
   • 邻接表
   • 关联矩阵
3. 无向图与有向图
4. 特殊类型的图
5. 图的存储方式对比与应用
6. 参考资料

1. 图的基本概念

图（Graph） 是由 顶点（Vertex） 和 边（Edge） 组成的数学结构，通常表示为 G = (V, E)，其中：

• V（Vertex Set）：顶点集合，表示图中的节点；
• E（Edge Set）：边集合，表示图中顶点之间的连接关系。

根据边的方向性，图可以分为：

• 无向图（Undirected Graph）：边无方向，表示两个顶点是相互连接的；
• 有向图（Directed Graph）：边有方向，表示从一个顶点指向另一个顶点。

2. 图的表示方法

2.1 邻接矩阵（Adjacency Matrix）

邻接矩阵是一个 n × n 的二维数组，用于表示图中的边：

• 无向图：若顶点 ii 和顶点 jj 之间有边，则 A[i][j]=A[j][i]=1A[i][j] = A[j][i] = 1；否则为 0。
• 有向图：若存在从 ii 到 jj 的有向边，则 A[i][j]=1A[i][j] = 1，否则为 0。
• 加权图：若边有权值 ww，则 A[i][j]=wA[i][j] = w；没有边则 A[i][j]=∞A[i][j] = ∞ 或 0。

优缺点：

• 优点：查询两个顶点是否相邻的时间复杂度为 O(1)O(1)。
• 缺点：存储空间为 O(n2)O(n^2)，对于稀疏图（边少）不够高效。

例子：

无向图邻接矩阵：

  0  1  2  3  
0 0  1  1  0  
1 1  0  1  1  
2 1  1  0  1  
3 0  1  1  0  

2.2 邻接表（Adjacency List）

邻接表使用 链表 或 动态数组 记录每个顶点的邻接顶点。适用于稀疏图，存储方式：

• 每个顶点有一个链表，存储所有与其相连的顶点。
• 有向图：只存储出度邻接点。
• 无向图：两个顶点互相存储。

优缺点：

• 优点：存储空间为 O(V+E)O(V + E)，适用于稀疏图。
• 缺点：查询两点是否相邻需要 O(degree)O(degree)。

例子：

0 -> [1, 2]  
1 -> [0, 2, 3]  
2 -> [0, 1, 3]  
3 -> [1, 2]  

2.3 关联矩阵（Incidence Matrix）

关联矩阵是一个 n × m 的矩阵，其中：

• n：顶点数；
• m：边数；
• 无向图：
  • 若顶点 viv_i 与边 eje_j 关联，则 M[i][j]=1M[i][j] = 1；
  • 否则 M[i][j]=0M[i][j] = 0。
• 有向图：
  • 边的起点设为 -1，终点设为 1。

优缺点：

• 优点：适用于超图（Hypergraph）和某些数学计算。
• 缺点：存储空间大，不常用。

3. 无向图与有向图

4. 特殊类型的图

4.1 完全图（Complete Graph）

• 定义：每对顶点间均有一条边。
• 边数：
  • 无向图：E=V(V−1)2E = \frac{V(V-1)}{2}。
  • 有向图：E=V(V−1)E = V(V-1)。

4.2 二分图（Bipartite Graph）

• 定义：顶点可分为两组，组内无边。
• 应用：任务分配、匹配问题。

5. 图的存储方式对比与应用

6. 参考资料

出站链接

• Graph Theory – Wikipedia
• Discrete Mathematics and Graph Theory – GeeksforGeeks
• Introduction to Graph Theory – MIT OpenCourseWare

站内链接

• 数据结构与算法解析
• 最短路径算法
• 最小生成树