Java中为String类型顶点的SimpleWeightedGraph实现BFS与DFS

需求说明 #

需要使用Java语言，为顶点类型为String的SimpleWeightedGraph实现广度优先搜索（Breadth First Search，简称BFS）与深度优先搜索（Depth First Search，简称DFS）遍历功能。

现有已完成功能 #

当前已编写的代码已经完成以下功能，且均验证可正常运行：

• 声明SimpleWeightedGraph实例
• 创建图的各个顶点
• 将顶点添加到图结构中
• 创建DefaultWeightedEdge默认加权边，添加边并设置对应权重
• 获取并打印顶点"a"到顶点"e"的最短路径
• 获取并打印顶点"a"到顶点"e"的路径总权重
• 获取并打印顶点"a"到顶点"e"路径的起始顶点
• 获取并打印顶点"a"到顶点"e"路径的终止顶点
  当前构建的无向加权图结构如下：

(A)---68--(B)
     | \    / |
     | 9\  /74|
   10|   (C)  |24
     | 8/  \55|
     | /    \ |
    (D)---7--(E)

现有完整代码 #

import org.jgrapht.alg.shortestpath.DijkstraShortestPath;
import org.jgrapht.graph.DefaultWeightedEdge;
import org.jgrapht.graph.SimpleWeightedGraph;

public class GrapgsExample {

    public static void main(String[] args) {


        // below is my graph...
        //
        //     (A)---68--(B)
        //      | \    / |
        //      | 9\  /74|
        //    10|   (C)  |24
        //      | 8/  \55|
        //      | /    \ |
        //     (D)---7--(E)
        //

        //declare SimpleWeightedGraph
        SimpleWeightedGraph<String, DefaultWeightedEdge> graph;
        graph = new SimpleWeightedGraph<>(DefaultWeightedEdge.class);

        // create vertices

        String a = "a";
        String b = "b";
        String c = "c";
        String d = "d";
        String e = "e";

        // add the vertices in graph

        graph.addVertex(a);
        graph.addVertex(b);
        graph.addVertex(c);
        graph.addVertex(d);
        graph.addVertex(e);

        // create default weighted edges and add edges and set edgeWeights.
        DefaultWeightedEdge aToB = graph.addEdge(a, b);
        graph.setEdgeWeight(aToB, 68);

        DefaultWeightedEdge aT0c = graph.addEdge(a,c);
        graph.setEdgeWeight(aT0c, 9);

        DefaultWeightedEdge aT0d = graph.addEdge(a,d);
        graph.setEdgeWeight(aT0d, 10);

        DefaultWeightedEdge bT0c = graph.addEdge(b,c);
        graph.setEdgeWeight(bT0c, 74);

        DefaultWeightedEdge bT0e = graph.addEdge(b,e);
        graph.setEdgeWeight(bT0e, 24);

        DefaultWeightedEdge cT0e = graph.addEdge(c,e);
        graph.setEdgeWeight(cT0e, 55);

        DefaultWeightedEdge cT0d = graph.addEdge(c,d);
        graph.setEdgeWeight(cT0d, 8);

        DefaultWeightedEdge dT0e = graph.addEdge(d,e);
        graph.setEdgeWeight(dT0e, 7);

        // shortest path
        DijkstraShortestPath<String, DefaultWeightedEdge> path = new DijkstraShortestPath<>(graph);

        var shortestPath = path.getPath(a, e);
        var weight = path.getPath(a, e).getWeight();
        var startVertex = path.getPath(a, e).getStartVertex();
        var endVertex = path.getPath(a, e).getEndVertex();


        System.out.println("shortest path from \"a\" to \"e\" "+ shortestPath); //this get the shortest path which is [(a : d), (d : e)]
        System.out.println("weight from a to e "+weight); // the weight is 10 + 7 = 17
        System.out.println("start Vertex between \"a\" and \"e\" is "+startVertex);
        System.out.println("end Vertex between \"a\" and \"e\" is "+endVertex);


        // Breadth First Search and Depth First Search... not implemented

    }
}

实现方案 #

方法1：调用JGraphT内置遍历器（生产环境推荐） #

JGraphT自带封装完善的遍历工具类，无需手动编写队列、栈逻辑，稳定性更高。首先导入两个遍历类：

import org.jgrapht.traverse.BreadthFirstIterator;
import org.jgrapht.traverse.DepthFirstIterator;

在原代码标注的BFS/DFS待实现位置添加以下代码：

// BFS遍历，起点为顶点a
System.out.println("=== BFS遍历结果（从a出发） ===");
BreadthFirstIterator<String, DefaultWeightedEdge> bfsIterator = new BreadthFirstIterator<>(graph, a);
while (bfsIterator.hasNext()) {
    System.out.print(bfsIterator.next() + " ");
}
System.out.println();

// DFS遍历，起点为顶点a
System.out.println("=== DFS遍历结果（从a出发） ===");
DepthFirstIterator<String, DefaultWeightedEdge> dfsIterator = new DepthFirstIterator<>(graph, a);
while (dfsIterator.hasNext()) {
    System.out.print(dfsIterator.next() + " ");
}

运行输出参考（邻接点遍历顺序由边存储顺序决定，符合遍历规则即为正确结果）：

=== BFS遍历结果（从a出发） ===
a b c d e 
=== DFS遍历结果（从a出发） ===
a d e c b 

方法2：手动实现遍历（用于原理理解） #

如果需要自己实现遍历逻辑，可以参考以下代码，不依赖JGraphT额外的遍历包：

import java.util.*;

// 手动实现BFS
public static List<String> bfs(SimpleWeightedGraph<String, DefaultWeightedEdge> graph, String start) {
    List<String> res = new ArrayList<>();
    Set<String> visited = new HashSet<>();
    Queue<String> queue = new LinkedList<>();
    queue.offer(start);
    visited.add(start);
    while (!queue.isEmpty()) {
        String cur = queue.poll();
        res.add(cur);
        for (DefaultWeightedEdge edge : graph.edgesOf(cur)) {
            String neighbor = graph.getEdgeTarget(edge).equals(cur) ? graph.getEdgeSource(edge) : graph.getEdgeTarget(edge);
            if (!visited.contains(neighbor)) {
                visited.add(neighbor);
                queue.offer(neighbor);
            }
        }
    }
    return res;
}

// 手动实现DFS
public static List<String> dfs(SimpleWeightedGraph<String, DefaultWeightedEdge> graph, String start) {
    List<String> res = new ArrayList<>();
    Set<String> visited = new HashSet<>();
    Deque<String> stack = new ArrayDeque<>();
    stack.push(start);
    while (!stack.isEmpty()) {
        String cur = stack.pop();
        if (visited.contains(cur)) continue;
        visited.add(cur);
        res.add(cur);
        for (DefaultWeightedEdge edge : graph.edgesOf(cur)) {
            String neighbor = graph.getEdgeTarget(edge).equals(cur) ? graph.getEdgeSource(edge) : graph.getEdgeTarget(edge);
            if (!visited.contains(neighbor)) {
                stack.push(neighbor);
            }
        }
    }
    return res;
}

调用方式：

System.out.println("手动实现BFS结果：" + bfs(graph, a));
System.out.println("手动实现DFS结果：" + dfs(graph, a));

内容的提问来源于stack exchange，提问作者Tinyiko Chauke