Using java .Write a program to determine whether a given unweighted undirected graph G contains a cycle or not
The algorithm for verifying whether a graph contains a cycle or not.
import java.io.*;
import java.util.*;
class Graph
{
public LinkedList<Integer> matrix[];
public int V;
void edge(int v,int w){
matrix[v].add(w);
matrix[w].add(v);
}
Boolean cyclicCondition(int v, Boolean vis[], int
parent)
{
vis[v]=true;
Integer i;
Iterator<Integer> it =
matrix[v].iterator();
while (it.hasNext())
{
i =
it.next();
if
(!vis[i])
{
if (cyclicCondition(i, vis, v)) {
return true;
}
}
else if (i != parent) {
return true;
}
}
return false;
}
Graph(int v){
V = v;
matrix= new LinkedList[v];
for(int i=0; i<v; ++i){
matrix[i] = new
LinkedList();
}
}
Boolean isCyclic()
{
Boolean visited[] = new
Boolean[V];
for (int i = 0; i < V;
i++)
visited[i] =
false;
for (int u = 0;
u < V; u++) {
if (!visited[u]){
if (cyclicCondition(u,
visited, -1)){
return
true;
}
}
}
return false;
}
public static void main(String args[])
{
Graph g1 = new Graph(6);
g1.edge(3,4);
g1.edge(1,4);
g1.edge(4,5);
g1.edge(1,3);
g1.edge(4,2);
g1.edge(3,2);
if (g1.isCyclic()) {
System.out.println("cycle is present");
}
else{
System.out.println("no cycle");
}
}
}
Using java .Write a program to determine whether a given unweighted undirected graph G contains a...
Given an unweighted directed graph G, write a program that counts and prints all simple paths from a given ‘s’ to a given ‘d’. Assume the graph G is represented using adjacent matrix. Using Java Language
Use Java if possible please:
Write an algorithm using pseudo code to determine if an undirected graph has any cycle. Analyze the complexity of your algorithm. Write an algorithm using pseudo code to determine if an undirected graph is connected or not. Analyze the complexity of your algorithm. (i) (ii)
Let G = (V;E) be an undirected and unweighted graph. Let S be a subset of the vertices. The graph induced on S, denoted G[S] is a graph that has vertex set S and an edge between two vertices u, v that is an element of S provided that {u,v} is an edge of G. A subset K of V is called a killer set of G if the deletion of K kills all the edges of G, that is...
3. Graph Connected Components (25 pts) You are given an undirected, unweighted graph that may be disconnected i.e. some vertices may not be reachable from other vertices. Every group of mutually reachable vertices forms an island, called a con- nected component. There is no path between vertices in different connected components. If a graph is not disconnected, then its vertices are in a single connected component, which is the entire graph itself. Implement a method using depth-first search that will...
Problem 3: Suppose you are given an undirected graph G and a specified starting node s and ending node t. The HaMILTONIAN PATH problem asks whether G contains a path beginning at s and ending at t that touches every node exactly once. The HAMILTONIAN CYCLE problem asks whether con- tains a cycle that touches every node exactly once (cycles don't have starting or ending points, so s and t are not used here) Assume that HaMIlTonian CYCLe is NP-Complete....
IN JAVA Given is a weighted undirected graph G = (V, E) with positive weights and a subset of its edges F E. ⊆ E. An F-containing spanning tree of G is a spanning tree that contains all edges from F (there might be other edges as well). Give an algorithm that finds the cost of the minimum-cost F-containing spanning tree of G and runs in time O(m log n) or O(n2). Input: The first line of the text file...
Let G = (V, E) be a weighted undirected connected graph that contains a cycle. Let k ∈ E be the edge with maximum weight among all edges in the cycle. Prove that G has a minimum spanning tree NOT including k.
Indicate whether the following is True or False. Consider a simple undirected graph G = (V, E), where |E| < |VI – 1. Then G has at least one cycle. True False
Consider an unweighted, undirected graph G = 〈V, E). The neighbourhood of a node u E V in the graph is the set of all nodes that are adjacent (or directly connected) to v. Subsequently, we can define the neighbourhood degree of the node v as the sum of the degrees of all its neighbours (those nodes that are directly connects to v) (a) Design an algorithm that returns a list containing the neighbourhood degree for each node v V,...
This question needs to be done using pseudocode (not any
particular programming language). Thanks
Consider an unweighted, undirected graph G = 〈V, E). The neighbourhood of a node u E V in the graph is the set of all nodes that are adjacent (or directly connected) to v. Subsequently, we can define the neighbourhood degree of the node v as the sum of the degrees of all its neighbours (those nodes that are directly connects to v) (a) Design an...