1. 图的存储结构邻接矩阵与邻接表第一次接触图这种数据结构时很多人都会被它的存储方式搞晕。我自己当年学数据结构的时候就经常分不清什么时候用邻接矩阵什么时候用邻接表。后来在实际项目中踩过几次坑才真正明白它们的区别。今天我就用最通俗的方式带大家彻底搞懂这两种存储结构。邻接矩阵就像是一个二维表格行和列都代表图中的顶点。如果两个顶点之间有边相连就在对应的格子里填上边的权重如果是带权图或者1如果是无权图。举个例子假设我们有4个城市A、B、C、D之间的航线图用邻接矩阵表示就像下面这样A B C D A [0, 1, 0, 1] B [1, 0, 1, 0] C [0, 1, 0, 1] D [1, 0, 1, 0]而邻接表更像是把每个顶点的邻居都列在一个链表里。还是刚才的航线图用邻接表表示就是A - B - D B - A - C C - B - D D - A - C在实际项目中我发现邻接矩阵特别适合稠密图边很多的情况因为查询两个顶点是否相邻只需要O(1)时间。但是当图比较稀疏时邻接矩阵会浪费大量空间存储0。这时候邻接表就更合适它只存储实际存在的边空间利用率高。2. 邻接矩阵的代码实现与实战让我们用C语言来实现一个邻接矩阵。我建议先定义一个结构体来存储图的基本信息#define MAXV 100 // 最大顶点数 #define INF 32767 // 无穷大表示 typedef struct { int edges[MAXV][MAXV]; // 邻接矩阵 int n, e; // 顶点数和边数 } MatGraph;创建邻接矩阵的函数可以这样写void CreateMat(MatGraph *g, int A[MAXV][MAXV], int n, int e) { g-n n; g-e e; for(int i0; in; i) { for(int j0; jn; j) { g-edges[i][j] A[i][j]; } } }这里有个坑我踩过初始化时一定要记得设置g-n和g-e的值否则后续操作可能会越界访问。输出邻接矩阵时我们可以用以下函数void DispMat(MatGraph g) { for(int i0; ig.n; i) { for(int j0; jg.n; j) { if(g.edges[i][j] ! INF) printf(%4d, g.edges[i][j]); else printf(%4s, ∞); } printf(\n); } }在实际项目中邻接矩阵的一个典型应用场景是社交网络的好友关系图。比如要快速判断两个人是否是好友关系用邻接矩阵只需要一次数组访问就能得到结果效率非常高。3. 邻接表的代码实现与优化邻接表的实现稍微复杂一些因为它涉及到链表操作。我们先定义几个关键结构体typedef struct ANode { int adjvex; // 邻接点编号 struct ANode *nextarc; // 下一条边 int weight; // 边权值 } ArcNode; typedef struct VNode { ArcNode *firstarc; // 第一条边 } AdjList[MAXV]; typedef struct { AdjList adjlist; // 邻接表 int n, e; // 顶点数和边数 } AdjGraph;创建邻接表的函数如下void CreateAdj(AdjGraph **G, int A[MAXV][MAXV], int n, int e) { *G (AdjGraph*)malloc(sizeof(AdjGraph)); (*G)-n n; (*G)-e e; for(int i0; in; i) (*G)-adjlist[i].firstarc NULL; for(int i0; in; i) { for(int jn-1; j0; j--) { // 倒序插入保持邻接点顺序 if(A[i][j] !0 A[i][j] ! INF) { ArcNode *p (ArcNode*)malloc(sizeof(ArcNode)); p-adjvex j; p-weight A[i][j]; p-nextarc (*G)-adjlist[i].firstarc; (*G)-adjlist[i].firstarc p; } } } }这里有个重要技巧我们采用头插法来构建邻接表这样插入操作的时间复杂度是O(1)。输出邻接表时void DispAdj(AdjGraph *G) { for(int i0; iG-n; i) { printf(%3d: , i); ArcNode *p G-adjlist[i].firstarc; while(p ! NULL) { printf(%3d[%d]-, p-adjvex, p-weight); p p-nextarc; } printf(∧\n); } }在实际项目中邻接表特别适合表示网页链接图或者交通路线图。比如导航系统中一个路口连接多个道路的情况用邻接表表示就非常自然。4. 图的遍历算法实战图的遍历是图算法的基础主要有深度优先搜索(DFS)和广度优先搜索(BFS)两种方式。我在实际项目中发现选择哪种遍历方式会直接影响算法效率。4.1 递归DFS实现递归实现的DFS代码非常简洁int visited[MAXV]; // 访问标记数组 void DFS(AdjGraph *G, int v) { printf(%3d, v); visited[v] 1; ArcNode *p G-adjlist[v].firstarc; while(p ! NULL) { if(!visited[p-adjvex]) DFS(G, p-adjvex); p p-nextarc; } }递归DFS虽然简单但在处理大规模图时可能会栈溢出。我曾经在一个社交网络分析项目中就遇到过这个问题后来改用非递归版本才解决。4.2 非递归DFS实现非递归DFS需要借助栈来实现void DFS1(AdjGraph *G, int v) { int St[MAXV], top -1; for(int i0; iG-n; i) visited[i] 0; printf(%3d, v); visited[v] 1; St[top] v; while(top 0) { int x St[top]; ArcNode *p G-adjlist[x].firstarc; while(p ! NULL) { if(!visited[p-adjvex]) { printf(%3d, p-adjvex); visited[p-adjvex] 1; St[top] p-adjvex; break; } p p-nextarc; } if(p NULL) top--; } }4.3 BFS实现BFS需要用到队列它特别适合寻找最短路径void BFS(AdjGraph *G, int v) { int queue[MAXV], front0, rear0; for(int i0; iG-n; i) visited[i] 0; printf(%3d, v); visited[v] 1; rear (rear1)%MAXV; queue[rear] v; while(front ! rear) { front (front1)%MAXV; int w queue[front]; ArcNode *p G-adjlist[w].firstarc; while(p ! NULL) { if(!visited[p-adjvex]) { printf(%3d, p-adjvex); visited[p-adjvex] 1; rear (rear1)%MAXV; queue[rear] p-adjvex; } p p-nextarc; } } printf(\n); }在实际的路径规划项目中我发现BFS特别适合解决无权图的最短路径问题。比如在一个迷宫游戏中用BFS一定能找到出口的最短路径。5. 存储结构与遍历算法的性能对比不同的存储结构会极大影响遍历算法的效率。通过大量测试我总结了以下经验空间复杂度邻接矩阵O(n²)适合稠密图邻接表O(ne)适合稀疏图时间复杂度DFS/BFS在邻接矩阵中O(n²)DFS/BFS在邻接表中O(ne)查询效率邻接矩阵判断边是否存在O(1)邻接表判断边是否存在O(degree(v))在实际项目中我通常会根据图的特点来选择存储结构。比如在社交网络分析中因为社交图通常很稀疏用邻接表更节省内存。而在一些稠密的交通网络图中邻接矩阵的查询优势就更明显。6. 实际项目中的经验分享在开发一个推荐系统时我需要分析用户之间的关系图。最初使用邻接矩阵存储当用户量达到10万时内存直接爆了。后来改用邻接表内存使用量减少了90%以上。另一个经验是关于遍历顺序的。在电商平台的商品推荐中使用DFS可能会陷入某个品类的深度搜索导致推荐结果单一。而BFS能更均匀地探索不同品类的商品最终我们选择了BFS为基础的推荐算法。对于大规模图处理我还发现一个技巧可以结合两种存储结构的优点。比如对热数据使用邻接矩阵缓存冷数据使用邻接表存储。这种混合存储策略在实际项目中往往能取得很好的效果。