Skip to main content
added 145 characters in body
Source Link
coderodde
  • 32.3k
  • 15
  • 79
  • 205

(See the next iteration.)

(See the next iteration.)

Added the definition of the problem being solved in the code.
Source Link
coderodde
  • 32.3k
  • 15
  • 79
  • 205

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?

Here my attempt was to write a graph algorithm the way a competitive programmer would write under time pressure. Basically, I would like to hear comments on my style. Is it effective, for example?

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?

Source Link
coderodde
  • 32.3k
  • 15
  • 79
  • 205

Breadth-first search in Java: competitive style

Here my attempt was to write a graph algorithm the way a competitive programmer would write under time pressure. 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)));
    }    
}