X432: Graphs - Breadth First Traversal

Given is an adjacency matrix and a starting index.

Complete the breadth first traversal method. Comments noted with //_________________ are lines that must be completed.
Queue, LinkedList and ArrayList have been enabled. The Queue API can be viewed here:
https://docs.oracle.com/javase/7/docs/api/java/util/Queue.html

Examples:

breadthFirstTraversal({{0, 1, 0, 0},{0, 0, 1, 0},{0, 0, 0, 1}, {0, 1, 1, 0}},0) -> new java.util.ArrayList<Integer>(){{add(0);add(1);add(2);add(3);}}

Your Answer:

Answer code

public ArrayList<Integer> breadthFirstTraversal(int[][] adjacency_matrix, int source)
{
    //A matrix and a source index is passed in
    //The traversal will be performed on this matrix and begin from the source index

    //Queue is created
    //This queue will be used to process nodes in FIFO order when an unvisited node is found
    Queue<Integer> queue = new LinkedList<>();
    
    //boolean array is created
    //This array will have a slot for each node
    //Whenever an unvisited node is visited it's slot in this array will be marked
    boolean[] visited = new boolean[adjacency_matrix.length];
    
    //This variable will hold the index of the element currently being analyzed
    int element;
    
    //The result of the traversal will be stored in this arraylist
    ArrayList<Integer> traversal = new ArrayList<Integer>();

    //Since the source index is passed in it has already been visited
    visited[source] = true;
    
    //The source index is added to the queue to continue processing it
    queue.add(source);

    while (!queue.isEmpty()) {
    
        //The first item from the queue is removed and stored in element
        //_____________________
        //Since this item has been processed it is added to the resulting array list
        //_____________________

        for (int i = 0; i < adjacency_matrix.length; i++) {
            //At the row in the matrix where element is stored
            //If that slot is not zero it means that node can be traveled to from the current element
            //If that node has not been checked off in the visited array
            if (adjacency_matrix[element][i] != 0 && visited[i] == false) {
                //The index currently being looked at will be added to the queue
                //_____________________
                
                //That index has now been visited, so it is checked off in the visited array
                //_____________________
            }
        }
    }
    //Once the traversal has been completed the array list is returned
    return traversal;
}

Reset

Practice a different Java exercise

Feedback

Your feedback will appear here when you check your answer.