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](https://he-s3.s3.amazonaws.com/media/uploads/9fa1119.jpg)
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](https://he-s3.s3.amazonaws.com/media/uploads/0dbec9e.jpg)
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