How would you implement the methods described above in Java using an Adjacency M

Question

How would you implement the methods described above in Java using an Adjacency Matrix? Assume that T is a node class that simply contains the index of the Node. Also assume I have a working Adjacency Matrix called arrayMap which is a 2D array of doubles with edges represented by '1'. If this question is too specific, please just let me know how to traverse a graph represented by an Adjacency Matrix using Java.

Iterato dfsNodeListing Returns an Iterator over all es in this graph, according to the order they are encountered in a DFS traversal Iterator bfsNodeListing Returns an Iterator over all nodes in this graph, according to the order they are encountered in a BFs traversal

Explanation / Answer

Hi,

Here is the code for DFS traversal of a tree in java

import java.util.InputMismatchException;
import java.util.Scanner;
import java.util.Stack;

public class DFS
{
private Stack<Integer> stack;

public DFS()
{
stack = new Stack<Integer>();
}

public void dfs(int arrayMap[][], int source)
{
int number_of_nodes = arrayMap[source].length - 1;

int visited[] = new int[number_of_nodes + 1];
int element = source;
int i = source;
System.out.print(element + " ");
visited[source] = 1;
stack.push(source);

while (!stack.isEmpty())
{
element = stack.peek();
i = element;
while (i <= number_of_nodes)
{
if (arrayMap[element][i] == 1 && visited[i] == 0)
{
stack.push(i);
visited[i] = 1;
element = i;
i = 1;
System.out.print(element + " ");
continue;
}
i++;
}
stack.pop();
}
}

public BFS()
{
queue = new LinkedList<Integer>();
}

public void bfs(int arrayMap[][], int source)
{
int number_of_nodes = arrayMap[source].length - 1;

int[] visited = new int[number_of_nodes + 1];
int i, element;

visited[source] = 1;
queue.add(source);

while (!queue.isEmpty())
{
element = queue.remove();
i = element;
System.out.print(i + " ");
while (i <= number_of_nodes)
{
if (arrayMap[element][i] == 1 && visited[i] == 0)
{
queue.add(i);
visited[i] = 1;
}
i++;
}
}
}

public static void main(String...arg)
{

try
{
System.out.println("The DFS Traversal for the graph is given by ");
DFS dfs = new DFS();
dfs.dfs(arrayMap, T);
           System.out.println("The BFS Traversal for the graph is given by ");
BFS bfs = new BFS();
bfs.bfs(arrayMap, T);  
}catch(InputMismatchException inputMismatch)
{
System.out.println("Wrong Input format");
}
}
}

unlike trees, graphs may contain cycles, so we may come to the same node again. To avoid processing a node more than once, we use a boolean visited array. so every time we visit a node we will mark it as 1 in "visited" array.
And in both the bfs and dfs cases we will just travese the tree first and add the nodes to a data structure it is the data structure output that will be different
a stack will give a first in last out and a queue will give a first in first out.

Please comment below for any doubts

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.