public ArrayList 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 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 traversal = new ArrayList(); //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; }
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;
}
![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, 8, 0}},0) -> new java.util.ArrayList<Integer>(){{add(0); add(3); add (1); add(2);}}
Your Answer:
Feedback
public ArrayList<Integer> depthFirstTraversal (int00 adjacency_matrix, int source)
Your feedback will appear here when you check your answer.
//A matríx 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 Stacko)
int numNodes - adjacency_matrix.length;
9
10
11
//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);
12
13
14
15
16
//This variable will hold the index of the element currently being analyzed
17
int element;
18
19
//The result of the traversal will be stored in this arraylist
ArrayList<Integer> traversal - new ArrayList<Integer> ();
20
21
22
//since the source index is passed in it has already been visited
23
visited[source] - true;
24
25
//The source index is added to the queue to continue processing it
stack.push (source);
26
27
28
while (Istack.isEmpty() {
29
30
//The first item from the stack is popped off and stored ín element](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2F2cfe3bec-4f28-49a3-8bd8-c4441e0c568b%2Fc7c0d178-092f-4145-96c9-85b42b097fde%2Fyxl1jxx_processed.png&w=3840&q=75)
Step by step
Solved in 2 steps
