图解邻接矩阵与邻接表存储

一、先解答上次的思考题插入 key5、15、25、7哈希表长度 10哈希函数key%105、15、25 都会落在桶5上形成链表7 落在桶7查找 15 能找到删除 5 后桶 5 还剩 15、25。二、今天学习目标理解 ** 图Graph** 的基本概念掌握两种最常用存储方式邻接矩阵邻接表完整可运行代码 结构对比三、什么是图树是一对多图是多对多。构成顶点Vertex节点边Edge两个顶点之间的连线分类无向图边没有方向 A↔B有向图边有方向 A→B带权图边有权重距离、代价等四、存储方式 1邻接矩阵用一个二维数组表示顶点之间是否相连。graph[i][j] 1i 和 j 相连graph[i][j] 0不相连优点直观、简单、查询 O (1)缺点空间浪费 O (n²)顶点多了巨耗内存代码示例#include stdio.h #define N 5 // 邻接矩阵 int graph[N][N] {0}; // 添加无向边 void addEdge(int u, int v) { graph[u][v] 1; graph[v][u] 1; } // 打印 void printMatrix() { for (int i 0; i N; i) { for (int j 0; j N; j) { printf(%d , graph[i][j]); } printf(\n); } } int main() { addEdge(0, 1); addEdge(0, 2); addEdge(1, 3); addEdge(1, 4); addEdge(3, 4); printMatrix(); return 0; }五、存储方式 2邻接表更常用、更省空间一个数组 多条链表每个顶点对应一条链表链上存它的邻居。结构0 → 1 → 2 1 → 0 → 3 → 4 2 → 0 3 → 1 → 4 4 → 1 → 3优点空间高效 O (VE)遍历邻居快缺点判断是否相连要遍历链表 O (度)邻接表完整代码#include stdio.h #include stdlib.h #define N 5 // 边节点 struct EdgeNode { int to; struct EdgeNode* next; }; // 顶点表头 struct VertexNode { struct EdgeNode* head; }; // 邻接表 struct VertexNode adj[N]; // 初始化 void initAdj() { for (int i 0; i N; i) { adj[i].head NULL; } } // 添加边 void addEdge(int u, int v) { // u → v struct EdgeNode* e (struct EdgeNode*)malloc(sizeof(struct EdgeNode)); e-to v; e-next adj[u].head; adj[u].head e; // 无向图再加一条 v→u struct EdgeNode* e2 (struct EdgeNode*)malloc(sizeof(struct EdgeNode)); e2-to u; e2-next adj[v].head; adj[v].head e2; } // 打印邻接表 void printAdj() { for (int i 0; i N; i) { printf(%d, i); struct EdgeNode* p adj[i].head; while (p) { printf( → %d, p-to); p p-next; } printf(\n); } } int main() { initAdj(); addEdge(0, 1); addEdge(0, 2); addEdge(1, 3); addEdge(1, 4); addEdge(3, 4); printAdj(); return 0; }六、邻接矩阵 vs 邻接表表格方式空间查询是否相连遍历邻居适用场景邻接矩阵O(n²)O(1)O(n)稠密图邻接表O(ne)O (度)O (度)稀疏图常用七、今日小练习构建如下无向图顶点0 1 2 3边0-10-21-22-3分别用邻接矩阵和邻接表存储并打印。