Create a class which constructs an adjacency matrix representation of a graph an

ID: 3686374 • Letter: C

Question

Create a class which constructs an adjacency matrix representation of a graph and performs a few graph operations.

Please answer in java code.

Write an Adjacency Matrix Graph class which has the following:

Two constructors:

Default which makes the matrix of a pre-defined size

Parameterized which takes in a non-negative or 0 size and creates an empty matrix

addEdge: this method returns nothing and takes in two string parameters and a weight. The two integer parameters correspond to the names of vertices and the weight is the weight of the newly created edge.

printDFS: This prints out the vertices name’s in depth first order. You can find the algorithm the presentation provided.

printBFS: This prints out the vertices name’s in breadth first order. Like above you can find the algorithm in the presentation.

printDFSForAll: For every vertex in the graph it will print its DFS

printBFSForAll: For every vertex in the graph it will print its BFS

Write another file that tests each of the methods for this graph.

Explanation / Answer

Sample code logic-

import java.util.Scanner;

public class Represent_Graph_Adjacency_Matrix
{
private final int vertices;
private int[][] adjacency_matrix;
public DFS()
{
stack = new Stack<Integer>();
}

public void dfs(int adjacency_matrix[][], int source)
{
int number_of_nodes = adjacency_matrix[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 (adjacency_matrix[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 adjacency_matrix[][], int source)
{
int number_of_nodes = adjacency_matrix[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 (adjacency_matrix[element][i] == 1 && visited[i] == 0)
{
queue.add(i);
visited[i] = 1;
}
i++;
}
}

}
}

public Graph_Adjacency_Matrix(int v)
{
vertices = v;
adjacency_matrix = new int[vertices + 1][vertices + 1];
}

public void makeEdge(int to, int from, int edge)
{
try
{
adjacency_matrix[to][from] = edge;
}
catch (ArrayIndexOutOfBoundsException index)
{
System.out.println("The vertices does not exists");
}
}

public int getEdge(int to, int from)
{
try
{
return adjacency_matrix[to][from];
}
catch (ArrayIndexOutOfBoundsException index)
{
System.out.println("The vertices does not exists");
}
return -1;
}

public static void main(String args[])
{
int v, e, count = 1, to = 0, from = 0;
Scanner sc = new Scanner(System.in);
Graph_Adjacency_Matrix graph;
try
{
System.out.println("Enter the number of vertices: ");
v = sc.nextInt();
System.out.println("Enter the number of edges: ");
e = sc.nextInt();

graph = new Graph_Adjacency_Matrix(v);

System.out.println("Enter the edges: <to> <from>");
while (count <= e)
{
to = sc.nextInt();
from = sc.nextInt();

graph.makeEdge(to, from, 1);
count++;
}
int adjacency_matrix[][] = new int[number_of_nodes + 1][number_of_nodes + 1];
   System.out.println("Enter the adjacency matrix");
   for (int i = 1; i <= number_of_nodes; i++)
   for (int j = 1; j <= number_of_nodes; j++)
adjacency_matrix[i][j] = scanner.nextInt();

   System.out.println("Enter the source for the graph");
source = scanner.nextInt();

System.out.println("The DFS Traversal for the graph is given by ");
DFS dfs = new DFS();
dfs.dfs(adjacency_matrix, source);
System.out.println("The BFS traversal of the graph is ");
BFS bfs = new BFS();
bfs.bfs(adjacency_matrix, source);

System.out.println("The adjacency matrix for the given graph is: ");
System.out.print(" ");
for (int i = 1; i <= v; i++)
System.out.print(i + " ");
System.out.println();

for (int i = 1; i <= v; i++)
{
System.out.print(i + " ");
for (int j = 1; j <= v; j++)
System.out.print(graph.getEdge(i, j) + " ");
System.out.println();
}

}
catch (Exception E)
{
System.out.println("Somthing went wrong");
}

sc.close();
}
}

note-by using the above code with required modifications it can help to answer the question.

Navigate

Create a class turned student that hat three member variables name - A swing tha

Create a class with a method that accepts a charge account number as it argument

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

Create a class which constructs an adjacency matrix representation of a graph an

Question

Explanation / Answer

Related Questions

Navigate