How to implement Breadth First Search and Depth First Search for a SimpleWeightedGraph in Java

I need to implement Breadth First Search and Depth First Search for a SimpleWeightedGraph which contains String Vertices in Java

Code below is my SimpleWeightedGraph where i implemented the following:

1. declared SimpleWeightedGraph
2. created vertices
3. added vertices to the graph
4. created default weighted edges, added edges and set Weights
5. got and printed the shortest path from vertex “a” to vertex “e”
6. got and printed the weight from vertex “a” to vertex “e”
7. got and printed the start vertex between vertex “a” and vertex “e”
8. got and printed the end vertex between vertex “a” and vertex “e”

The above mentioned works as expected.

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

    }
}

Answer

Pseudocode only.

You will need a Set that can contain the places in your graph that you’ve visited. And a Queue or Stack for the work to be done. Then the algorithm looks like:

initialize visited to be a Set
Initialize todo to be a Queue or Stack
todo.push(start)
while todo not empty:
    next_node = todo.pop()
    if next_node not in visited:
        visited.add(next_node)
        for child in next_node.children:
            todo.append(child)
        process next_node in whatever way you want

If you choose a stack, it will be depth first. If you choose a queue, it will be breadth first.

Note that MOST implementations you encounter of depth first search will hide the stack inside the call stack by making it recursive. That makes them look very different, but doesn’t change how they really work. It also hides how fundamentally similar the two forms of search are.

Note that we can use other data structures instead of a stack or queue. For example the pathfinding algorithm A* search uses a Priority Queue to come out with the most promising candidate for a shortest path.