2
\$\begingroup\$

I have improved my BFS in Java according to vnp's suggestions. Again, we wish to find shortest paths in directed unweighted graphs using BFS, competitive style (no Maps, Set's or Lists):

import java.util.Arrays;

class BFS {

    static int[] bfs(int[][] graph, int sourceNode, int targetNode) {
        int[] queue = new int[graph.length];
        int[] parents = new int[graph.length];

        for (int i = 0; i < parents.length; i++) {
            parents[i] = -1; // -1 denotes 'not used'
        }

        int queueStartIndex = 0;
        int queueEndIndex = 1;

        queue[0] = sourceNode;
        parents[sourceNode] = -2;

        while (queueStartIndex < queueEndIndex) {
            int currentNode = queue[queueStartIndex++];

            if (currentNode == targetNode) {
                return buildPath(targetNode, parents);
            }

            for (int childNode : graph[currentNode]) {
                if (parents[childNode] == -1) {
                    parents[childNode] = currentNode;
                    queue[queueEndIndex++] = childNode;
                }
            }
        }

        return null;
    }

    private static int[] buildPath(int targetNode, int[] parents) {
        int pathLength = 0;
        int node = targetNode;

        while (node >= 0) {
            pathLength++;
            node = parents[node];
        }

        int[] path = new int[pathLength];
        int pathIndex = path.length - 1;
        int currentNode = targetNode;

        while (currentNode >= 0) {
            path[pathIndex--] = currentNode;
            currentNode = parents[currentNode];
        }

        return path;
    }

    /*    B ----+
         /      |
        A       E
         \      /
          C - D
    */

    public static void main(String[] args) {
        int a = 0;
        int b = 1;
        int c = 2;
        int d = 3;
        int e = 4;

        int[][] graph = new int[5][];
        graph[a] = new int[]{ c, b };
        graph[b] = new int[]{ e };
        graph[c] = new int[]{ d };
        graph[d] = new int[]{ c, e };
        graph[e] = new int[]{ b, d };

        // A -> B -> E
        int[] path = bfs(graph, a, e);
        System.out.println(Arrays.toString(path));

        // A <- B <- E does not exist:
        System.out.println(Arrays.toString(bfs(graph, e, a)));

        graph = new int[4][];
        graph[a] = new int[]{ b, c };
        graph[b] = new int[]{ d };
        graph[c] = new int[]{ a, d };
        graph[d] = new int[]{ b, c };

        /*     B
              / \
             A   D
              \ /
               C
        */

        // A -> B -> D
        path = bfs(graph, a, d);
        System.out.println(Arrays.toString(path));

        path = bfs(graph, d, a);
        // D -> C -> A:
        System.out.println(Arrays.toString(path));
    }    
}

Please tell me anything that comes to mind.

\$\endgroup\$
  • \$\begingroup\$ is there any reason why you implement this code in java? one benefit of java is OOP and your code has not much Objects... \$\endgroup\$ – Martin Frank May 7 at 7:45
  • \$\begingroup\$ @MartinFrank (1) It's written in competition in mind where people have no time for implementing, say, graph node types, but instead represent them via simple int value. (2) The above requires no Objects... \$\endgroup\$ – coderodde May 7 at 8:53
  • \$\begingroup\$ well, ok, if that is fine for you ... i don't understand that 'competitive style' yet, time to go back on my books... \$\endgroup\$ – Martin Frank May 7 at 10:19
  • 1
    \$\begingroup\$ @MartinFrank Google up in YouTube "acm icpc world finals 2018" ;) \$\endgroup\$ – coderodde May 7 at 10:33
  • \$\begingroup\$ thank you very very much on how to find that - googling 'competive style' was rather worthless !!! \$\endgroup\$ – Martin Frank May 7 at 10:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.