图的实现与操作

### 图的实现与操作 #### 一、引言 图是一种重要的非线性数据结构，在计算机科学中有着广泛的应用，例如在社交网络分析、路线规划、编译原理等多个领域都有其身影。图由一系列节点（顶点）以及连接这些节点的边组成。本篇文章将详细介绍如何使用 C++ 实现图的数据结构，并且演示两种常见的图存储方式：邻接矩阵和邻接表，以及基于这两种存储方式的遍历算法。 #### 二、邻接矩阵 邻接矩阵是一种通过二维数组来表示图中各个顶点之间关系的方法。对于一个具有 n 个顶点的图来说，可以用一个 n×n 的二维数组 G 来表示该图。如果顶点 i 和顶点 j 之间存在一条边，则 G[i][j] 的值为 1 或者边的权重；否则为 0。 ##### 2.1 邻接矩阵的实现 ```cpp void InitGraph(MGraph &G, int n) { // 分配内存空间 G = new int*[n]; for (int i = 0; i < n; i++) G[i] = new int[n]; // 初始化所有值为 0 for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) G[i][j] = 0; } void CreateGraph(MGraph &G, int n) { // 输入边的数量 cout << "输入无向图中边的总数量: "; int e; cin >> e; // 输入每条边的起点和终点序号 cout << "\n输入每条边的起点和终点序号(注：结点编号范围为 0~" << n - 1 << "):\n"; for (int k = 1; k <= e; k++) { cout << "\n第 " << k << " 对边："; int i, j; cin >> i >> j; if (i > n || j > n || i < 0 || j < 0) return; G[i][j] = G[j][i] = 1; } } ``` ##### 2.2 深度优先搜索 (DFS) 深度优先搜索是一种沿着图的深度遍历的算法。它首先选择一个顶点作为起始顶点，然后尽可能深地搜索这个顶点的所有分支。 ```cpp void dfsMGraph(MGraph G, int n, int i) { visited[i] = 1; cout << i << "==>"; for (int j = 0; j < n; j++) if (G[i][j] != 0 && !visited[j]) dfsMGraph(G, n, j); } ``` ##### 2.3 广度优先搜索 (BFS) 广度优先搜索是从根节点开始，然后逐层遍历每一层的所有节点，直到所有的节点都被访问过。 ```cpp void bfsMGraph(MGraph G, int n, int i) { int *q = new int[n]; int front = 0, rear = 0; cout << i << "==>"; visited[i] = 1; q[rear] = i; rear = (rear + 1) % n; while (front != rear) { int k = q[front]; front = (front + 1) % n; for (int j = 0; j < n; j++) { if (G[k][j] != 0 && !visited[j]) { cout << j << "==>"; visited[j] = true; q[rear] = j; rear = (rear + 1) % n; } } } } ``` #### 三、邻接表 邻接表是另一种常用的图的存储结构，对于每个顶点 i，邻接表会存储一个链表，链表中的每一个元素代表了与顶点 i 相邻的顶点及其相关信息（如权重等）。 ##### 3.1 邻接表的实现 ```cpp void InitAdj(adjlist &G, int n) { G = new VNode[n]; for (int i = 0; i < n; i++) { G[i].data = i; G[i].nextarc = NULL; } } void CreateAdj(adjlist &G, int n) { int e; cout << "输入图的总边数："; cin >> e; cout << "\n输入每条边的起点和终点序号(注：结点编号范围为 0~" << n - 1 << "):\n"; for (int k = 1; k <= e; k++) { cout << "\n第 " << k << " 对边："; int i, j; cin >> i >> j; if (i > n || j > n || i < 0 || j < 0) return; ArcNode *p = new ArcNode; p->adjvex = j; p->weight = 1; p->nextarc = G[i].nextarc; G[i].nextarc = p; p = new ArcNode; p->adjvex = i; p->weight = 1; p->nextarc = G[j].nextarc; G[j].nextarc = p; } } ``` ##### 3.2 深度优先搜索 (DFS) ```cpp void dfsAdj(adjlist G, int n, int i) { cout << i << "==>"; visited[i] = true; ArcNode *p = G[i].nextarc; while (p != NULL) { int j = p->adjvex; if (!visited[j]) dfsAdj(G, n, j); p = p->nextarc; } } ``` ##### 3.3 广度优先搜索 (BFS) ```cpp void bfsAdj(adjlist G, int n, int i) { int *q = new int[n]; int front = 0, rear = 0; cout << i << "==>"; visited[i] = true; q[rear] = i; rear = (rear + 1) % n; while (front != rear) { int k = q[front]; front = (front + 1) % n; ArcNode *p = G[k].nextarc; while (p != NULL) { int j = p->adjvex; if (!visited[j]) { cout << j << "==>"; visited[j] = true; q[rear] = j; rear = (rear + 1) % n; } p = p->nextarc; } } } ``` #### 四、总结 本文介绍了图的两种主要存储方式——邻接矩阵和邻接表，以及基于这两种存储方式的深度优先搜索和广度优先搜索算法。邻接矩阵适用于密集图，即图中的边较多的情况；而邻接表则更适合稀疏图，即图中的边较少的情况。根据具体应用场景的不同，可以选择适合的存储方式来提高效率。此外，深度优先搜索和广度优先搜索都是图遍历的重要方法，它们各有特点，可以根据实际需求灵活运用。