Graph Search Algorithms

In this post next graph search algorithm are discussed:

• Depth-First Search
• Breadth-First Search
• Dijkstra's algorithm

Class diagram:

Main methods of a class Graph:

• dfs - Depth-First Search
• bfs - Breadth-First Search
• dijkstra - Dijkstra's algorithm

Methods definition could be found below:

public class Graph {
   
   ...
   
    public List<Node> dfs(Node node) {
        clearVisited();
   
        return dfs(node, new LinkedList<Node>());
    }
   
    private List<Node> dfs(Node node, List<Node> dfsNodes) {
        if (isVisited(node))
            return dfsNodes;
   
        visit(node);
        dfsNodes.add(node);
   
        for (Edge edge : node.getEdges())
            dfsNodes = dfs(edge.getNode(), dfsNodes);
        return dfsNodes;
    }
   
    public List<Node> bfs(Node node) {
        clearVisited();
   
        Queue<Node> queue = new LinkedList<Node>();
        queue.add(node);
   
        return bfs(queue, new LinkedList<Node>());
    }
   
    private List<Node> bfs(Queue<Node> queue, List<Node> bfsNodes) {
        while (!queue.isEmpty()) {
            Node node = queue.remove();
   
            if (!isVisited(node)) {
                visit(node);
                bfsNodes.add(node);
   
                for (Edge edge : node.getEdges())
                    queue.add(edge.getNode());
            }
        }
        return bfsNodes;
    }
   
    public Map<Node, Integer> dijkstra(Node current) {
        Map<Node, Integer> weights = new HashMap<Node, Integer>();
        for (Node node : getNodes())
            weights.put(node, Integer.MAX_VALUE);
        weights.put(current, 0);
   
        clearVisited();
        do {
            int minWeight = Integer.MAX_VALUE;
            Node minNode = null;
   
            for (Edge edge : current.getEdges()) {
                Node node = edge.getNode();
                int weight = weights.get(current) + edge.getWeight();
   
                if (weight < weights.get(node))
                    weights.put(node, weight);
   
                if ((weight < minWeight) && (!isVisited(node))) {
                    minWeight = weight;
                    minNode = node;
                }
            }
            visit(current);
            current = minNode;
        } while (current != null);
        return weights;
    }
}