\n| \n \u904d\u5386\u7ed3\u679c<\/p>\n<\/td>\n | \n \u552f\u4e00（\u56fa\u5b9a\u5de6\u53f3\u5b50\u6811\u987a\u5e8f）<\/p>\n<\/td>\n | \n \u4e0d\u552f\u4e00（\u4f9d\u8d56\u90bb\u63a5\u9876\u70b9\u7684\u8bbf\u95ee\u987a\u5e8f）<\/p>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n \u4e8c\u3001\u6df1\u5ea6\u4f18\u5148\u641c\u7d22（DFS，Depth First Search）<\/h3>\n2.1 \u601d\u60f3<\/h4>\nDFS\u7684\u662f\u201c\u6df1\u5ea6\u4f18\u5148，\u56de\u6eaf\u63a2\u7d22\u201d，\u7c7b\u4f3c\u8d70\u8ff7\u5bab：\u4ece\u8d77\u70b9\u51fa\u53d1，\u9009\u62e9\u4e00\u4e2a\u65b9\u5411\u4e00\u76f4\u5f80\u524d\u8d70，\u76f4\u5230\u8d70\u5230\u201c\u6b7b\u80e1\u540c\u201d（\u5f53\u524d\u9876\u70b9\u65e0\u672a\u8bbf\u95ee\u7684\u90bb\u63a5\u9876\u70b9），\u518d\u56de\u6eaf\u5230\u4e0a\u4e00\u4e2a\u9876\u70b9，\u5c1d\u8bd5\u5176\u4ed6\u672a\u8d70\u7684\u65b9\u5411，\u76f4\u5230\u904d\u5386\u6240\u6709\u9876\u70b9\u3002
\n\u7b80\u5355\u603b\u7ed3：\u5148\u6df1\u540e\u5e7f，\u9047\u963b\u56de\u6eaf\u3002<\/p>\n 2.2 \u5b9e\u73b0\u4f9d\u8d56<\/h4>\nDFS\u7684\u5b9e\u73b0\u4f9d\u8d56\u6808（Stack）（\u540e\u8fdb\u5148\u51faLIFO），\u6709\u4e24\u79cd\u5b9e\u73b0\u65b9\u5f0f：<\/p>\n \u9012\u5f52\u5b9e\u73b0：\u5229\u7528JVM\u7684\u65b9\u6cd5\u8c03\u7528\u6808（\u9690\u5f0f\u6808），\u4ee3\u7801\u66f4\u7b80\u6d01，\u9002\u5408\u5c0f\u89c4\u6a21\u56fe；<\/li>\n\u975e\u9012\u5f52\u5b9e\u73b0：\u663e\u5f0f\u521b\u5efa\u6808\u5bf9\u8c61，\u624b\u52a8\u63a7\u5236\u5165\u6808\/\u51fa\u6808，\u9002\u5408\u5927\u89c4\u6a21\u56fe（\u907f\u514d\u6808\u6ea2\u51fa）\u3002
\n\u65e0\u8bba\u54ea\u79cd\u65b9\u5f0f，\u90fd\u9700\u8981\u8bbf\u95ee\u6807\u8bb0\u6570\u7ec4\/\u96c6\u5408（\u5982visited[]），\u6807\u8bb0\u9876\u70b9\u662f\u5426\u5df2\u88ab\u8bbf\u95ee\u3002<\/li>\n2.3 \u904d\u5386\u6b65\u9aa4（\u4ee5\u9876\u70b9A\u4e3a\u8d77\u70b9，\u90bb\u63a5\u9876\u70b9\u6309\u5b57\u6bcd\u5e8f\u8bbf\u95ee）<\/h4>\n\n ![\"\"](\"https:\/\/www.wsisp.com\/helps\/wp-content\/uploads\/2026\/02\/20260225140938-699f02a2196cf.png\") <\/p>\n
\u4ee5\u5305\u542b\u9876\u70b9A\u3001B\u3001C\u3001D\u3001E\u3001F\u3001G\u3001H\u3001aoyou\u7684\u8fde\u901a\u56fe\u4e3a\u4f8b，\u6b65\u9aa4\u53ef\u6982\u62ec\u4e3a\u201c\u5165\u6808\u6807\u8bb0\u2192\u6df1\u5ea6\u63a2\u7d22\u2192\u6b7b\u80e1\u540c\u51fa\u6808\u2192\u56de\u6eaf\u518d\u63a2\u7d22\u201d，\u5173\u952e\u8282\u70b9：<\/p>\n \u8d77\u70b9 A \u5165\u9012\u5f52\u8c03\u7528\u6808，\u6807\u8bb0\u5df2\u8bbf\u95ee，\u63a2\u7d22\u90bb\u63a5\u9876\u70b9（\u5b57\u6bcd\u5e8f：B\u3001D\u3001G\u3001aoyou），\u9996\u5148\u8bbf\u95ee B，B \u5165\u6808\u6807\u8bb0；<\/li>\n\u4ece B \u63a2\u7d22\u672a\u8bbf\u95ee\u90bb\u63a5\u9876\u70b9（\u5b57\u6bcd\u5e8f：E\u3001F），\u9996\u5148\u8bbf\u95ee E，E \u5165\u6808\u6807\u8bb0；<\/li>\nE \u65e0\u90bb\u63a5\u9876\u70b9（\u6216\u90bb\u63a5\u70b9\u5747\u65e0\u51fa\u8fb9），\u4e3a\u6b7b\u80e1\u540c，\u56de\u6eaf\u5230 B；<\/li>\nB \u7ee7\u7eed\u63a2\u7d22\u4e0b\u4e00\u4e2a\u672a\u8bbf\u95ee\u90bb\u63a5\u9876\u70b9 F，F \u5165\u6808\u6807\u8bb0；<\/li>\n\u4ece F \u63a2\u7d22\u672a\u8bbf\u95ee\u90bb\u63a5\u9876\u70b9 C，C \u5165\u6808\u6807\u8bb0；<\/li>\n\u4ece C \u63a2\u7d22\u672a\u8bbf\u95ee\u90bb\u63a5\u9876\u70b9 H，H \u5165\u6808\u6807\u8bb0；<\/li>\nH \u65e0\u90bb\u63a5\u9876\u70b9，\u56de\u6eaf\u5230 C；C \u65e0\u5176\u4ed6\u90bb\u63a5\u70b9，\u56de\u6eaf\u5230 F；F \u65e0\u5269\u4f59\u672a\u8bbf\u95ee\u90bb\u63a5\u70b9，\u56de\u6eaf\u5230 B；B \u90bb\u63a5\u70b9\u5df2\u5168\u90e8\u8bbf\u95ee，\u56de\u6eaf\u5230 A；<\/li>\nA \u7ee7\u7eed\u63a2\u7d22\u4e0b\u4e00\u4e2a\u672a\u8bbf\u95ee\u90bb\u63a5\u9876\u70b9 D，D \u5165\u6808\u6807\u8bb0；<\/li>\nD \u7684\u90bb\u63a5\u70b9\u4e3a E \u548c F，\u4f46 E \u548c F \u5747\u5df2\u88ab\u8bbf\u95ee，D \u65e0\u65b0\u8def\u5f84，\u56de\u6eaf\u5230 A；<\/li>\nA \u7ee7\u7eed\u63a2\u7d22\u4e0b\u4e00\u4e2a\u672a\u8bbf\u95ee\u90bb\u63a5\u9876\u70b9 G，G \u5165\u6808\u6807\u8bb0；<\/li>\nG \u65e0\u90bb\u63a5\u9876\u70b9，\u56de\u6eaf\u5230 A；<\/li>\nA \u7ee7\u7eed\u63a2\u7d22\u6700\u540e\u4e00\u4e2a\u672a\u8bbf\u95ee\u90bb\u63a5\u9876\u70b9 aoyou，aoyou \u5165\u6808\u6807\u8bb0；<\/li>\naoyou \u7684\u90bb\u63a5\u70b9\u4e3a G，\u4f46 G \u5df2\u88ab\u8bbf\u95ee，aoyou \u65e0\u65b0\u8def\u5f84，\u56de\u6eaf\u5230 A；<\/li>\nA \u6240\u6709\u90bb\u63a5\u70b9\u5747\u5df2\u8bbf\u95ee，\u9012\u5f52\u7ed3\u675f，\u904d\u5386\u5b8c\u6210\u3002<\/li>\n\u904d\u5386\u8fc7\u7a0b<\/p>\n \n ![\"\"](\"https:\/\/www.wsisp.com\/helps\/wp-content\/uploads\/2026\/02\/20260225140938-699f02a23e7cf.png\") <\/p>\n
![\"\"](\"https:\/\/www.wsisp.com\/helps\/wp-content\/uploads\/2026\/02\/20260225140938-699f02a293f27.png\") <\/p>\n
\n ![\"\"](\"https:\/\/www.wsisp.com\/helps\/wp-content\/uploads\/2026\/02\/20260225140938-699f02a2dc0c9.png\") <\/p>\n
![\"\"](\"https:\/\/www.wsisp.com\/helps\/wp-content\/uploads\/2026\/02\/20260225140939-699f02a321261.png\") <\/p>\n
\n ![\"\"](\"https:\/\/www.wsisp.com\/helps\/wp-content\/uploads\/2026\/02\/20260225140939-699f02a368d71.png\") <\/p>\n
![\"\"](\"https:\/\/www.wsisp.com\/helps\/wp-content\/uploads\/2026\/02\/20260225140939-699f02a39f235.png\") <\/p>\n
![\"\"](\"https:\/\/www.wsisp.com\/helps\/wp-content\/uploads\/2026\/02\/20260225140939-699f02a3d9a49.png\") <\/p>\n
\n ![\"\"](\"https:\/\/www.wsisp.com\/helps\/wp-content\/uploads\/2026\/02\/20260225140940-699f02a42027a.png\") <\/p>\n
\n ![\"\"](\"https:\/\/www.wsisp.com\/helps\/wp-content\/uploads\/2026\/02\/20260225140940-699f02a45f47a.png\") <\/p>\n
![\"\"](\"https:\/\/www.wsisp.com\/helps\/wp-content\/uploads\/2026\/02\/20260225140940-699f02a4ac92e.png\") <\/p>\n
\n ![\"\"](\"https:\/\/www.wsisp.com\/helps\/wp-content\/uploads\/2026\/02\/20260225140941-699f02a5027e7.png\") <\/p>\n
\n ![\"\"](\"https:\/\/www.wsisp.com\/helps\/wp-content\/uploads\/2026\/02\/20260225140941-699f02a5411aa.png\") <\/p>\n
![\"\"](\"https:\/\/www.wsisp.com\/helps\/wp-content\/uploads\/2026\/02\/20260225140941-699f02a581695.png\") <\/p>\n
\n ![\"\"](\"https:\/\/www.wsisp.com\/helps\/wp-content\/uploads\/2026\/02\/20260225140941-699f02a5caa79.png\") <\/p>\n
![\"\"](\"https:\/\/www.wsisp.com\/helps\/wp-content\/uploads\/2026\/02\/20260225140942-699f02a612a39.png\") <\/p>\n
\n ![\"\"](\"https:\/\/www.wsisp.com\/helps\/wp-content\/uploads\/2026\/02\/20260225140942-699f02a657279.png\") <\/p>\n
![\"\"](\"https:\/\/www.wsisp.com\/helps\/wp-content\/uploads\/2026\/02\/20260225140942-699f02a6a291e.png\") <\/p>\n
\n ![\"\"](\"https:\/\/www.wsisp.com\/helps\/wp-content\/uploads\/2026\/02\/20260225140942-699f02a6e3c41.png\") <\/p>\n
![\"\"](\"2026-02-255bqh5jt4ucw.png\") <\/p>\n
2.4 \u4ee3\u7801\u5b9e\u73b0（\u90bb\u63a5\u8868\u7248，\u9012\u5f52+\u975e\u9012\u5f52）<\/h4>\n\u57fa\u4e8e\u4e4b\u524d\u7684\u90bb\u63a5\u8868\u56fe\u7ed3\u6784，\u5b9e\u73b0DFS\u7684\u9012\u5f52\u7248（\u7b80\u6d01）\u548c\u975e\u9012\u5f52\u7248（\u901a\u7528），\u878d\u5165aoyou\u9876\u70b9，\u8d34\u5408\u793a\u4f8b\u8981\u6c42：<\/p>\n import java.util.*;<\/p>\n \/**
\n * \u56fe\u7684\u904d\u5386：DFS（\u6df1\u5ea6\u4f18\u5148\u641c\u7d22）
\n * \u57fa\u4e8e\u90bb\u63a5\u8868\u5b9e\u73b0，\u5305\u542b\u9012\u5f52+\u975e\u9012\u5f52\u7248，\u878d\u5165aoyou\u9876\u70b9
\n * @author aoyou
\n *\/
\npublic class AoyouGraphDFS {
\n \/\/ \u9876\u70b9\u7c7b：\u5c01\u88c5\u9876\u70b9\u540d\u79f0\u548c\u8fb9\u94fe\u8868
\n static class Vertex {
\n String name;
\n Edge next;
\n public Vertex(String name, Edge next) {
\n this.name = name;
\n this.next = next;
\n }
\n }
\n \/\/ \u8fb9\u7c7b：\u5c01\u88c5\u76ee\u6807\u9876\u70b9\u548c\u6743\u503c
\n static class Edge {
\n String target;
\n int weight;
\n Edge next;
\n public Edge(String target, int weight, Edge next) {
\n this.target = target;
\n this.weight = weight;
\n this.next = next;
\n }
\n }<\/p>\n private Map<String, Vertex> vertexMap; \/\/ \u5b58\u50a8\u6240\u6709\u9876\u70b9
\n private Set<String> visited; \/\/ \u8bbf\u95ee\u6807\u8bb0\u96c6\u5408，\u66ff\u4ee3\u6570\u7ec4（\u66f4\u7075\u6d3b）<\/p>\n public AoyouGraphDFS() {
\n vertexMap = new HashMap<>();
\n visited = new HashSet<>();
\n }<\/p>\n \/\/ \u63d2\u5165\u9876\u70b9
\n public void insertVertex(String name) {
\n vertexMap.putIfAbsent(name, new Vertex(name, null));
\n }
\n \/\/ \u63d2\u5165\u6709\u5411\u8fb9：begin\u2192end，\u6743\u503cweight
\n public void insertEdge(String begin, String end, int weight) {
\n Vertex beginV = vertexMap.get(begin);
\n Edge newEdge = new Edge(end, weight, beginV.next);
\n beginV.next = newEdge; \/\/ \u5934\u63d2\u6cd5（\u4e0d\u5f71\u54cd\u904d\u5386，\u4ec5\u7b80\u5316\u4ee3\u7801）
\n \/\/ \u65e0\u5411\u56fe\u9700\u989d\u5916\u63d2\u5165end\u2192begin\u7684\u8fb9
\n \/\/ insertEdge(end, begin, weight);
\n }<\/p>\n \/\/ \u3010DFS\u9012\u5f52\u7248\u3011\u4ece\u6307\u5b9a\u8d77\u70b9\u5f00\u59cb\u904d\u5386
\n public void dfsRecursive(String start) {
\n if (!vertexMap.containsKey(start) || visited.contains(start)) {
\n return;
\n }
\n \/\/ 1. \u8bbf\u95ee\u5f53\u524d\u9876\u70b9：\u6253\u5370+\u6807\u8bb0
\n System.out.print(start + " \u2192 ");
\n visited.add(start);
\n \/\/ 2. \u904d\u5386\u5f53\u524d\u9876\u70b9\u7684\u6240\u6709\u90bb\u63a5\u9876\u70b9，\u9012\u5f52\u8bbf\u95ee\u672a\u6807\u8bb0\u7684\u9876\u70b9
\n Vertex current = vertexMap.get(start);
\n Edge edge = current.next;
\n \/\/ \u6309\u5b57\u6bcd\u5e8f\u6392\u5e8f\u90bb\u63a5\u9876\u70b9（\u4fdd\u8bc1\u904d\u5386\u987a\u5e8f\u4e00\u81f4）
\n List<String> neighbors = new ArrayList<>();
\n while (edge != null) {
\n neighbors.add(edge.target);
\n edge = edge.next;
\n }
\n Collections.sort(neighbors);
\n \/\/ \u9012\u5f52\u8bbf\u95ee\u6bcf\u4e2a\u90bb\u63a5\u9876\u70b9
\n for (String neighbor : neighbors) {
\n if (!visited.contains(neighbor)) {
\n dfsRecursive(neighbor);
\n }
\n }
\n }<\/p>\n \/\/ \u3010DFS\u975e\u9012\u5f52\u7248\u3011\u4ece\u6307\u5b9a\u8d77\u70b9\u5f00\u59cb\u904d\u5386（\u663e\u5f0f\u6808）
\n public void dfsNonRecursive(String start) {
\n if (!vertexMap.containsKey(start)) {
\n return;
\n }
\n Stack<String> stack = new Stack<>();
\n Set<String> visited = new HashSet<>();
\n \/\/ 1. \u8d77\u70b9\u5165\u6808+\u6807\u8bb0
\n stack.push(start);
\n visited.add(start);
\n System.out.print("\u975e\u9012\u5f52DFS：");
\n while (!stack.isEmpty()) {
\n \/\/ 2. \u51fa\u6808\u5e76\u8bbf\u95ee\u5f53\u524d\u9876\u70b9
\n String current = stack.pop();
\n System.out.print(current + " \u2192 ");
\n \/\/ 3. \u904d\u5386\u90bb\u63a5\u9876\u70b9，\u672a\u6807\u8bb0\u7684\u5165\u6808+\u6807\u8bb0（\u9006\u5e8f\u5165\u6808，\u4fdd\u8bc1\u8bbf\u95ee\u987a\u5e8f\u4e3a\u5b57\u6bcd\u5e8f）
\n Vertex v = vertexMap.get(current);
\n Edge edge = v.next;
\n List<String> neighbors = new ArrayList<>();
\n while (edge != null) {
\n neighbors.add(edge.target);
\n edge = edge.next;
\n }
\n Collections.sort(neighbors, Collections.reverseOrder()); \/\/ \u9006\u5e8f
\n for (String neighbor : neighbors) {
\n if (!visited.contains(neighbor)) {
\n stack.push(neighbor);
\n visited.add(neighbor);
\n }
\n }
\n }
\n }<\/p>\n \/\/ \u91cd\u7f6e\u8bbf\u95ee\u6807\u8bb0（\u591a\u6b21\u904d\u5386\u7528）
\n public void resetVisited() {
\n visited.clear();
\n }<\/p>\n \/\/ \u6d4b\u8bd5\u793a\u4f8b（\u65e0\u5411\u56fe\u9700\u6ce8\u91ca\u6389\u8fb9\u7684\u5355\u5411\u63d2\u5165）
\n public static void main(String[] args) {
\n AoyouGraphDFS graph = new AoyouGraphDFS();
\n \/\/ 1. \u63d2\u5165\u9876\u70b9（\u5305\u542bA\u3001B\u3001C\u3001D\u3001E\u3001F\u3001G\u3001H\u3001aoyou）
\n String[] vertexes = {"A", "B", "C", "D", "E", "F", "G", "H", "aoyou"};
\n for (String v : vertexes) {
\n graph.insertVertex(v);
\n }
\n \/\/ 2. \u63d2\u5165\u6709\u5411\u8fb9（\u6a21\u62df\u8fde\u901a\u56fe）
\n graph.insertEdge("A", "B", 4);
\n graph.insertEdge("A", "D", 5);
\n graph.insertEdge("A", "G", 1);
\n graph.insertEdge("A", "aoyou", 8);
\n graph.insertEdge("B", "E", 2);
\n graph.insertEdge("B", "F", 3);
\n graph.insertEdge("D", "F", 4);
\n graph.insertEdge("D", "E", 3);
\n graph.insertEdge("F", "C", 2);
\n graph.insertEdge("C", "H", 5);
\n graph.insertEdge("aoyou", "G", 2); \/\/ aoyou\u8fde\u63a5G<\/p>\n \/\/ 3. \u9012\u5f52\u7248DFS（\u8d77\u70b9A）
\n System.out.print("\u9012\u5f52\u7248DFS：");
\n graph.dfsRecursive("A");
\n System.out.println("\u7ed3\u675f");<\/p>\n \/\/ 4. \u975e\u9012\u5f52\u7248DFS（\u8d77\u70b9A）
\n graph.dfsNonRecursive("A");
\n System.out.println("\u7ed3\u675f");
\n }
\n}<\/p>\n 2.5 \u8fd0\u884c\u7ed3\u679c<\/h4>\n\u9012\u5f52\u7248DFS：A \u2192 B \u2192 E \u2192 F \u2192 C \u2192 H \u2192 D \u2192 G \u2192 aoyou \u2192 \u7ed3\u675f
\n\u975e\u9012\u5f52DFS：A \u2192 B \u2192 E \u2192 F \u2192 C \u2192 H \u2192 D \u2192 G \u2192 aoyou \u2192 \u7ed3\u675f<\/p>\n \n ![\"\"](\"2026-02-25co4vbbrl2bh.png\") <\/p>\n
2.6 \u65f6\u95f4\u590d\u6742\u5ea6<\/h4>\nDFS\u7684\u65f6\u95f4\u590d\u6742\u5ea6\u4e0e\u56fe\u7684\u5b58\u50a8\u65b9\u5f0f\u76f8\u5173，\u53d6\u51b3\u4e8e\u8bbf\u95ee\u6240\u6709\u9876\u70b9\u548c\u904d\u5386\u6240\u6709\u8fb9\u7684\u5f00\u9500：<\/p>\n \u90bb\u63a5\u8868\u5b58\u50a8：\u8bbf\u95ee\u6240\u6709\u9876\u70b9\u8017\u65f6\n![\"\"](\"2026-02-251s34bdsorlv.png\") <\/p>\n
（V\u4e3a\u9876\u70b9\u6570），\u904d\u5386\u6240\u6709\u8fb9\u8017\u65f6<\/p>\n ![\"\"](\"2026-02-25wxepljwhg1z.png\") <\/p>\n
（E\u4e3a\u8fb9\u6570），\u603b\u65f6\u95f4\u590d\u6742\u5ea6<\/p>\n ![\"\"](\"2026-02-25rqdfpqn2qdn.png\") <\/p>\n
；<\/li>\n \u90bb\u63a5\u77e9\u9635\u5b58\u50a8：\u67e5\u627e\u6bcf\u4e2a\u9876\u70b9\u7684\u90bb\u63a5\u9876\u70b9\u9700\u904d\u5386\u6574\u884c，\u8017\u65f6\n![\"\"](\"2026-02-25ayolvhd1n2m.png\") <\/p>\n
，\u603b\u65f6\u95f4\u590d\u6742\u5ea6<\/p>\n ![\"\"](\"2026-02-25ptgangpmwhn.png\") <\/p>\n
\u3002<\/li>\n 2.7 \u5e94\u7528\u573a\u666f<\/h4>\nDFS\u4e13\u6ce8\u4e8e\u201c\u662f\u5426\u5b58\u5728\u8def\u5f84\u201d，\u4e0d\u5173\u5fc3\u8def\u5f84\u957f\u5ea6，\u5178\u578b\u5e94\u7528：<\/p>\n \n- \u5224\u65ad\u56fe\u7684\u8fde\u901a\u6027（\u65e0\u5411\u56fe\u662f\u5426\u4e3a\u8fde\u901a\u56fe\u3001\u6709\u5411\u56fe\u662f\u5426\u5f3a\u8fde\u901a）；<\/li>\n
- \u5bfb\u627e\u56fe\u4e2d\u7684\u73af（\u5982\u68c0\u6d4b\u4efb\u52a1\u4f9d\u8d56\u662f\u5426\u6709\u5faa\u73af）；<\/li>\n
- \u62d3\u6251\u6392\u5e8f（\u6709\u5411\u65e0\u73af\u56feDAG）\u3001\u8ff7\u5bab\u63a2\u7d22\u3001\u6392\u5217\u7ec4\u5408\u95ee\u9898；<\/li>\n
- \u6df1\u5ea6\u4f18\u5148\u7684\u641c\u7d22\u904d\u5386（\u5982\u6587\u4ef6\u5939\u7684\u9012\u5f52\u904d\u5386，\u672c\u8d28\u662f\u6811\u7684DFS）\u3002<\/li>\n<\/ul>\n
\u4e09\u3001\u5e7f\u5ea6\u4f18\u5148\u641c\u7d22（BFS，Breadth First Search）<\/h3>\n3.1 \u601d\u60f3<\/h4>\nBFS\u7684\u662f\u201c\u5e7f\u5ea6\u4f18\u5148，\u5c42\u5c42\u63a8\u8fdb\u201d，\u7c7b\u4f3c\u6c34\u9762\u6ce2\u7eb9\u6269\u6563：\u4ece\u8d77\u70b9\u51fa\u53d1，\u5148\u8bbf\u95ee\u8d77\u70b9\u7684\u6240\u6709\u90bb\u63a5\u9876\u70b9（\u7b2c\u4e00\u5c42），\u518d\u4f9d\u6b21\u8bbf\u95ee\u7b2c\u4e00\u5c42\u6bcf\u4e2a\u9876\u70b9\u7684\u90bb\u63a5\u9876\u70b9（\u7b2c\u4e8c\u5c42），\u4ee5\u6b64\u7c7b\u63a8，\u76f4\u5230\u904d\u5386\u6240\u6709\u9876\u70b9\u3002
\n\u7b80\u5355\u603b\u7ed3：\u5148\u5e7f\u540e\u6df1，\u5c42\u5c42\u904d\u5386\u3002<\/p>\n 3.2 \u5b9e\u73b0\u4f9d\u8d56<\/h4>\nBFS\u7684\u5b9e\u73b0\u4f9d\u8d56\u961f\u5217（Queue）（\u5148\u8fdb\u5148\u51faFIFO），\u5fc5\u987b\u663e\u5f0f\u5b9e\u73b0（\u65e0\u9012\u5f52\u7248），\u540c\u65f6\u9700\u8981\u8bbf\u95ee\u6807\u8bb0\u6570\u7ec4\/\u96c6\u5408，\u539f\u56e0：\u961f\u5217\u4fdd\u8bc1\u201c\u5c42\u5c42\u63a8\u8fdb\u201d\u7684\u987a\u5e8f，\u6807\u8bb0\u907f\u514d\u540c\u4e00\u9876\u70b9\u88ab\u591a\u6b21\u5165\u961f\u3002<\/p>\n 3.3 \u904d\u5386\u6b65\u9aa4（\u4ee5\u9876\u70b9A\u4e3a\u8d77\u70b9，\u90bb\u63a5\u9876\u70b9\u6309\u5b57\u6bcd\u5e8f\u5165\u961f）<\/h4>\n\n <\/p>\n \u4ee5\u4e0a\u8ff0\u8fde\u901a\u56fe\u4e3a\u4f8b，BFS\u7684\u662f\u201c\u5165\u961f\u6807\u8bb0\u2192\u51fa\u961f\u8bbf\u95ee\u2192\u90bb\u63a5\u9876\u70b9\u5165\u961f\u6807\u8bb0\u201d，\u5c42\u5c42\u904d\u5386：<\/p>\n - \u8d77\u70b9A\u5165\u961f，\u6807\u8bb0\u5df2\u8bbf\u95ee；<\/li>\n
- A\u51fa\u961f\u5e76\u8bbf\u95ee，\u5c06A\u7684\u90bb\u63a5\u9876\u70b9B\u3001D\u3001G\u3001aoyou（\u5b57\u6bcd\u5e8f）\u4f9d\u6b21\u5165\u961f，\u6807\u8bb0\u5df2\u8bbf\u95ee（\u7b2c\u4e00\u5c42）；<\/li>\n
- B\u51fa\u961f\u5e76\u8bbf\u95ee，\u5c06B\u7684\u672a\u8bbf\u95ee\u90bb\u63a5\u9876\u70b9E\u3001F\u5165\u961f，\u6807\u8bb0（\u7b2c\u4e8c\u5c42）；<\/li>\n
- D\u51fa\u961f\u5e76\u8bbf\u95ee，\u5176\u90bb\u63a5\u9876\u70b9\u5747\u5df2\u6807\u8bb0，\u65e0\u5165\u961f；G\u51fa\u961f\u5e76\u8bbf\u95ee，\u65e0\u672a\u8bbf\u95ee\u90bb\u63a5\u9876\u70b9；aoyou\u51fa\u961f\u5e76\u8bbf\u95ee，\u65e0\u672a\u8bbf\u95ee\u90bb\u63a5\u9876\u70b9；<\/li>\n
- E\u51fa\u961f\u5e76\u8bbf\u95ee，\u65e0\u672a\u8bbf\u95ee\u90bb\u63a5\u9876\u70b9；F\u51fa\u961f\u5e76\u8bbf\u95ee，\u5c06F\u7684\u672a\u8bbf\u95ee\u90bb\u63a5\u9876\u70b9C\u5165\u961f，\u6807\u8bb0（\u7b2c\u4e09\u5c42）；<\/li>\n
- C\u51fa\u961f\u5e76\u8bbf\u95ee，\u5c06C\u7684\u672a\u8bbf\u95ee\u90bb\u63a5\u9876\u70b9H\u5165\u961f，\u6807\u8bb0（\u7b2c\u56db\u5c42）；<\/li>\n
- H\u51fa\u961f\u5e76\u8bbf\u95ee，\u65e0\u672a\u8bbf\u95ee\u90bb\u63a5\u9876\u70b9；\u961f\u5217\u4e3a\u7a7a，\u904d\u5386\u7ed3\u675f\u3002<\/li>\n
\u904d\u5386\u8fc7\u7a0b<\/p>\n \n ![\"\"](\"2026-02-25q3mm4huolff.png\") <\/p>\n
![\"\"](\"2026-02-25p1iywkcjhsw.png\") <\/p>\n
![\"\"](\"2026-02-25l30x4rk0yrd.png\") <\/p>\n
\n ![\"\"](\"2026-02-25g3iao0wmt3j.png\") <\/p>\n
\n ![\"\"](\"2026-02-25axqjjkebrm2.png\") <\/p>\n
\n ![\"\"](\"2026-02-25yrenspwscxx.png\") <\/p>\n
![\"\"](\"2026-02-250wkxdcxsn0c.png\") <\/p>\n
![\"\"](\"2026-02-25ey1umkfff0l.png\") <\/p>\n
\n ![\"\"](\"2026-02-25nuz4sbdju0d.png\") <\/p>\n
3.4 \u4ee3\u7801\u5b9e\u73b0（\u90bb\u63a5\u8868\u7248，\u6c42\u89e3\u6700\u77ed\u8def\u5f84）<\/h4>\n\u57fa\u4e8e\u540c\u4e00\u90bb\u63a5\u8868\u7ed3\u6784，\u5b9e\u73b0BFS\u904d\u5386，\u5e76\u589e\u52a0\u65e0\u6743\u56fe\u6700\u77ed\u8def\u5f84\u6c42\u89e3\u529f\u80fd（BFS\u7684\u7ecf\u5178\u5e94\u7528）：<\/p>\n import java.util.*;<\/p>\n \/**
\n * \u56fe\u7684\u904d\u5386：BFS（\u5e7f\u5ea6\u4f18\u5148\u641c\u7d22）
\n * \u57fa\u4e8e\u90bb\u63a5\u8868\u5b9e\u73b0，\u542b\u904d\u5386+\u65e0\u6743\u56fe\u6700\u77ed\u8def\u5f84\u6c42\u89e3
\n * @author aoyou
\n *\/
\npublic class AoyouGraphBFS {
\n \/\/ \u590d\u7528\u9876\u70b9\u7c7b\u548c\u8fb9\u7c7b（\u4e0eDFS\u4e00\u81f4，\u7701\u7565）
\n static class Vertex {
\n String name;
\n Edge next;
\n public Vertex(String name, Edge next) {
\n this.name = name;
\n this.next = next;
\n }
\n }
\n static class Edge {
\n String target;
\n int weight;
\n Edge next;
\n public Edge(String target, int weight, Edge next) {
\n this.target = target;
\n this.weight = weight;
\n this.next = next;
\n }
\n }<\/p>\n private Map<String, Vertex> vertexMap;<\/p>\n public AoyouGraphBFS() {
\n vertexMap = new HashMap<>();
\n }<\/p>\n \/\/ \u63d2\u5165\u9876\u70b9\u3001\u63d2\u5165\u8fb9（\u4e0eDFS\u4e00\u81f4，\u7701\u7565）
\n public void insertVertex(String name) {
\n vertexMap.putIfAbsent(name, new Vertex(name, null));
\n }
\n public void insertEdge(String begin, String end, int weight) {
\n Vertex beginV = vertexMap.get(begin);
\n Edge newEdge = new Edge(end, weight, beginV.next);
\n beginV.next = newEdge;
\n \/\/ \u65e0\u5411\u56fe\u8bf7\u6dfb\u52a0：insertEdge(end, begin, weight);
\n }<\/p>\n \/\/ \u3010BFS\u904d\u5386\u3011\u4ece\u6307\u5b9a\u8d77\u70b9\u904d\u5386\u6240\u6709\u9876\u70b9
\n public void bfsTraverse(String start) {
\n if (!vertexMap.containsKey(start)) {
\n System.out.println("\u8d77\u70b9\u9876\u70b9\u4e0d\u5b58\u5728！");
\n return;
\n }
\n Queue<String> queue = new LinkedList<>();
\n Set<String> visited = new HashSet<>();
\n \/\/ \u8d77\u70b9\u5165\u961f+\u6807\u8bb0
\n queue.offer(start);
\n visited.add(start);
\n System.out.print("BFS\u904d\u5386\u5e8f\u5217：");
\n while (!queue.isEmpty()) {
\n \/\/ \u51fa\u961f\u5e76\u8bbf\u95ee\u5f53\u524d\u9876\u70b9
\n String current = queue.poll();
\n System.out.print(current + " \u2192 ");
\n \/\/ \u904d\u5386\u90bb\u63a5\u9876\u70b9，\u672a\u6807\u8bb0\u7684\u5165\u961f+\u6807\u8bb0（\u6309\u5b57\u6bcd\u5e8f）
\n Vertex v = vertexMap.get(current);
\n Edge edge = v.next;
\n List<String> neighbors = new ArrayList<>();
\n while (edge != null) {
\n neighbors.add(edge.target);
\n edge = edge.next;
\n }
\n Collections.sort(neighbors);
\n for (String neighbor : neighbors) {
\n if (!visited.contains(neighbor)) {
\n queue.offer(neighbor);
\n visited.add(neighbor);
\n }
\n }
\n }
\n System.out.println("\u7ed3\u675f");
\n }<\/p>\n \/\/ \u3010BFS\u7ecf\u5178\u5e94\u7528\u3011\u6c42\u89e3\u65e0\u6743\u56fe\u4e2d\u8d77\u70b9\u5230\u76ee\u6807\u9876\u70b9\u7684\u6700\u77ed\u8def\u5f84（\u8fb9\u6570）
\n public int bfsShortestPath(String start, String target) {
\n if (!vertexMap.containsKey(start) || !vertexMap.containsKey(target)) {
\n return -1; \/\/ \u9876\u70b9\u4e0d\u5b58\u5728，\u8fd4\u56de-1\u8868\u793a\u4e0d\u53ef\u8fbe
\n }
\n if (start.equals(target)) {
\n return 0; \/\/ \u8d77\u70b9=\u76ee\u6807，\u8def\u5f84\u957f\u5ea60
\n }
\n Queue<String> queue = new LinkedList<>();
\n Set<String> visited = new HashSet<>();
\n Map<String, Integer> pathLen = new HashMap<>(); \/\/ \u8bb0\u5f55\u6bcf\u4e2a\u9876\u70b9\u5230\u8d77\u70b9\u7684\u8def\u5f84\u957f\u5ea6
\n \/\/ \u521d\u59cb\u5316
\n queue.offer(start);
\n visited.add(start);
\n pathLen.put(start, 0);<\/p>\n while (!queue.isEmpty()) {
\n String current = queue.poll();
\n \/\/ \u904d\u5386\u90bb\u63a5\u9876\u70b9
\n Vertex v = vertexMap.get(current);
\n Edge edge = v.next;
\n while (edge != null) {
\n String neighbor = edge.target;
\n if (neighbor.equals(target)) {
\n return pathLen.get(current) + 1; \/\/ \u627e\u5230\u76ee\u6807，\u8fd4\u56de\u8def\u5f84\u957f\u5ea6
\n }
\n if (!visited.contains(neighbor)) {
\n visited.add(neighbor);
\n queue.offer(neighbor);
\n pathLen.put(neighbor, pathLen.get(current) + 1);
\n }
\n edge = edge.next;
\n }
\n }
\n return -1; \/\/ \u65e0\u8def\u5f84\u53ef\u8fbe
\n }<\/p>\n \/\/ \u6d4b\u8bd5\u793a\u4f8b
\n public static void main(String[] args) {
\n AoyouGraphBFS graph = new AoyouGraphBFS();
\n \/\/ 1. \u63d2\u5165\u9876\u70b9（A\u3001B\u3001C\u3001D\u3001E\u3001F\u3001G\u3001H\u3001aoyou）
\n String[] vertexes = {"A", "B", "C", "D", "E", "F", "G", "H", "aoyou"};
\n for (String v : vertexes) {
\n graph.insertVertex(v);
\n }
\n \/\/ 2. \u63d2\u5165\u6709\u5411\u8fb9
\n graph.insertEdge("A", "B", 4);
\n graph.insertEdge("A", "D", 5);
\n graph.insertEdge("A", "G", 1);
\n graph.insertEdge("A", "aoyou", 8);
\n graph.insertEdge("B", "E", 2);
\n graph.insertEdge("B", "F", 3);
\n graph.insertEdge("D", "F", 4);
\n graph.insertEdge("D", "E", 3);
\n graph.insertEdge("F", "C", 2);
\n graph.insertEdge("C", "H", 5);
\n graph.insertEdge("aoyou", "G", 2);<\/p>\n \/\/ 3. BFS\u904d\u5386（\u8d77\u70b9A）
\n graph.bfsTraverse("A");<\/p>\n \/\/ 4. \u6c42\u89e3\u6700\u77ed\u8def\u5f84（\u65e0\u6743\u56fe）
\n System.out.println("A\u5230aoyou\u7684\u6700\u77ed\u8def\u5f84\u957f\u5ea6：" + graph.bfsShortestPath("A", "aoyou"));
\n System.out.println("A\u5230H\u7684\u6700\u77ed\u8def\u5f84\u957f\u5ea6：" + graph.bfsShortestPath("A", "H"));
\n System.out.println("aoyou\u5230H\u7684\u6700\u77ed\u8def\u5f84\u957f\u5ea6：" + graph.bfsShortestPath("aoyou", "H"));
\n }
\n}<\/p>\n 3.5 \u8fd0\u884c\u7ed3\u679c<\/h4>\nBFS\u904d\u5386\u5e8f\u5217：A \u2192 B \u2192 D \u2192 G \u2192 aoyou \u2192 E \u2192 F \u2192 C \u2192 H \u2192 \u7ed3\u675f
\nA\u5230aoyou\u7684\u6700\u77ed\u8def\u5f84\u957f\u5ea6：1
\nA\u5230H\u7684\u6700\u77ed\u8def\u5f84\u957f\u5ea6：4
\naoyou\u5230H\u7684\u6700\u77ed\u8def\u5f84\u957f\u5ea6：-1<\/p>\n \n ![\"\"](\"2026-02-25hnzzykii5b1.png\") <\/p>\n
3.6 \u65f6\u95f4\u590d\u6742\u5ea6<\/h4>\nBFS\u7684\u65f6\u95f4\u590d\u6742\u5ea6\u4e0eDFS\u5b8c\u5168\u4e00\u81f4，\u4ec5\u4f9d\u8d56\u5b58\u50a8\u65b9\u5f0f，\u4e0e\u904d\u5386\u7b56\u7565\u65e0\u5173：<\/p>\n - \u90bb\u63a5\u8868\u5b58\u50a8：\u8bbf\u95ee\u9876\u70b9 + \u904d\u5386\u8fb9 \u2192 \u603b；<\/li>\n
- \u90bb\u63a5\u77e9\u9635\u5b58\u50a8：\u67e5\u627e\u90bb\u63a5\u9876\u70b9 \u2192 \u603b\u3002<\/li>\n
3.7 \u5e94\u7528\u573a\u666f<\/h4>\nBFS\u4e13\u6ce8\u4e8e\u201c\u6700\u77ed\u8def\u5f84\u201d（\u65e0\u6743\u56fe），\u5c42\u5c42\u63a8\u8fdb\u7684\u7279\u6027\u4f7f\u5176\u9002\u5408\u591a\u6e90\u904d\u5386，\u5178\u578b\u5e94\u7528：<\/p>\n |
![\"\"](\"https:\/\/www.wsisp.com\/helps\/wp-content\/uploads\/2026\/02\/20260225140937-699f02a15c13f.png\")
<\/p>\n