From Introduction to Java Programming 9th. ed.: Write a program that reads a gra
ID: 3555607 • Letter: F
Question
From Introduction to Java Programming 9th. ed.:
Write a program that reads a graph from a file and determines whether the graph is connected. The first line in the file contains a number that indicates the number of vertices (n). The vertices are labeled as 0, 1, . . . , n - 1. Each subsequent line, with the format u vl v2 ..., describes edges (u, vl), (u, v2), and so on. Figure 30.21 gives the examples of two files for their corresponding graphs. The vertices and edges of a graph can be stored in a file. Your program should prompt the user to enter the name of the file, then it should read data from the file, create an instance g of Un weighted Graph, invoke g. print Edges() to display all edges, and invoke dfs() to obtain an instance tree of Abstract Graph. Tree. If tree. Get Number Of Vertices Found is the same as the number of vertices in the graph, the graph is connected. Here is a sample run of the program: (Hint: Use new Un weighted Grapiest, number Of Vertices) to create a graph, where list contains a list of Abstract Graph. Edge objects. Use new Abstract Graph. Edge(u, v) to create an edge. Read the first line to get the number of vertices. Read each subsequent line into a string s and use. split("[\s + ]") to extract the vertices from the string and create edges from the vertices.)Explanation / Answer
Wow its s complicated question......anyway a part fof question came in my lab test the question is "to test whether undirected graph is connected" I did by using BFS. May be this helps...
import java.util.InputMismatchException;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class UndirectedConnectivityBFS
{
private Queue<Integer> queue;
public UndirectedConnectivityBFS()
{
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;
while (i <= number_of_nodes)
{
if (adjacency_matrix[element][i] == 1 && visited[i] == 0)
{
queue.add(i);
visited[i] = 1;
}
i++;
}
}
boolean connected = false;
for (int vertex = 1; vertex <= number_of_nodes; vertex++)
{
if (visited[vertex] == 1)
{
connected = true;
} else
{
connected = false;
break;
}
}
if (connected)
{
System.out.println("The graph is connected");
} else
{
System.out.println("The graph is disconnected");
}
}
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();
for (int i = 1; i <= number_of_nodes; i++)
{
for (int j = 1; j <= number_of_nodes; j++)
{
if (adjacency_matrix[i][j] == 1 && adjacency_matrix[j][i] == 0)
{
adjacency_matrix[j][i] = 1;
}
}
}
System.out.println("Enter the source for the graph");
source = scanner.nextInt();
UndirectedConnectivityBFS undirectedConnectivity= new UndirectedConnectivityBFS();
undirectedConnectivity.bfs(adjacency_matrix, source);
} catch (InputMismatchException inputMismatch)
{
System.out.println("Wrong Input Format");
}
scanner.close();
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.