import java.util.*;
class Pair<Key, Value>{
public Key first;
public Value second;
public Pair(Key first, Value second)
{
this.first=first;
this.second=second;
}
}
public class Main
{
public static void main(String[] args) {
System.out.println("Hello World");
ArrayList<Integer> arr = new ArrayList<>();
HashMap<Integer, ArrayList<Integer>> adj = makeAdjList(10,arr);
addEdge(0,1,adj);
addEdge(0,2,adj);
addEdge(1,3,adj);
addEdge(2,3,adj);
addEdge(0,2,adj);
addEdge(3,4,adj);
addEdge(3,5,adj);
addEdge(4,6,adj);
addEdge(4,7,adj);
addEdge(5,8,adj);
addEdge(5,9,adj);
addEdge(6,10,adj);
addEdge(7,10,adj);
addEdge(8,10,adj);
addEdge(9,10,adj);
System.out.println(adj);
bfs(0,adj);
System.out.println("Given graph contains cycle or not: true/false ?");
System.out.println(isCycle(10,adj));
}
// Make adjList
public static HashMap<Integer, ArrayList<Integer>> makeAdjList(int V, ArrayList<Integer> arr) {
HashMap<Integer, ArrayList<Integer>> adj = new HashMap<>();
for(int i=0;i<V+1;i++)
{
adj.put(i,new ArrayList<Integer>()) ;
}
return adj;
}
// Add Edge
public static void addEdge(int src, int dest, HashMap<Integer, ArrayList<Integer>> adjList)
{
adjList.get(src).add(dest);
adjList.get(dest).add(src);
}
// BFS traversal
public static void bfs(int start, HashMap<Integer, ArrayList<Integer>> adjList)
{
ArrayList<Integer> ans = new ArrayList<>();
int V = adjList.size();
boolean vis[] = new boolean[V];
Arrays.fill(vis,false);
Queue<Integer> q = new LinkedList<>();
q.add(0);
vis[0]=true;
while(!q.isEmpty())
{
int node=q.poll();
ans.add(node);
for(int it: adjList.get(node))
{
if(vis[it]==false)
{
vis[it]=true;
q.add(it);
}
}
}
System.out.println(ans);
}
// Cycle detection in a graph via bfs traversal
public static boolean checkCycle(int src, boolean vis[], int V, HashMap<Integer, ArrayList<Integer>> adjList)
{
//boolean vis[] = new boolean[V+1];
//Arrays.fill(vis,false);
Queue<Pair<Integer,Integer>> q = new LinkedList<>();
q.add(new Pair(src,-1));
vis[src]=true;
while(!q.isEmpty())
{
int node=q.peek().first;
int parent=q.peek().second;
q.poll();
for(int it: adjList.get(node))
{
if(vis[it]==false)
{
vis[it]=true;
q.add(new Pair(it,node));
}
else if(parent!=it) return true;
}
}
return false;
}
// Main cycle detection function using above
public static boolean isCycle(int V, HashMap<Integer, ArrayList<Integer>> adjList)
{
boolean vis[] = new boolean[V+1];
Arrays.fill(vis,false);
for(int i=0;i<V;i++)
{
if(vis[i]==false)
{
if(checkCycle(i,vis,V,adjList)) return true;
}
}
return false;
}
}
No comments:
Post a Comment