X443: Graphs - Depth First Traversal

Given is an adjacency matrix and a starting index.

Complete the depth first traversal method. Comments noted with //_________________ are lines that must be completed
java.util.Stack and java.util.ArrayList have been enabled.

Examples:

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

Your Answer:

Answer code

public ArrayList<Integer> depthFirstTraversal(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

    //Stack is created
    //This stack will be used to process nodes in LIFO order when an unvisited node is found
    Stack<Integer> stack = new Stack<>();
    int numNodes = adjacency_matrix.length;

    //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[numNodes];

    //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
    stack.push(source);

    while (!stack.isEmpty()) {

        //The first item from the stack is popped off and stored in element
        //___________
        //Since this item has been processed it is added to the resulting array list
        //___________

        for (int i = 0; i < numNodes; 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 pushed on to the stack
                //___________

                //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.