@@ -0,0 +1,2446 @@
+package com.graphs;%0A%0Aimport java.util.ArrayDeque;%0Aimport java.util.Arrays;%0Aimport java.util.LinkedList;%0Aimport java.util.Queue;%0A%0A/**%0A * Given a graph G and a vertex S, we use the BFS to find the most direct path%0A * between any vertex and S.%0A * %0A * @author STEPHANE MIGUEL KAKANAKOU (Skakanakou@gmail.com)%0A *%0A */%0Apublic class MostDirectPath %7B%0A%0A    /*** The Source vertex of the BFS */%0A    private int S;%0A%0A    /*** Array that contains the distance from the source to other vertices */%0A    private int%5B%5D dist;%0A%0A    /*** Array that contains the path from the source to other vertices */%0A    private int%5B%5D prev;%0A%0A    /**%0A     * Constructor that take the graph and the source vertex.%0A     * %0A     * @param graph%0A     * @param S%0A     */%0A    public MostDirectPath(GraphAdjacencyListRepresentation graph, int S) %7B%0A        int v_size = graph.getV_Size();%0A        if ((S %3C 0) %7C%7C (S %3E= v_size))%0A            throw new IllegalArgumentException(%22Invalid Argument%22);%0A        this.S = S;%0A        dist = new int%5Bv_size%5D;%0A        prev = new int%5Bv_size%5D;%0A        Arrays.fill(dist, -1);%0A        Arrays.fill(prev, -1);%0A%0A        bfs(graph);%0A%0A    %7D%0A%0A    /*%0A     * Private method that perform the Breath First Search on the graph%0A     */%0A    private void bfs(GraphAdjacencyListRepresentation graph) %7B%0A        dist%5BS%5D = 0;%0A        Queue%3CInteger%3E queue = new ArrayDeque%3C%3E();%0A        queue.add(S);%0A        int u;%0A        while (!queue.isEmpty()) %7B%0A            u = queue.poll();%0A            for (int v : graph.getAdjNode(u)) %7B%0A                if (dist%5Bv%5D == -1) %7B%0A                    dist%5Bv%5D = dist%5Bu%5D + 1;%0A                    prev%5Bv%5D = u;%0A                    queue.add(v);%0A                %7D%0A            %7D%0A        %7D%0A    %7D%0A%0A    /**%0A     * Return the value of the most direct distance from the source vertex to a%0A     * given vertex.%0A     * %0A     * @param v%0A     * @return return the most direct distance value.%0A     */%0A    public int getDistance(int v) %7B%0A        return dist%5Bv%5D;%0A    %7D%0A%0A    /**%0A     * Return the most direct path from the source vertex to the given vertex.%0A     * %0A     * @param v%0A     * @return The most direct path%0A     */%0A    public LinkedList%3CInteger%3E getMostDirectPath(int v) %7B%0A        if (dist%5Bv%5D == -1)%0A            return null;%0A        LinkedList%3CInteger%3E directPath = new LinkedList%3C%3E();%0A        while (v != S) %7B%0A            directPath.addFirst(v);%0A            v = prev%5Bv%5D;%0A        %7D%0A        directPath.addFirst(S);%0A        return directPath;%0A    %7D%0A%0A%7D%0A

Add MostDirectPath class that use BFS to solve the most direct route problem