1. 图的存储方式邻接矩阵与邻接表基础图这种数据结构在计算机科学中应用广泛从社交网络到地图导航再到编译器优化到处都有它的身影。但要让计算机处理图数据首先得解决一个基本问题如何把图存储到内存中这就引出了今天要讨论的两种经典存储方式——邻接矩阵和邻接表。想象一下你正在规划城市间的航线图。如果用邻接矩阵就好比制作了一个巨大的城市间直达航班表行和列都代表城市表格中的数字表示两个城市间是否有航班以及票价多少。而邻接表则更像是为每个城市准备了一个小本子只记录从这个城市出发能直达哪些邻居城市。邻接矩阵本质上是个二维数组。对于有n个顶点的图我们就创建一个n×n的矩阵。矩阵中的每个元素表示对应顶点间的连接情况可以是简单的0/1表示有无连接也可以是具体的权值。这种存储方式最大的特点就是直观——想知道顶点i和j是否相连直接查矩阵的第i行第j列即可。邻接表则采用了完全不同的思路。它为每个顶点维护一个链表链表中只存储与该顶点直接相连的邻居。这种存储方式更节俭特别适合那些边数远少于顶点数平方的稀疏图。在实际应用中Facebook的好友关系、Twitter的关注网络这些超大规模社交图几乎都采用邻接表或其变种来存储。2. 邻接矩阵的代码实现详解2.1 数据结构设计让我们先用C语言定义邻接矩阵的数据结构。这个结构体需要包含几个关键部分#define INF 32767 // 用一个大数表示无穷即两顶点间没有边 #define MAXV 100 // 最大顶点数 typedef char InfoType; // 顶点附加信息的类型 // 顶点类型 typedef struct { int no; // 顶点编号 InfoType info; // 顶点其他信息 } VertexType; // 邻接矩阵表示的图 typedef struct { int edges[MAXV][MAXV]; // 邻接矩阵数组 int n, e; // 顶点数和边数 VertexType vexs[MAXV]; // 顶点信息数组 } MatGraph;这里有几个设计要点值得注意edges二维数组是核心存储所有边的信息n和e分别记录顶点和边的数量vexs数组可以存储顶点的附加信息。INF这个常量特别重要它表示无穷大在图中用来表示两个顶点间没有直接连接。2.2 创建邻接矩阵有了数据结构接下来实现创建邻接矩阵的函数void CreateMat(MatGraph g, int A[MAXV][MAXV], int n, int e) { g.n n; g.e e; // 初始化邻接矩阵 for(int i0; ig.n; i) { for(int j0; jg.n; j) { g.edges[i][j] INF; // 初始时所有边都不存在 } } // 填充邻接矩阵 for(int i0; ig.n; i) { for(int j0; jg.n; j) { if(A[i][j] ! 0 A[i][j] ! INF) { g.edges[i][j] A[i][j]; } } } }这个函数接收一个空的MatGraph结构体和一个二维数组AA中存储了图的初始连接信息。函数首先初始化整个矩阵为INF无边然后根据A中的值填充有效边。注意这里对A[i][j]做了双重判断既不为0也不为INF时才认为是有效边这在实际项目中很常见可以处理各种边界情况。2.3 输出与销毁邻接矩阵输出邻接矩阵相对简单就是遍历二维数组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); } }有趣的是邻接矩阵的销毁操作——在C语言中由于我们用的是静态数组实际上不需要特别的销毁操作这是邻接矩阵的一个便利之处。当MatGraph结构体离开作用域时系统会自动回收其内存。这也是邻接矩阵在某些场景下更受欢迎的原因之一内存管理简单。3. 邻接表的代码实现详解3.1 数据结构设计邻接表的数据结构比邻接矩阵复杂一些因为它结合了数组和链表// 边表结点 typedef struct ANode { int adjvex; // 邻接点编号 struct ANode *nextarc; // 指向下一条边的指针 int weight; // 边的权值 } ArcNode; // 顶点表结点 typedef struct VNode { InfoType info; // 顶点信息 ArcNode *firstarc; // 指向第一条邻接边的指针 } VNode; // 邻接表表示的图 typedef struct { VNode adjlist[MAXV]; // 顶点数组 int n, e; // 顶点数和边数 } AdjGraph;这里的设计很巧妙AdjGraph包含一个顶点数组adjlist每个顶点又通过firstarc指向一个边链表。边链表中的每个节点ArcNode存储了邻接点编号、边权值以及下一条边的指针。这种结构特别适合表示稀疏图因为它只为实际存在的边分配内存。3.2 创建邻接表创建邻接表的函数比邻接矩阵复杂因为涉及动态内存分配void CreateAdj(AdjGraph *G, int A[MAXV][MAXV], int n, int e) { G (AdjGraph*)malloc(sizeof(AdjGraph)); if(!G) { printf(内存分配失败\n); exit(1); } 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; } } } }这里有几个关键点首先整个邻接表结构是动态分配的其次我们使用头插法构建边表这样后插入的边会出现在链表前面最后记得检查malloc的返回值这是良好编程习惯的体现。3.3 输出与销毁邻接表输出邻接表的函数需要遍历每个顶点的边链表void DispAdj(AdjGraph *G) { ArcNode *p; for(int i0; iG-n; i) { printf(%3d: , i); p G-adjlist[i].firstarc; while(p ! NULL) { printf(%3d[%d]-, p-adjvex, p-weight); p p-nextarc; } printf(∧\n); } }邻接表的销毁操作要格外小心因为涉及多层动态内存释放void DestroyAdj(AdjGraph *G) { ArcNode *pre, *p; for(int i0; iG-n; i) { pre G-adjlist[i].firstarc; while(pre ! NULL) { p pre-nextarc; free(pre); pre p; } } free(G); G NULL; // 避免悬空指针 }这个销毁函数先释放所有边表节点再释放邻接表结构本身最后将指针置为NULL。这种谨慎的内存管理在C语言中至关重要否则很容易导致内存泄漏。4. 两种存储方式的性能对比4.1 空间复杂度分析邻接矩阵的空间复杂度是O(n²)因为它要存储所有可能的边包括不存在的边。对于有1000个顶点的图邻接矩阵需要100万单位的存储空间即使实际只有5000条边。邻接表的空间复杂度是O(ne)n是顶点数e是边数。同样的1000顶点5000边的图邻接表只需要大约6000单位的存储空间1000个顶点头结点5000条边。显然对于稀疏图邻接表在空间上优势明显。4.2 时间复杂度对比不同操作的效率对比操作邻接矩阵邻接表判断u到v是否有边O(1)O(d)获取顶点v的所有邻居O(n)O(d)添加一条边O(1)O(1)*删除一条边O(1)O(d)*注邻接表添加边的时间复杂度取决于插入位置头插法为O(1)邻接矩阵在判断边存在性和修改边操作上占优因为可以直接通过索引访问。邻接表在获取顶点所有邻居时更高效特别是对于度数d远小于n的顶点。4.3 适用场景建议根据我的项目经验选择存储方式要考虑以下因素图的密度稠密图边数接近n²适合邻接矩阵稀疏图适合邻接表常见操作如果需要频繁检查边是否存在邻接矩阵更好如果需要频繁遍历邻居邻接表更优内存限制内存紧张时优先考虑邻接表算法需求某些算法如Floyd-Warshall需要邻接矩阵而BFS/DFS通常在邻接表上效率更高在实际开发中我曾经用邻接表处理过百万级节点的社交网络图如果用邻接矩阵光是内存消耗就是灾难性的。但后来处理一个小型交通图约50个交叉路口时邻接矩阵反而更简单高效因为路口之间连接相对密集。