6.图：多对多的非线性数据结构-平芜编程栈

一、什么是图？

图（Graph）是一种多对多的非线性数据结构，它由 ** 节点（Vertex）和边（Edge）** 组成：

节点：表示实体（如人、地点、设备）；
边：表示节点之间的关系（如连接、路径、交互）。

简单来说：

数组、链表是一对一的线性结构；
树是一对多的层次结构；
图是多对多的网状结构，任意两个节点之间都可能存在连接。

图在实际开发中应用非常广泛：

社交网络：用户是节点，关注 / 好友关系是边；
地图导航：地点是节点，道路是边；
计算机网络：设备是节点，网线 / 无线连接是边；
推荐系统：用户和商品是节点，点击 / 购买行为是边；
路由算法：路由器是节点，链路是边。

二、图的核心分类

1. 无向图 vs 有向图

无向图：边没有方向，节点之间双向连通（如朋友关系）；
有向图：边有方向，A→B 不代表 B→A（如关注关系）。

2. 带权图 vs 无权图

带权图：边上标有数值，表示距离、时间、代价等（如地图的道路长度）；
无权图：边没有数值，只表示存在连接（如社交网络的好友关系）。

3. 稀疏图 vs 稠密图

稀疏图：边数远少于完全图（如社交网络，大部分人只和少数人互动）；
稠密图：边数接近完全图（如全连接的路由器网络）。

4. 连通图 vs 非连通图

连通图：任意两个节点之间都有路径（如一个城市的道路网）；
非连通图：存在节点之间没有路径（如两个独立的岛屿）。

三、图的存储方式

图的存储主要有两种方式：邻接矩阵和邻接表。

1. 邻接矩阵

用二维数组存储图，matrix[i][j] = 1表示节点 i 和 j 之间有边，0表示没有边。

优点：

判断两个节点是否相连的时间复杂度为O(1)；
实现简单，适合稠密图。

缺点：

空间复杂度为O(n²)，当节点数很多时会非常占用空间。

代码实现：

#include <stdio.h> #include <stdlib.h> #define MAX_NODES 100 // 邻接矩阵结构体 typedef struct { int matrix[MAX_NODES][MAX_NODES]; // 二维数组存储边 int nodeCount; // 节点总数 } AdjacencyMatrix; // 初始化邻接矩阵 void initMatrix(AdjacencyMatrix* graph, int nodeCount) { graph->nodeCount = nodeCount; // 初始化所有边为0（无连接） for (int i = 0; i < nodeCount; i++) { for (int j = 0; j < nodeCount; j++) { graph->matrix[i][j] = 0; } } } // 添加无向边 void addUndirectedEdge(AdjacencyMatrix* graph, int u, int v) { graph->matrix[u][v] = 1; graph->matrix[v][u] = 1; } // 添加有向边 void addDirectedEdge(AdjacencyMatrix* graph, int u, int v) { graph->matrix[u][v] = 1; } // 打印邻接矩阵 void printMatrix(AdjacencyMatrix* graph) { printf("邻接矩阵：\n"); for (int i = 0; i < graph->nodeCount; i++) { for (int j = 0; j < graph->nodeCount; j++) { printf("%d ", graph->matrix[i][j]); } printf("\n"); } }

2. 邻接表

每个节点存储一个链表，只记录它能直接到达的邻居节点。

优点：

空间复杂度为O(n+e)，适合稀疏图；
遍历邻居的效率高。

缺点：

判断两个节点是否相连的时间复杂度为O(k)（k 是节点的邻居数）。

代码实现：

// 邻接表节点结构体 typedef struct AdjNode { int node; // 邻居节点编号 struct AdjNode* next; // 下一个邻居节点 } AdjNode; // 邻接表结构体 typedef struct { AdjNode* head[MAX_NODES]; // 每个节点的链表头 int nodeCount; // 节点总数 } AdjacencyList; // 初始化邻接表 void initList(AdjacencyList* graph, int nodeCount) { graph->nodeCount = nodeCount; // 初始化所有链表头为NULL for (int i = 0; i < nodeCount; i++) { graph->head[i] = NULL; } } // 添加无向边 void addUndirectedEdgeList(AdjacencyList* graph, int u, int v) { // 添加u→v AdjNode* newNode = (AdjNode*)malloc(sizeof(AdjNode)); newNode->node = v; newNode->next = graph->head[u]; graph->head[u] = newNode; // 添加v→u newNode = (AdjNode*)malloc(sizeof(AdjNode)); newNode->node = u; newNode->next = graph->head[v]; graph->head[v] = newNode; } // 添加有向边 void addDirectedEdgeList(AdjacencyList* graph, int u, int v) { AdjNode* newNode = (AdjNode*)malloc(sizeof(AdjNode)); newNode->node = v; newNode->next = graph->head[u]; graph->head[u] = newNode; } // 打印邻接表 void printList(AdjacencyList* graph) { printf("邻接表：\n"); for (int i = 0; i < graph->nodeCount; i++) { printf("节点 %d 的邻居：", i); AdjNode* p = graph->head[i]; while (p != NULL) { printf("%d ", p->node); p = p->next; } printf("\n"); } }

四、图的基本概念

1. 度（Degree）

无向图：节点的度是它连接的边数；
有向图：
- 入度：指向该节点的边数；
- 出度：从该节点出发的边数。

2. 路径

节点之间的边组成的序列，如 A→B→C。

3. 回路（环）

起点和终点相同的路径，如 A→B→C→A。

4. 简单路径

不重复经过任何节点的路径。

5. 完全图

每对节点之间都有边的图，n 个节点的完全图有n*(n-1)/2条边。

五、图的遍历方式

图的遍历是指访问图中的所有节点，且每个节点只访问一次。常见的遍历方式有两种：

1. 深度优先搜索（DFS）

从起始节点出发，尽可能深地访问分支，直到无法继续，再回溯到上一个节点。

代码实现（邻接表版）：

// 深度优先搜索 void dfs(AdjacencyList* graph, int start, int* visited) { // 标记当前节点已访问 visited[start] = 1; printf("%d ", start); // 遍历当前节点的所有邻居 AdjNode* p = graph->head[start]; while (p != NULL) { if (!visited[p->node]) { dfs(graph, p->node, visited); } p = p->next; } }

2. 广度优先搜索（BFS）

从起始节点出发，先访问所有直接邻居，再访问邻居的邻居，逐层向外扩展。

代码实现（邻接表版）：

#include <stdio.h> #include <stdlib.h> // 广度优先搜索 void bfs(AdjacencyList* graph, int start, int* visited) { // 使用队列存储待访问的节点 int queue[MAX_NODES]; int front = 0, rear = 0; // 标记起始节点已访问并入队 visited[start] = 1; queue[rear++] = start; while (front < rear) { int node = queue[front++]; printf("%d ", node); // 遍历当前节点的所有邻居 AdjNode* p = graph->head[node]; while (p != NULL) { if (!visited[p->node]) { visited[p->node] = 1; queue[rear++] = p->node; } p = p->next; } } }

六、完整代码示例

#include <stdio.h> #include <stdlib.h> #define MAX_NODES 100 // 邻接表节点结构体 typedef struct AdjNode { int node; struct AdjNode* next; } AdjNode; // 邻接表结构体 typedef struct { AdjNode* head[MAX_NODES]; int nodeCount; } AdjacencyList; // 初始化邻接表 void initList(AdjacencyList* graph, int nodeCount) { graph->nodeCount = nodeCount; for (int i = 0; i < nodeCount; i++) { graph->head[i] = NULL; } } // 添加无向边 void addUndirectedEdgeList(AdjacencyList* graph, int u, int v) { AdjNode* newNode = (AdjNode*)malloc(sizeof(AdjNode)); newNode->node = v; newNode->next = graph->head[u]; graph->head[u] = newNode; newNode = (AdjNode*)malloc(sizeof(AdjNode)); newNode->node = u; newNode->next = graph->head[v]; graph->head[v] = newNode; } // 打印邻接表 void printList(AdjacencyList* graph) { printf("邻接表：\n"); for (int i = 0; i < graph->nodeCount; i++) { printf("节点 %d 的邻居：", i); AdjNode* p = graph->head[i]; while (p != NULL) { printf("%d ", p->node); p = p->next; } printf("\n"); } } // 深度优先搜索 void dfs(AdjacencyList* graph, int start, int* visited) { visited[start] = 1; printf("%d ", start); AdjNode* p = graph->head[start]; while (p != NULL) { if (!visited[p->node]) { dfs(graph, p->node, visited); } p = p->next; } } // 广度优先搜索 void bfs(AdjacencyList* graph, int start, int* visited) { int queue[MAX_NODES]; int front = 0, rear = 0; visited[start] = 1; queue[rear++] = start; while (front < rear) { int node = queue[front++]; printf("%d ", node); AdjNode* p = graph->head[node]; while (p != NULL) { if (!visited[p->node]) { visited[p->node] = 1; queue[rear++] = p->node; } p = p->next; } } } // 释放邻接表内存 void freeList(AdjacencyList* graph) { for (int i = 0; i < graph->nodeCount; i++) { AdjNode* p = graph->head[i]; while (p != NULL) { AdjNode* tmp = p; p = p->next; free(tmp); } } } int main() { AdjacencyList graph; int nodeCount = 5; initList(&graph, nodeCount); // 添加无向边 addUndirectedEdgeList(&graph, 0, 1); addUndirectedEdgeList(&graph, 0, 2); addUndirectedEdgeList(&graph, 1, 3); addUndirectedEdgeList(&graph, 2, 4); // 打印邻接表 printList(&graph); // 测试深度优先搜索 int visited[MAX_NODES] = {0}; printf("深度优先搜索："); dfs(&graph, 0, visited); // 输出：0 1 3 2 4 printf("\n"); // 测试广度优先搜索 for (int i = 0; i < nodeCount; i++) { visited[i] = 0; } printf("广度优先搜索："); bfs(&graph, 0, visited); // 输出：0 1 2 3 4 printf("\n"); // 释放内存 freeList(&graph); printf("内存已释放\n"); return 0; }

七、图的实际应用场景

图在实际开发中应用非常广泛，常见场景包括：

社交网络：用户是节点，关注 / 好友关系是边，用于推荐好友、计算影响力；
地图导航：地点是节点，道路是边，用于计算最短路径（如 Dijkstra 算法）；
计算机网络：设备是节点，链路是边，用于路由选择、故障排查；
推荐系统：用户和商品是节点，点击 / 购买行为是边，用于协同过滤推荐；
编译器：函数调用关系是图，用于优化编译、检测循环依赖；
人工智能：知识图谱是图，用于表示实体之间的关系，支持推理和问答。

八、总结

图是一种多对多的非线性数据结构，由节点和边组成，支持无向 / 有向、带权 / 无权、稀疏 / 稠密等多种形态。

图的存储主要有邻接矩阵和邻接表两种方式，遍历方式有深度优先搜索（DFS）和广度优先搜索（BFS）。

在实际开发中，图的应用非常广泛，是算法和开发中不可或缺的基础数据结构。

希望这篇文章能帮助你深入理解图的原理和实现！

6.图：多对多的非线性数据结构