目录一、主要任务二、主要内容1. 图的基本概念2. 图的表示方法2.1 邻接矩阵2.2 邻接表3. Java实现图的表示4. 图的遍历4.1 深度优先搜索DFS4.2 广度优先搜索BFS4.3 Java实现5. 可视化遍历顺序5.1 测试用例6. 有权图的应用简介7. 完整代码汇总8. 总结一、主要任务1. 理解图的邻接矩阵、邻接表表示。2. 实现图的BFS、DFS遍历。3. 了解有权图的应用。4.实现无向图和有向图编写BFS/DFS遍历代码可视化遍历顺序。二、主要内容图Graph是一种非常重要的数据结构它广泛应用于社交网络、地图导航、任务调度等现实场景。对于许多初学者来说图的概念和算法可能显得有些抽象。本文将用最通俗的语言从零开始带你理解图的两种表示方法邻接矩阵和邻接表并亲手用Java实现图的深度优先搜索DFS和广度优先搜索BFS最后通过打印遍历顺序让你直观看到搜索过程。1. 图的基本概念在计算机科学中图由顶点Vertex和边Edge组成。可以想象成一群点顶点以及连接它们的线边。无向图边没有方向就像两个人互相认识关系是对称的。例如社交网络中的好友关系。有向图边有方向就像微博的关注关系A关注B但B不一定关注A。有权图边带有权重可以表示距离、时间、成本等。例如地图上两个城市之间的路程距离。图的数学表示G (V, E)其中V是顶点集合E是边的集合。2. 图的表示方法要在程序中存储图我们有两种常用的方式邻接矩阵和邻接表。2.1 邻接矩阵使用一个二维数组adjMatrix来表示图。假设有n个顶点那么矩阵的大小为n × n。如果顶点i到顶点j有边则adjMatrix[i][j] 1无权图或权重值有权图否则为0或无穷大。优点判断任意两个顶点之间是否有边非常快O(1)时间。缺点占用空间大对于稀疏图边很少会浪费大量空间。2.2 邻接表为每个顶点维护一个列表如ArrayList存储与该顶点相邻的所有顶点。对于有向图只存储出边对于无向图存储所有邻接点。优点节省空间尤其适合稀疏图。缺点判断两个顶点是否有边需要遍历列表不如邻接矩阵快。在实际开发中邻接表更常用。我们下面就用邻接表来实现图。3. Java实现图的表示我们将创建一个Graph类支持添加顶点可选通常我们初始化时就确定顶点数添加边无向/有向打印图的结构为了简化我们假设顶点用整数编号0到n-1并且图是无权图。我们会在类中增加一个布尔字段directed来区分有向和无向。import java.util.ArrayList; import java.util.LinkedList; import java.util.List; import java.util.Queue; public class Graph { private int numVertices; // 顶点数 private ListListInteger adjList; // 邻接表 private boolean directed; // 是否为有向图 // 构造方法 public Graph(int numVertices, boolean directed) { this.numVertices numVertices; this.directed directed; adjList new ArrayList(numVertices); for (int i 0; i numVertices; i) { adjList.add(new LinkedList()); } } // 添加边 public void addEdge(int src, int dest) { adjList.get(src).add(dest); if (!directed) { // 无向图需要添加反向边 adjList.get(dest).add(src); } } // 打印邻接表 public void printGraph() { for (int i 0; i numVertices; i) { System.out.print(顶点 i 的邻接表: ); for (Integer neighbor : adjList.get(i)) { System.out.print(neighbor ); } System.out.println(); } } // 获取邻接表供遍历使用 public ListListInteger getAdjList() { return adjList; } public int getNumVertices() { return numVertices; } }4. 图的遍历图的遍历是指从某个顶点出发沿着边访问图中所有顶点且每个顶点只访问一次。常用的遍历算法有深度优先搜索DFS和广度优先搜索BFS。4.1 深度优先搜索DFSDFS 类似于树的先序遍历采用栈递归或显式栈实现。它从起始顶点开始沿着一条路径一直走到底然后回溯再走另一条路径直到所有顶点都被访问。算法步骤递归标记当前顶点为已访问。输出当前顶点或记录访问顺序。遍历当前顶点的所有邻接点如果邻接点未被访问则递归访问它。4.2 广度优先搜索BFSBFS 类似于树的层序遍历使用队列实现。它从起始顶点开始先访问所有距离为1的顶点再访问距离为2的顶点依此类推。算法步骤将起始顶点加入队列并标记为已访问。当队列不为空时取出队首顶点输出它。遍历该顶点的所有邻接点如果邻接点未被访问则将其加入队列并标记为已访问。4.3 Java实现我们在Graph类中添加两个遍历方法并记录遍历顺序用列表保存。// 深度优先遍历从顶点 start 开始 public ListInteger dfs(int start) { ListInteger result new ArrayList(); boolean[] visited new boolean[numVertices]; dfsHelper(start, visited, result); return result; } private void dfsHelper(int vertex, boolean[] visited, ListInteger result) { visited[vertex] true; result.add(vertex); for (int neighbor : adjList.get(vertex)) { if (!visited[neighbor]) { dfsHelper(neighbor, visited, result); } } } // 广度优先遍历从顶点 start 开始 public ListInteger bfs(int start) { ListInteger result new ArrayList(); boolean[] visited new boolean[numVertices]; QueueInteger queue new LinkedList(); visited[start] true; queue.offer(start); while (!queue.isEmpty()) { int vertex queue.poll(); result.add(vertex); for (int neighbor : adjList.get(vertex)) { if (!visited[neighbor]) { visited[neighbor] true; queue.offer(neighbor); } } } return result; }注意如果图不是连通图从某个起点出发可能无法访问所有顶点。上面的实现只访问从起点可达的顶点。要遍历整个图需要在外层循环中检查每个顶点是否被访问并对未访问的顶点再次调用遍历对于非连通图。5. 可视化遍历顺序所谓“可视化”在这里我们通过打印遍历顺序来展示搜索过程。我们可以在测试代码中构建一个图然后分别调用DFS和BFS输出遍历序列。5.1 测试用例我们创建一个包含6个顶点的无向图结构如下0 -- 1 -- 2| | |3 -- 4 -- 5假设所有边都是双向的。代码实现public class GraphTraversalDemo { public static void main(String[] args) { // 创建一个无向图有6个顶点 Graph graph new Graph(6, false); graph.addEdge(0, 1); graph.addEdge(0, 3); graph.addEdge(1, 2); graph.addEdge(1, 4); graph.addEdge(2, 5); graph.addEdge(3, 4); graph.addEdge(4, 5); System.out.println(图的邻接表表示); graph.printGraph(); System.out.println(\n从顶点0开始的DFS遍历顺序); ListInteger dfsOrder graph.dfs(0); System.out.println(dfsOrder); System.out.println(\n从顶点0开始的BFS遍历顺序); ListInteger bfsOrder graph.bfs(0); System.out.println(bfsOrder); } }运行结果示例图的邻接表表示 顶点 0 的邻接表: 1 3 顶点 1 的邻接表: 0 2 4 顶点 2 的邻接表: 1 5 顶点 3 的邻接表: 0 4 顶点 4 的邻接表: 1 3 5 顶点 5 的邻接表: 2 4 从顶点0开始的DFS遍历顺序 [0, 1, 2, 5, 4, 3] 从顶点0开始的BFS遍历顺序 [0, 1, 3, 2, 4, 5]可以看到DFS顺着一条路走到黑0→1→2→5→4→3而BFS一层层扩展0→1,3→2,4→5。通过输出列表我们可以直观地感受两种算法的差异。6. 有权图的应用简介上述实现针对的是无权图。但在实际应用中我们经常遇到有权图例如最短路径问题如 Dijkstra 算法用于计算一个顶点到其他顶点的最短路径。最小生成树如 Prim 算法、Kruskal 算法用于在连通图中找到一棵包含所有顶点且边权和最小的树。网络流如最大流问题。在处理有权图时邻接表中存储的不仅仅是邻居顶点还需要存储边的权重。通常我们会定义一个内部类Edge包含目标顶点和权重。遍历算法也需要相应调整如 Dijkstra 使用优先队列。由于篇幅限制本文不展开有权图的算法但希望读者了解图的表示和遍历是学习这些高级算法的基础。7. 完整代码汇总为了方便复制我们将所有代码整合在一起省略重复注释。import java.util.*; class Graph { private int numVertices; private ListListInteger adjList; private boolean directed; public Graph(int numVertices, boolean directed) { this.numVertices numVertices; this.directed directed; adjList new ArrayList(numVertices); for (int i 0; i numVertices; i) { adjList.add(new LinkedList()); } } public void addEdge(int src, int dest) { adjList.get(src).add(dest); if (!directed) { adjList.get(dest).add(src); } } public void printGraph() { for (int i 0; i numVertices; i) { System.out.print(顶点 i 的邻接表: ); for (Integer neighbor : adjList.get(i)) { System.out.print(neighbor ); } System.out.println(); } } public ListInteger dfs(int start) { ListInteger result new ArrayList(); boolean[] visited new boolean[numVertices]; dfsHelper(start, visited, result); return result; } private void dfsHelper(int vertex, boolean[] visited, ListInteger result) { visited[vertex] true; result.add(vertex); for (int neighbor : adjList.get(vertex)) { if (!visited[neighbor]) { dfsHelper(neighbor, visited, result); } } } public ListInteger bfs(int start) { ListInteger result new ArrayList(); boolean[] visited new boolean[numVertices]; QueueInteger queue new LinkedList(); visited[start] true; queue.offer(start); while (!queue.isEmpty()) { int vertex queue.poll(); result.add(vertex); for (int neighbor : adjList.get(vertex)) { if (!visited[neighbor]) { visited[neighbor] true; queue.offer(neighbor); } } } return result; } } public class GraphTraversalDemo { public static void main(String[] args) { // 创建无向图 Graph graph new Graph(6, false); graph.addEdge(0, 1); graph.addEdge(0, 3); graph.addEdge(1, 2); graph.addEdge(1, 4); graph.addEdge(2, 5); graph.addEdge(3, 4); graph.addEdge(4, 5); System.out.println(图的邻接表表示); graph.printGraph(); System.out.println(\n从顶点0开始的DFS遍历顺序); System.out.println(graph.dfs(0)); System.out.println(\n从顶点0开始的BFS遍历顺序); System.out.println(graph.bfs(0)); // 有向图示例 System.out.println(\n 有向图示例 ); Graph digraph new Graph(4, true); digraph.addEdge(0, 1); digraph.addEdge(0, 2); digraph.addEdge(1, 2); digraph.addEdge(2, 3); digraph.addEdge(3, 1); System.out.println(有向图的邻接表); digraph.printGraph(); System.out.println(从顶点0开始的DFS); System.out.println(digraph.dfs(0)); System.out.println(从顶点0开始的BFS); System.out.println(digraph.bfs(0)); } }运行上述代码你可以看到无向图和有向图的遍历结果。尝试修改图的结构观察遍历顺序的变化。8. 总结图的基本概念顶点、边、有向图、无向图、有权图。图的两种表示方法邻接矩阵和邻接表并实现了邻接表。图的两种遍历算法深度优先搜索DFS和广度优先搜索BFS并用Java实现了它们。通过打印遍历顺序直观地感受了DFS和BFS的区别。简单了解了有权图的应用场景。