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(ne)适合稀疏图遍历邻居的效率高。缺点判断两个节点是否相连的时间复杂度为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.图：多对多的非线性数据结构

相关推荐

AI Agent驱动智能习惯养成：从监督到陪伴的产品架构与实现

Minecraft 存档修复完整指南：免费命令行工具，一条命令找回丢失区块

科大讯飞轮趣麦克风阵列开发板调试

更多资讯

C#上位机实战：西门子、三菱、欧姆龙PLC数据如何统一解析？

markit凭什么快13.9倍？5万页“丑陋PDF“三方基准测试全记录

Unibest：基于Vite和Vue3重构uni-app开发体验的现代化工程方案

Pandas读写Excel实战指南：openpyxl配置、多级表头处理与样式控制

Tesseract OCR中文识别实战：安装、语言包配置与Python集成

离线环境部署Docker：从docker.rpm.tar到MySQL与Redis容器实战

今日更新

Susi AI API实战指南：susi_alexa_skill如何用Node.js调用chat.json获取智能回答

换新电脑了？KeyStats 恢复码数据找回完全指南，端到端加密统计一键重建

重建二叉树：由前序与中序遍历序列还原二叉树的原理与 Java 实现（YCBlogs 剑指 Offer 精讲）

本周精选

交通拥堵预测毕设：基于Python+LSTM的车辆流量预测系统全流程解析

MATLAB/Simulink搭建10机39节点电力系统暂态稳定仿真实战

无人机航拍三维重建全流程：从SfM到网格生成的避坑指南

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？