Graph algorithm

Minimum Spanning Tree What is spanning tree? Graph is weighted undirected and find a tree which has lowest weights. Kruskal’s Algorithm 1. Sort edges of graph with their weights. 2. Take edge and check whether it makes cycle or not. 3. If it doesn't make cycle than take this edge in MST. 4. else not take this edge in cycle. 5. apply 2,3,4 until all edges are taken. For checking adding edge makes cycle or not we make DFS( see my previous post) but it takes O(V+E) time it is expensive, so use DSU. DSU algorithm:- Below  example are explain algorithm. 1. first declare Arr[i]=i. 2.  make size[i]=i. 3.  4. Connect to 2 to 0 because size[0]> size[1]. My DSU code:- class DSU { int par [], size [], connectedComponent ; DSU( int n) { par = new int [n]; size = new int [n]; for ( int i = 0 ; i < n; i++) { size [i] = 1 ; par [i] = i; } connectedComponent = n;

Depth First Search The DFS algorithm works as follows: 1. Take random node of graph and put it on stack. 2. Pop top element of stack and set true in visited array of that index of vertex. 3. Take all adjacent node to that node and put all to stack. 4. Repeating 2 , 3 until stack is empty.   My code:- void dfs( int currentVertex, int visited[],ArrayList<Integer> graph[]){     visited[currentVertex]= 1 ;     for ( int nextVertex:graph[currentVertex]){         if (visited[nextVertex]== 0 ){             dfs(nextVertex,visited,graph);         }     } } Time complexity   O(V+E) , when implemented using an adjacency list. Breadth First Search The algorithm works as follows: 1    1. Take random node of graph and enqueue in queue. 2. dequeue first element of queue and set true in visited array of that index of vertex. 3. Take all adjacent node to that node and put all to stack. 4. Repeating 2 , 3 until queue is empty.