Day 1
Date Completed: March 2, 2023 3:20 AM
Date Started: March 1, 2023 11:00 PM
Difficulty: ⭐⭐⭐
Done: Yes
Languages: Java
Related to Progress (Days): 1%
Topic: Detect cycle in an undirected graph using BFS, Dijkstra Algorithm
What I Learned Today
Code Implementation Of Dijkstra's Algorithm
Detect cycle in an undirected graph using BFS
Quick Links
Key Concepts
Dijkstra's Algorithm
Step 1: All nodes should be marked as unvisited.
Step 2: All the nodes must be initialized with the "infinite" (a big number) distance. The starting node must be initialized with zero.
Step 3: Mark starting node as the current node.
Step 4: From the current node, analyze all of its neighbors that are not visited yet, and compute their distances by adding the weight of the edge, which establishes the connection between the current node and neighbor node to the current distance of the current node.
Step 5: Now, compare the recently computed distance with the distance allotted to the neighboring node, and treat it as the current distance of the neighboring node,
Step 6: After that, the surrounding neighbors of the current node, which has not been visited, are considered, and the current nodes are marked as visited.
Step 7: When the ending node is marked as visited, then the algorithm has done its job; otherwise,
Step 8: Pick the unvisited node which has been allotted the minimum distance and treat it as the new current node. After that, start again from step4.
Detect cycle in an undirected graph using BFS
To detect a cycle in an undirected graph using Breadth-First Search (BFS), we can follow the following algorithm:
Step 1: Create a visited array to keep track of visited vertices and initialize all vertices as not visited.
Step 2: Create a parent array to keep track of the parent of each vertex and initialize all parent values to -1.
Step 3: Create an empty queue for BFS.
Step 4: Pick any vertex as the starting vertex and mark it as visited and enqueue it.
Step 5: While the queue is not empty, dequeue a vertex from the queue and iterate through all its adjacent vertices.
Step 6: For each adjacent vertex, if it is not visited, mark it as visited, set its parent as the current vertex, and enqueue it.
Step 7: If an adjacent vertex is already visited and its parent is not the current vertex, then a cycle exists in the graph.
Step 8: Repeat steps 5 to 7 until the queue is empty.
If no cycle is detected, then the graph is acyclic.
Code Snippets
//Dijkstra's Algorithm
import java.util.ArrayList;
import java.util.PriorityQueue;
public class DijkstraAlgo {
static class Edge {
int src;
int dest;
int wt;
public Edge(int s, int d, int w){
this.src=s;
this.dest=d;
this.wt=w;
}
}
static void createGraph(ArrayList<Edge> graph[]){
for (int i=0; i< graph.length; i++){
graph[i]=new ArrayList<>();
}
graph[0].add(new Edge(0,1,2));
graph[0].add(new Edge(0,2,4));
graph[1].add(new Edge(1,3,7));
graph[1].add(new Edge(1,2,1));
graph[2].add(new Edge(2,4,3));
graph[3].add(new Edge(3,5,1));
graph[4].add(new Edge(4,3,2));
graph[4].add(new Edge(4,5,5));
}
static class Pair implements Comparable<Pair>{
int n;
int path;
public Pair(int n, int path){
this.n=n;
this.path=path;
}
@Override
public int compareTo(Pair p2){
return this.path - p2.path; //path based sorting for pairs
}
}
public static void dijkstra(ArrayList<Edge> graph[], int src){ // O(V+ElogV) -> Priority Queue
int dist[] = new int[graph.length];
for (int i=0; i< graph.length; i++){ //dis[i] -> src to i
if (i != src){
dist[i] = Integer.MAX_VALUE; //+infinity for neighbour of src
}
}
boolean[] vis = new boolean[graph.length];
PriorityQueue<Pair> pq = new PriorityQueue<>();
pq.add(new Pair(src,0));
//loop
while (!pq.isEmpty()){
Pair curr = pq.remove();
if (!vis[curr.n]){
vis[curr.n] = true;
//neighbours ke liye check karlo
for (int i=0; i< graph[curr.n].size(); i++){
Edge e = graph[curr.n].get(i);
int u = e.src;
int v = e.dest;
int wt = e.wt;
if (dist[u]+wt < dist[v]){
dist[v] = dist[u]+wt;
pq.add(new Pair(v,dist[v]));
}
}
}
}
for (int i =0; i< dist.length; i++){
System.out.print(dist[i]+" ");
}
System.out.println();
}
public static void main(String[] args) {
int V=6;
ArrayList<Edge> []graph = new ArrayList[V];
createGraph(graph);
int src = 0;
dijkstra(graph, src);
}
}
//Detect cycle in an undirected graph using BFS
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
public class GraphPractice {
static void addEdge(ArrayList<Integer> graph[], int u, int v) {
graph[u].add(v);
graph[v].add(u);
}
public static boolean detectCycleUtilBFS(ArrayList<Integer>[] graph, int curr, boolean[] visited, int V) {
int parent[] = new int[V];
Queue<Integer> q = new LinkedList<>();
visited[curr] = true;
q.add(curr);
while (!q.isEmpty()) {
int u = q.poll();
for (int i = 0; i < graph[u].size(); i++) {
int v = graph[u].get(i);
if (!visited[v]) {
visited[v] = true;
q.add(v);
parent[v] = u;
} else if (parent[u] != v) {
return true;
}
}
}
return false;
}
public static boolean detectCycleBFS(ArrayList<Integer>[] graph) {
boolean[] visited = new boolean[graph.length];
Arrays.fill(visited, false); // we are marking false in all
for (int i = 0; i < graph.length; i++) {
if (!visited[i]) {
if (detectCycleUtilBFS(graph, i, visited, graph.length)) {
return true;
//Cycle exists in one of the parts
}
}
}
return false;
}
public static void main(String[] args) {
int V = 4;
ArrayList<Integer> graph[] = new ArrayList[V];
for (int i = 0; i < 4; i++) graph[i] = new ArrayList<Integer>();
addEdge(graph, 0, 1);
addEdge(graph, 1, 2);
addEdge(graph, 2, 0);
addEdge(graph, 2, 3);
System.out.println(detectCycleBFS(graph));
}
}