图是数据结构中最后一类重要的非线性结构。前面的链表是一对一，树是一对多，图是多对多。图的遍历（DFS/BFS）和最小生成树是 408 考研的重点。
一、图的基本概念
1. 定义
图由**顶点（Vertex）和边（Edge）**组成。
无向图： A —— B | | C —— D 有向图（带箭头）： A → B ↓ ↓ C ← D术语：
- 顶点：图中的节点
- 边：顶点之间的连线
- 无向图：边没有方向，(A, B) = (B, A)
- 有向图：边有方向，<A, B> ≠ <B, A>
- 完全图：任意两个顶点之间都有边
- 权：边上的数值（如距离、花费）
- 连通图：任意两个顶点之间都有路径可达
二、图的存储结构
1. 邻接矩阵
// 用一个二维数组存储顶点之间的邻接关系// graph[i][j] = 1 表示顶点 i 到 j 有边// graph[i][j] = 0 表示没有边publicclassGraphMatrix{privateint[][]matrix;// 邻接矩阵privateintn;// 顶点数privatebooleandirected;// 是否有向publicGraphMatrix(intn,booleandirected){this.n=n;this.directed=directed;matrix=newint[n][n];}// 添加边publicvoidaddEdge(inti,intj,intweight){matrix[i][j]=weight;// i → jif(!directed){matrix[j][i]=weight;// 无向图对称}}// 判断是否有边publicbooleanhasEdge(inti,intj){returnmatrix[i][j]!=0;}}无向图的邻接矩阵（对称）： A B C D A [0, 1, 1, 0] B [1, 0, 0, 1] C [1, 0, 0, 1] D [0, 1, 1, 0]优点：判断两点是否有边 O(1)，实现简单
缺点：占用空间 O(n²)，稀疏图浪费空间
2. 邻接表
// 每个顶点维护一个链表，存储与其相连的顶点publicclassGraphList{privateList<Integer>[]adj;// 邻接表数组privateintn;publicGraphList(intn){this.n=n;adj=newList[n];for(inti=0;i<n;i++){adj[i]=newArrayList<>();}}publicvoidaddEdge(inti,intj){adj[i].add(j);adj[j].add(i);// 无向图}publicList<Integer>getNeighbors(intv){returnadj[v];}}无向图的邻接表： A → [B, C] B → [A, D] C → [A, D] D → [B, C]优点：节省空间 O(n + e)，适合稀疏图
缺点：判断两点是否有边需要遍历链表 O(degree)
3. 邻接矩阵 vs 邻接表
| 对比 | 邻接矩阵 | 邻接表 |
|---|---|---|
| 空间 | O(n²) | O(n + e) |
| 判边 | O(1) 🏆 | O(度) |
| 遍历邻居 | O(n) | O(度) 🏆 |
| 适合 | 稠密图 | 稀疏图（常用）🏆 |
三、图的遍历
1. 深度优先搜索（DFS）
沿着一条路走到黑，走不通了再回头。
publicclassGraphDFS{privateList<Integer>[]adj;privateboolean[]visited;publicvoiddfs(intstart){visited=newboolean[adj.length];dfsRecursive(start);}privatevoiddfsRecursive(intv){visited[v]=true;System.out.print(v+" ");// 访问当前顶点for(intneighbor:adj[v]){if(!visited[neighbor]){dfsRecursive(neighbor);// 递归访问未访问的邻居}}}}从 A 开始 DFS（假设邻接顺序从小到大）： A → B → D → C 路径：A → B → D → C 访问顺序：A, B, D, C时间复杂度：O(n + e)
空间复杂度：O(n)（递归栈）
2. 广度优先搜索（BFS）
一层一层往外扩，像水的波纹。
publicclassGraphBFS{privateList<Integer>[]adj;privateboolean[]visited;publicvoidbfs(intstart){visited=newboolean[adj.length];Queue<Integer>queue=newLinkedList<>();visited[start]=true;queue.offer(start);while(!queue.isEmpty()){intv=queue.poll();System.out.print(v+" ");// 访问当前顶点for(intneighbor:adj[v]){if(!visited[neighbor]){visited[neighbor]=true;queue.offer(neighbor);// 未访问的邻居入队}}}}}从 A 开始 BFS： 第一层：A 第二层：B, C 第三层：D 访问顺序：A, B, C, D时间复杂度：O(n + e)
空间复杂度：O(n)（队列）
3. DFS vs BFS
| 对比 | DFS | BFS |
|---|---|---|
| 数据结构 | 栈（递归） | 队列 |
| 遍历顺序 | 沿着路径深入 | 逐层扩展 |
| 适用场景 | 连通性判断、拓扑排序 | 最短路径、层序遍历 |
| 实现难度 | 递归，代码简洁 | 循环，稍复杂 |
四、最小生成树
用最小的总权值把所有顶点连通。
1. Prim 算法
从一个顶点开始，每次找权值最小的边加入。
publicclassPrim{/** * Prim 算法求最小生成树 * @param graph 邻接矩阵（权值，0表示无边） * @return 最小总权值 */publicstaticintprim(int[][]graph){intn=graph.length;int[]lowCost=newint[n];// 到各顶点的最小权值boolean[]visited=newboolean[n];inttotal=0;// 从顶点0开始visited[0]=true;for(inti=0;i<n;i++){lowCost[i]=graph[0][i]==0?Integer.MAX_VALUE:graph[0][i];}for(inti=1;i<n;i++){// 找权值最小的未访问顶点intmin=Integer.MAX_VALUE;intminIdx=-1;for(intj=0;j<n;j++){if(!visited[j]&&lowCost[j]<min){min=lowCost[j];minIdx=j;}}if(minIdx==-1)break;// 不连通visited[minIdx]=true;total+=min;// 更新 lowCostfor(intj=0;j<n;j++){if(!visited[j]&&graph[minIdx][j]!=0&&graph[minIdx][j]<lowCost[j]){lowCost[j]=graph[minIdx][j];}}}returntotal;}}2. Kruskal 算法
每次选权值最小的边，只要不形成环就加入。
publicclassKruskal{// 边的定义staticclassEdgeimplementsComparable<Edge>{intu,v,weight;publicintcompareTo(Edgeo){returnthis.weight-o.weight;}}// 并查集staticclassUnionFind{int[]parent;UnionFind(intn){parent=newint[n];for(inti=0;i<n;i++)parent[i]=i;}intfind(intx){returnparent[x]==x?x:(parent[x]=find(parent[x]));}booleanunion(intx,inty){intrx=find(x),ry=find(y);if(rx==ry)returnfalse;parent[rx]=ry;returntrue;}}publicstaticintkruskal(Edge[]edges,intn){Arrays.sort(edges);// 按权值排序UnionFinduf=newUnionFind(n);inttotal=0,count=0;for(Edgee:edges){if(uf.union(e.u,e.v)){// 不会形成环total+=e.weight;count++;if(count==n-1)break;// n个顶点需要n-1条边}}returntotal;}}3. Prim vs Kruskal
| 对比 | Prim | Kruskal |
|---|---|---|
| 策略 | 选顶点 | 选边 |
| 数据结构 | 邻接矩阵 | 边集 + 并查集 |
| 时间复杂度 | O(n²) | O(e log e) |
| 适合 | 稠密图🏆 | 稀疏图🏆 |
五、408 考研经典考题
题1：邻接矩阵转邻接表
List<Integer>[]matrixToList(int[][]matrix){intn=matrix.length;List<Integer>[]adj=newList[n];for(inti=0;i<n;i++){adj[i]=newArrayList<>();for(intj=0;j<n;j++){if(matrix[i][j]==1){adj[i].add(j);}}}returnadj;}题2：判断图是否连通
booleanisConnected(List<Integer>[]adj){intn=adj.length;boolean[]visited=newboolean[n];dfs(adj,visited,0);for(booleanv:visited){if(!v)returnfalse;}returntrue;}题3：拓扑排序
有向无环图（DAG）的顶点线性排序，AOV 网中活动执行的先后顺序。
// 核心思想：不断删除入度为 0 的顶点List<Integer>topologicalSort(List<Integer>[]adj){intn=adj.length;int[]inDegree=newint[n];for(inti=0;i<n;i++){for(intv:adj[i])inDegree[v]++;}Queue<Integer>queue=newLinkedList<>();for(inti=0;i<n;i++){if(inDegree[i]==0)queue.offer(i);}List<Integer>result=newArrayList<>();while(!queue.isEmpty()){intv=queue.poll();result.add(v);for(intneighbor:adj[v]){if(--inDegree[neighbor]==0){queue.offer(neighbor);}}}returnresult;}六、图的常见考点
1. 有 n 个顶点的无向完全图有 n(n-1)/2 条边 2. 有 n 个顶点的有向完全图有 n(n-1) 条边 3. 连通图至少需要 n-1 条边（树） 4. 图的邻接矩阵是对称矩阵（无向图） DFS/BFS 时间复杂度的写法： 邻接矩阵：O(n²) 邻接表：O(n + e)💡 觉得有用的话，点赞 + 关注【张老师技术栈】吧！每周更新 Java/Python/爬虫 实战干货，不让你白来。
