Write the java code needed to complete isUnicyclic() which determines if a graph

Question

Write the java code needed to complete isUnicyclic() which determines if a graph is unicyclical (if it contains exactly one (simple) cycle). The algorithm to solve this problem uses breadth first search to check if each vertices has been visited and returns true if cycles=1, false otherwise.

import java.util.ArrayList;
import java.util.Queue;
import java.util.LinkedList;

class Graph
{
  
ArrayList<ArrayList<Integer>> adjlist;

public Graph()
{
adjlist = new ArrayList<ArrayList<Integer>>();
}

public void SetNumVertices(int n)
{
adjlist.ensureCapacity(n);
for (int i = 0; i < n; ++i) {
adjlist.add(new ArrayList<Integer>());
}
}

public void AddEdge(int u, int v)
{
adjlist.get(u).add(v);
}

public boolean IsUnicyclic()
{

//THIS IS WHAT I NEED HELP WITH
return false;
}
}

Explanation / Answer

package com.sanjeev.chegg;

import java.util.Iterator;

import java.util.LinkedList;

public class Graph {

private int V; // No. of vertices

private LinkedList<Integer> adj[]; //Adjacency Lists

// Constructor

Graph(int v)

{

V = v;

adj = new LinkedList[v];

for (int i=0; i<v; ++i)

adj[i] = new LinkedList();

}

// Function to add an edge into the graph

void addEdge(int v,int w)

{

adj[v].add(w);

}

// prints BFS traversal from a given source s

void BFS(int s)

{

// Mark all the vertices as not visited(By default

// set as false)

boolean visited[] = new boolean[V];

// Create a queue for BFS

LinkedList<Integer> queue = new LinkedList<Integer>();

// Mark the current node as visited and enqueue it

visited[s]=true;

queue.add(s);

while (queue.size() != 0)

{

// Dequeue a vertex from queue and print it

s = queue.poll();

System.out.print(s+" ");

// Get all adjacent vertices of the dequeued vertex s

// If a adjacent has not been visited, then mark it

// visited and enqueue it

Iterator<Integer> i = adj[s].listIterator();

while (i.hasNext())

{

int n = i.next();

if (!visited[n])

{

visited[n] = true;

queue.add(n);

}

}

}

}

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, 0);

g.addEdge(2, 3);

g.addEdge(3, 3);

System.out.println("Following is Breadth First Traversal "+

"(starting from vertex 2)");

g.BFS(2);

}

}

Note :

we start traversal from vertex 2. When we come to vertex 0, we look for all adjacent vertices of it. 2 is also an adjacent vertex of 0. If we don’t mark visited vertices, then 2 will be processed again and it will become a non-terminating process. A Breadth First Traversal of the following graph is 2, 0, 3, 1.

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

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