Usng Java Eclipse l Implement the following: 1) [Part One] Design an interface t
ID: 3706626 • Letter: U
Question
Usng Java Eclipse
l Implement the following:
1) [Part One] Design an interface that allows the user to provide all necessary information about nodes and edges; construct a graph based on the user input and then implement two items listed below.
· Display its adjacency matrix.
· Display its adjacency list.
[Part Two] Implement any one of the following four items.
· Run BFS on your graph and output all nodes in the order when they are visited. Use separate lines for different components during the graph traversal.
· Run DFS on your graph and output all nodes in the order when they are visited. Use separate lines for different components during the graph traversal.
· Output one topological ordering for your graph.
(Note: it requires the graph to be a DAG.)
· Output all strongly connected components for your graph.
(Note: it requires the graph to be a directed graph.)
Explanation / Answer
[Part one]
/* java program to represent graph as a adjacency matrix.
*/
import java.util.Scanner;
public class Graph_Adjacency_Matrix
{
private final int vertices;
private int[][] adjacency_matrix;
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++;
}
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();
}
}
...........Adajaceny List.........
import java.io.*;
import java.util.*;
class graph
{
private int numVertices;
private LinkedList<Integer> adjLists[];
graph(int vertices)
{
numVertices = vertices;
adjLists = new LinkedList[vertices];
for (int i = 0; i < vertices; i++)
adjLists[i] = new LinkedList();
}
void addEdge(int src, int dest)
{
adjLists[src].add(dest);
}
public static void main(String args[])
{
graph g = new graph(4);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 3);
}
}
[part two]
BFS Traversal.....
import java.util.InputMismatchException;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class BFS
{
private Queue<Integer> queue;
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 static void main(String... arg)
{
int number_no_nodes, source;
Scanner scanner = null;
try
{
System.out.println("Enter the number of nodes in the graph");
scanner = new Scanner(System.in);
number_no_nodes = scanner.nextInt();
int adjacency_matrix[][] = new int[number_no_nodes + 1][number_no_nodes + 1];
System.out.println("Enter the adjacency matrix");
for (int i = 1; i <= number_no_nodes; i++)
for (int j = 1; j <= number_no_nodes; j++)
adjacency_matrix[i][j] = scanner.nextInt();
System.out.println("enter the source for the graph");
source = scanner.nextInt();
System.out.println("The BFS traversal of the graph is ");
BFS bfs = new BFS();
bfs.bfs(adjacency_matrix, source);
} catch (InputMismatchException inputMismatch)
{
System.out.println("Wrong Input Format");
}
scanner.close();
}
}
....DFS Traversal....
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 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 static void main(String...arg)
{
int number_of_nodes, source;
Scanner scanner = null;
try
{
System.out.println("Enter the number of nodes in the graph");
scanner = new Scanner(System.in);
number_of_nodes = scanner.nextInt();
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);
}catch(InputMismatchException inputMismatch)
{
System.out.println("Wrong Input format");
}
scanner.close();
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.