1. 图的定义和基本概念
在图论中,图(Graph)是由顶点(Vertex)和边(Edge)构成的集合。我们可以通过图来表示各种关系,比如社交网络中的人际关系、城市交通中的路线等。图的基本元素包括顶点和边。
1.1 图的基本组成
- 顶点(Vertex): 图中的基本单位,表示对象或元素。例如,社交网络中的“人”、城市图中的“城市”等。
- 边(Edge): 连接两个顶点的线,表示这些顶点之间的关系。例如,社交网络中的“朋友关系”、城市图中的“公路”。
图可以用不同的方式分类,主要包括以下几类:
- 有向图(Directed Graph): 边有方向。即边从一个顶点指向另一个顶点。例如,一个网页的链接。
- 无向图(Undirected Graph): 边没有方向,表示两个顶点之间的双向关系。例如,社交网络中的朋友关系。
- 加权图(Weighted Graph): 边有权重,表示边的“大小”或“成本”,例如地图中的路程长度。
- 非加权图(Unweighted Graph): 边没有权重,边只表示是否存在连接。
- 简单图(Simple Graph): 不包含自环和多重边,即每对顶点之间至多有一条边。
2. 图的存储结构
在计算机中,图的存储方式有多种,最常用的存储方式是 邻接矩阵 和 邻接表。
2.1 邻接矩阵(Adjacency Matrix)
邻接矩阵是一个二维数组,表示图中顶点之间的连接关系。如果图有 n 个顶点,那么邻接矩阵是一个 n x n 的矩阵。矩阵中的元素表示顶点之间是否有边,如果存在边,则值为 1 或 权重;如果不存在边,则值为 0 或无穷大。
- 优点:
- 判断两顶点之间是否有边的时间复杂度是 O(1)。
- 实现简单,适用于边数较多的图。
- 缺点:
- 空间复杂度为 O(n^2),对于稀疏图,空间浪费较大。
- 边的遍历时间复杂度较高,遍历所有边的时间是 O(n^2)。
2.2 邻接表(Adjacency List)
邻接表使用一个数组来存储每个顶点的邻接点,通常使用链表或动态数组来存储每个顶点的邻接点。这种存储方式适合稀疏图。
- 优点:
- 空间效率高,适合稀疏图,空间复杂度为 O(n + m),其中
n是顶点数,m是边数。 - 遍历顶点的所有邻接点时间复杂度为 O(d),其中 d 是顶点的度。
- 空间效率高,适合稀疏图,空间复杂度为 O(n + m),其中
- 缺点:
- 判断两顶点之间是否有边的时间复杂度是 O(d),其中 d 是顶点的度。
3. 数组模拟临界表存储
在图的实现中,通常用邻接表来存储图,因为它比邻接矩阵更节省空间。数组模拟邻接表存储时,我们用一个数组,每个数组的元素保存一个链表,链表中的节点表示与该顶点相连的其他顶点。
3.1 实现思路
- 定义一个结构体
Edge,表示图中的边,存储边的终点。 - 用一个
vector<vector<int>>或vector<list<int>>来表示邻接表。
3.2 示例代码
以下是使用邻接表来存储图并进行边的添加的代码:
#include <iostream>#include <vector>#include <list>using namespace std;
const int MAXN = 100; // 顶点最大数vector<int> adjList[MAXN]; // 邻接表
// 添加一条边void addEdge(int u, int v) { adjList[u].push_back(v); // 有向图,u -> v adjList[v].push_back(u); // 无向图,需要反向添加}
int main() { int n, m; // 顶点数n和边数m cin >> n >> m;
for (int i = 0; i < m; i++) { int u, v; cin >> u >> v; addEdge(u, v); }
// 输出邻接表 for (int i = 1; i <= n; i++) { cout << "Vertex " << i << ": "; for (int v : adjList[i]) { cout << v << " "; } cout << endl; }
return 0;}4. 图的遍历
图的遍历算法是图论中的一个基础问题,常见的遍历算法有 深度优先搜索(DFS) 和 广度优先搜索(BFS)。这两种算法分别使用递归和队列来遍历图中的顶点。
4.1 深度优先搜索(DFS)
DFS 是一种深度优先的遍历方式,它会从一个起始点出发,沿着一条路径一直深入直到没有未访问的邻接点,再回溯到上一个顶点。DFS 的特点是通过递归或栈来实现。
- 时间复杂度: O(V + E),其中 V 是顶点数,E 是边数。
- 空间复杂度: O(V),栈空间最多存储 V 个顶点。
#include <iostream>#include <vector>using namespace std;
vector<int> adjList[MAXN]; // 邻接表bool visited[MAXN]; // 记录访问状态
// 深度优先搜索void DFS(int u) { visited[u] = true; cout << u << " "; // 输出当前访问的顶点
// 递归访问与u相连的所有未访问的邻接点 for (int v : adjList[u]) { if (!visited[v]) { DFS(v); } }}
int main() { int n, m; cin >> n >> m;
// 构建邻接表 for (int i = 0; i < m; i++) { int u, v; cin >> u >> v; adjList[u].push_back(v); adjList[v].push_back(u); // 无向图 }
// 从节点1开始DFS遍历 DFS(1);
return 0;}4.2 广度优先搜索(BFS)
BFS 是一种层次优先的遍历方式,它会从起始点出发,首先访问所有邻接点,然后再访问每个邻接点的邻接点,以此类推。BFS 使用队列来实现。
- 时间复杂度: O(V + E),其中 V 是顶点数,E 是边数。
- 空间复杂度: O(V),队列最多存储 V 个顶点。
#include <iostream>#include <vector>#include <queue>using namespace std;
vector<int> adjList[MAXN]; // 邻接表bool visited[MAXN]; // 记录访问状态
// 广度优先搜索void BFS(int start) { queue<int> q; visited[start] = true; q.push(start);
while (!q.empty()) { int u = q.front(); q.pop(); cout << u << " "; // 输出当前访问的顶点
// 访问与u相连的所有未访问的邻接点 for (int v : adjList[u]) { if (!visited[v]) { visited[v] = true; q.push(v); } } }}
int main() { int n, m; cin >> n >> m;
// 构建邻接表 for (int i = 0; i < m; i++) { int u, v; cin >> u >> v; adjList[u].push_back(v); adjList[v].push_back(u); // 无向图 }
// 从节点1开始BFS遍历 BFS(1);
return 0;}总结
- 图的定义:图是由顶点和边组成的数据结构。图可以是有向的、无向的、加权的等。
- 图的存储结构:主要有邻接矩阵和邻接表两种。邻接矩阵适用于边多的图,而邻接表适用于稀疏图。
- 数组模拟邻接表:使用
vector或list来存储每个顶点的邻接点。
图的遍历:
- 深度优先搜索(DFS):利用递归或者栈的方式从一个顶点出发,尽可能深入地访问每个顶点。
- 广度优先搜索(BFS):利用队列的方式,从起始顶点开始,层层展开地访问图中的顶点。
这些基础知识和代码示例构成了理解和实现图论相关问题的基础。在实际应用中,掌握这些算法和数据结构将帮助你解决许多图相关的计算机问题。