DFS AND BFS

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.

enter image description here 

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.

enter image description here 

My code:-

void bfs(int startVertex,ArrayList<Integer> graph[]){
    Queue<Integer> queue=new LinkedList<>();
    queue.add(startVertex);
    int visited[]=new int[graph.length];
    visited[startVertex]=1;
    while (!queue.isEmpty()){
        int currentVertex=queue.remove();
        for(int nextVertex:graph[currentVertex]){
            if(visited[nextVertex]==0){
                queue.add(nextVertex);
                visited[nextVertex]=1;
            }
        }
    }
}

Comments

Post a Comment

Popular posts from this blog

introduction to Graph

Image
Graph Algorithm Graphs are mathematical structures that represent pairwise relationships between objects.   There two things to represent graph. 1) Node: Nodes are entities whose relationships are expressed using edges. 2) Edge:  Edges are the components that are used to represent the relationships between various nodes in a graph. Types of graphs Graph representation You can represent a graph in many ways. The two most common ways of representing a graph is as follows: Adjacency matrix An adjacency matrix is a  VxV  binary matrix  A . Element  A i , j  is 1 if there is an edge from vertex i to vertex j else  A i , j  is 0. The adjacency matrix of the following graph is: i/j  :  1  2   3   4 1  : 0 - 1 - 0 - 1 2  : 1 - 0 - 1 - 0 3  : 0 - 1 - 0 - 1 4  : 1 - 0 - 1 - 0 The adjacency matrix of the following graph is: i/j :  1   2   3   4 1  : 0 - 1 - 0 - 0 2  : 0 - 0 - 0 - 1 3  : 1 - 0 - 0 - 1 4  : 0 - 1 - 0 - 0 Code:-
Read more

MST

Image
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;
Read more