Can you write the code using java language and also put the code to copy and any
ID: 3573281 • Letter: C
Question
Can you write the code using java language and also put the code to copy and any other files, please.
Hints:
1.Use an undirected graph.
2.Find an unmarked vertex and find and mark all vertices reachable from that vertex. Count this as #1.
3.Then find the next unmarked vertex and repeat, incrementing the count. Repeat until all vertices has been marked.
(Can you write the code using JAVA language, please? Thank you)
35. Informally, a connected component of a graph is a subset of the vertices of the graph such that all of the vertices in the subset are connected to each other by a path. For example, the following graph consists of three connected components O. Create a numComponents method that returns the number of connected compo- nents that exist in a graph. You can put your new method in our useGraph class and use it to test your code.Explanation / Answer
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
class CCGraph {
static final int MAXV = 100;
static final int MAXDEGREE = 50;
public int edges[][] = new int[MAXV + 1][MAXDEGREE];
public int degree[] = new int[MAXV + 1];
public int nvertices;
public int nedges;
CCGraph() {
nvertices = nedges = 0;
for (int i = 1; i <= MAXV; i++)
degree[i] = 0;
}
void read_CCGraph(boolean directed) {
int x, y;
Scanner sc = new Scanner(System.in);
System.out.println("Enter the number of vertices: ");
nvertices = sc.nextInt();
System.out.println("Enter the number of edges: ");
int m = sc.nextInt();
// vertices starts from 1
System.out.println("Enter the edges: <from> <to>");
for (int i = 1; i <= m; i++) {
x = sc.nextInt();
y = sc.nextInt();
insert_edge(x, y, directed);
}
sc.close();
}
void insert_edge(int x, int y, boolean directed) {
if (degree[x] > MAXDEGREE)
System.out.printf("Warning: insertion (%d, %d) exceeds max degree ", x, y);
edges[x][degree[x]] = y;
degree[x]++;
if (!directed)
insert_edge(y, x, true);
else
nedges++;
}
void print_CCGraph() {
for (int i = 1; i <= nvertices; i++) {
System.out.printf("%d: ", i);
for (int j = degree[i] - 1; j >= 0; j--)
System.out.printf(" %d", edges[i][j]);
System.out.printf(" ");
}
}
}
public class ConnectedComponents {
static final int MAXV = 100;
static boolean processed[] = new boolean[MAXV];
static boolean discovered[] = new boolean[MAXV];
static int parent[] = new int[MAXV];
static void bfs(CCGraph g, int start) {
Queue<Integer> q = new LinkedList<Integer>();
int i, v;
q.offer(start);
// marking edge as reached if it can be reached from a vertex
//push the vertex to queue and mark all reachable vertices from this vertex and so on until all vertices are covered for given vertex
discovered[start] = true;
while (!q.isEmpty()) {
v = q.remove();
processed[v] = true;
for (i = g.degree[v] - 1; i >= 0; i--) {
if (!discovered[g.edges[v][i]]) {
q.offer(g.edges[v][i]);
discovered[g.edges[v][i]] = true;
parent[g.edges[v][i]] = v;
}
}
}
}
static void initialize_search(CCGraph g) {
for (int i = 1; i <= g.nvertices; i++) {
processed[i] = discovered[i] = false;
parent[i] = -1;
}
}
static int connected_components(CCGraph g) {
int components = 0;
initialize_search(g);
for (int i = 1; i <= g.nvertices; i++) {
if (!discovered[i]) {
// every time a vertex still not reached is discovered increase
// components by 1
components++;
// and mark all vertices reachable from here as reachable
bfs(g, i);
}
}
return components;
}
static public void main(String[] args) {
CCGraph g = new CCGraph();
// to take input from user
g.read_CCGraph(false);
System.out.println("Number of components : "+connected_components(g));
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.