Question & Answer: Create a Java class that implements an undirected graph. The class must have the following functions:…..

UndirGraph.java

import java.io.*;
import java.util.*;
import java.util.LinkedList;

class UndirGraph
{
private int Vertices;
private LinkedList<Integer> adjacent[];
int timing = 0;
static final int NM = -1;
UndirGraph(int vertex)
{
Vertices = vertex;
adjacent = new LinkedList[vertex];
for (int uu=0; uu<vertex; ++uu)
adjacent[uu] = new LinkedList();
}

// Function to add edges into the graph
void addingEdges(int vertex, int nv)
{
adjacent[vertex].add(nv); // Add nv to vertex’s list.
adjacent[nv].add(vertex); //Add vertex to nv’s list
}

// A recursive function that finds and prints bridges
// using DFS traversal
// nvv –> The vertex to be visiting next
// visiting[] –> keeps tract of visiting vertices
// desco[] –> Stores discovery times of visiting vertices
// parent[] –> Stores roots vertices in DFS tree
void bridgingUtility(int nvv, boolean visiting[], int desco[],
int lo[], int roots[])
{

// Count of childs in DFS Tree
int childs = 0;

// Mark the current node as visiting
visiting[nvv] = true;

// Initialize discovery timing and lo value
desco[nvv] = lo[nvv] = ++timing;

// Go through all vertices aadjacent to this
Iterator<Integer> uu = adjacent[nvv].iterator();
while (uu.hasNext())
{
int vertex = uu.next(); // vertex is current adjacent of nvv
if (!visiting[vertex])
{
roots[vertex] = nvv;
bridgingUtility(vertex, visiting, desco, lo, roots);

// Check if the subtree rooted with vertex has a
// connection to one of the ancestors of nvv
lo[nvv] = Math.min(lo[nvv], lo[vertex]);

// If the lowest vertex reachable from the subtree
// under vertex is below nvv in DFS tree, then nvv-vertex is
// a graphBridge
if (lo[vertex] > desco[nvv])
System.out.println(nvv+” “+vertex);
}

// Update lo value of nvv for roots function calls.
else if (vertex != roots[nvv])
lo[nvv] = Math.min(lo[nvv], desco[vertex]);
}
}

// DFS based function to find all bridges. This is the recursive
// function bridgingUtility()
void graphBridge()
{
// Mark all the vertices as not visiting
boolean visiting[] = new boolean[Vertices];
int desco[] = new int[Vertices];
int lo[] = new int[Vertices];
int roots[] = new int[Vertices];

// Initialize roots and visiting, and ap(articulation point)
// arrays
for (int uu = 0; uu < Vertices; uu++)
{
roots[uu] = NM;
visiting[uu] = false;
}

// Calling recursive helper function to find the Bridges
// in DFS tree rooted with vertex ‘uu’
for (int uu = 0; uu < Vertices; uu++)
if (visiting[uu] == false)
bridgingUtility(uu, visiting, desco, lo, roots);
}

public static void main(String args[])
{
System.out.println(“Bridges in first graph “);
UndirGraph ug = new UndirGraph(5);
ug.addingEdges(1, 0);
ug.addingEdges(0, 2);
ug.addingEdges(2, 1);
ug.addingEdges(0, 3);
ug.addingEdges(3, 4);
ug.graphBridge();
System.out.println();

System.out.println(“Bridges in Second graph”);
UndirGraph ug1 = new UndirGraph(4);
ug1.addingEdges(0, 1);
ug1.addingEdges(1, 2);
ug1.addingEdges(2, 3);
ug1.graphBridge();
System.out.println();

System.out.println(“Bridges in Third graph “);
UndirGraph ug2 = new UndirGraph(7);
ug2.addingEdges(0, 1);
ug2.addingEdges(1, 2);
ug2.addingEdges(2, 0);
ug2.addingEdges(1, 3);
ug2.addingEdges(1, 4);
ug2.addingEdges(1, 6);
ug2.addingEdges(3, 5);
ug2.addingEdges(4, 5);
ug2.graphBridge();
}
}