一、什么是图图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。在实际开发中图的应用非常广泛是算法和开发中不可或缺的基础数据结构。希望这篇文章能帮助你深入理解图的原理和实现