从哈希表到图：指针如何在网状结构里完成 DFS 与 BFS图是指针最自由的舞台。链表是一条线，树有固定层级，而图允许节点连接任意节点。遍历图，本质上是在网状指针中找路。引言链表是一条线。二叉树是一棵树。堆把树压进数组。哈希表把数组和链表组合起来。到了图，指针彻底挣脱固定层级。图里的节点没有绝对的父子关系。一个节点可以连接多个节点，也可以被多个节点连接。社交网络、城市道路、计算机网络、任务依赖关系，本质上都是图。如果说前几种数据结构是在“走线”和“爬树”，那么图就是进入一张网。这篇文章继续从指针视角看图：图如何存储，DFS 如何深入，BFS 如何扩散，为什么visited是图遍历中不可省略的安全绳。1. 图的存储：邻接矩阵与邻接表图最常见的两种存储方式，是邻接矩阵和邻接表。邻接矩阵用二维数组表示边：matrix[i][j] = 1 表示 i 到 j 有边它适合稠密图。优点是判断两个点是否相连很快，缺点是空间消耗大，而且要找某个点的所有邻居，必须扫描一整行。真正更能体现指针思想的是邻接表。邻接表维护一个数组adj，数组每个位置都是一条链表的头指针。链表里的每个节点代表一条边。structEdgeNode{inttarget;intweight;EdgeNode*next;};classGraph{private:vectorEdgeNode*adj;intvertexCount;};这和哈希表的拉链法非常像。哈希表中，数组桶后面挂的是冲突 key。图中，数组顶点后面挂的是邻居节点。adj[0] - 1 - 3 - 5 adj[1] - 0 - 2 adj[2] - 4adj[i]表示从顶点i出发的所有边。每个EdgeNode通过next串起来。所以，邻接表本质上就是N 条边链表的集合。2. DFS：指针的纵向深入与递归回溯DFS，深度优先搜索。它的策略很简单：沿着一条路尽量往深处走，走不通再退回来。递归版本最直观：voiddfs(intcur,vectorboolvisited){visited[cur]=true;coutcur" ";EdgeNode*edge=adj[cur];while(edge!=NULL){intneighbor=edge
从哈希表到图：指针如何在网状结构里完成 DFS 与 BFS
发布时间：2026/6/25 12:27:57
从哈希表到图：指针如何在网状结构里完成 DFS 与 BFS图是指针最自由的舞台。链表是一条线，树有固定层级，而图允许节点连接任意节点。遍历图，本质上是在网状指针中找路。引言链表是一条线。二叉树是一棵树。堆把树压进数组。哈希表把数组和链表组合起来。到了图，指针彻底挣脱固定层级。图里的节点没有绝对的父子关系。一个节点可以连接多个节点，也可以被多个节点连接。社交网络、城市道路、计算机网络、任务依赖关系，本质上都是图。如果说前几种数据结构是在“走线”和“爬树”，那么图就是进入一张网。这篇文章继续从指针视角看图：图如何存储，DFS 如何深入，BFS 如何扩散，为什么visited是图遍历中不可省略的安全绳。1. 图的存储：邻接矩阵与邻接表图最常见的两种存储方式，是邻接矩阵和邻接表。邻接矩阵用二维数组表示边：matrix[i][j] = 1 表示 i 到 j 有边它适合稠密图。优点是判断两个点是否相连很快，缺点是空间消耗大，而且要找某个点的所有邻居，必须扫描一整行。真正更能体现指针思想的是邻接表。邻接表维护一个数组adj，数组每个位置都是一条链表的头指针。链表里的每个节点代表一条边。structEdgeNode{inttarget;intweight;EdgeNode*next;};classGraph{private:vectorEdgeNode*adj;intvertexCount;};这和哈希表的拉链法非常像。哈希表中，数组桶后面挂的是冲突 key。图中，数组顶点后面挂的是邻居节点。adj[0] - 1 - 3 - 5 adj[1] - 0 - 2 adj[2] - 4adj[i]表示从顶点i出发的所有边。每个EdgeNode通过next串起来。所以，邻接表本质上就是N 条边链表的集合。2. DFS：指针的纵向深入与递归回溯DFS，深度优先搜索。它的策略很简单：沿着一条路尽量往深处走，走不通再退回来。递归版本最直观：voiddfs(intcur,vectorboolvisited){visited[cur]=true;coutcur" ";EdgeNode*edge=adj[cur];while(edge!=NULL){intneighbor=edge
