Breadth-first search in Java: competitive style

Question

Here my attempt was to write a graph algorithm the way a competitive programmer would write under time pressure. The problem to solve was to find a shortest path in a directed, unweighted graph using breadth-first search algorithm (BFS, for short).

Basically, I would like to hear comments on my style. Is it effective, for example?

import java.util.Arrays;
class BFS {
 static int[] bfs(int[][] graph, int sourceNode, int targetNode) {
 int[] queue = new int[graph.length];
 int[] distance = new int[graph.length];
 int[] parents = new int[graph.length];
 for (int i = 0; i < parents.length; i++) {
 parents[i] = -1;
 }
 int queueStartIndex = 0;
 int queueEndIndex = 1;
 queue[0] = sourceNode;
 distance[sourceNode] = 0;
 while (queueStartIndex < queueEndIndex) {
 int currentNode = queue[queueStartIndex++];
 if (currentNode == targetNode) {
 return buildPath(targetNode, 
 distance[targetNode] + 1,
 parents);
 }
 for (int childNode : graph[currentNode]) {
 if (parents[childNode] == -1) {
 parents[childNode] = currentNode;
 distance[childNode] = distance[currentNode] + 1;
 queue[queueEndIndex++] = childNode;
 }
 }
 }
 return null;
 }
 private static int[] buildPath(int targetNode,
 int pathLength,
 int[] parents) {
 int[] path = new int[pathLength];
 int pathIndex = path.length - 1;
 int currentNode = targetNode;
 while (currentNode != -1) {
 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)));
 } 
}

(See the next iteration.)

• simbo1905: Surely the definition of the problem should be given. Please exactly state the definition of the problem the code is to solve. Also if it's competitive there would be some criteria that it is scored under.
• coderodde: Thanks, @simbo1905. Added the description of the problem being solved.

Answer 1

• Correctness.

  The parent of the source node is initially -1, and buildPath relies on that. However, if the source node belongs to a cycle, its parent will be eventually reassigned, breaking the contract. Now buildPath will misbehave.

• Efficiency.

  Since the algorithm assumes an unweighted graph, the distance array seems redundant. In the implementation only one value is used, only to hint buildPath on the size of the path array. Meanwhile, the distances are incremented likely \$O(V)\$ times, and surely more than P = pathLength times. Instead you can let buildPath to compute P, trading \$O(V)\$ increments for \$O(P)\$ path length computation.