Breadth-First Search :
BFS explores graphs level by level, starting from a source node and visiting all its neighbors before moving deeper. It is ideal for finding the shortest path in unweighted graphs and for scenarios like social network analysis.
*Depth-First Search (DFS):
DFS dives deep into the graph, exploring as far as possible along a branch before backtracking. It excels in applications like topological sorting, cycle detection, and solving puzzles like mazes.
*Applications:
Both BFS and DFS are essential in problem-solving, offering complementary strengths based on traversal needs and graph structures.
EFFICIENCIES
*Time Complexity:
O(V + E), where V is the number of vertices and E is the number of edges. This is because BFS visits every vertex once and explores all edges in the graph.
*Space Complexity:
O(V), because BFS stores each vertex in a queue, and in the worst case, all vertices may be in the queue at once.
*Use Case: BFS is optimal for finding the shortest path in an unweighted graph and exploring all nodes level by level.
Time Complexity:
O(V + E), for similar reasons as BFS. DFS also visits each vertex once and explores each edge once.
Space Complexity:
O(V) in the worst case (for storing the recursion stack or an explicit stack). If the graph is deep or the tree is highly unbalanced, the space complexity can grow significantly.
Use Case: DFS is useful for topological sorting, pathfinding in a maze, or searching for connected components in a graph.
BFS CODE IMPLEMENTATION
#include <iostream>
using namespace std;
void bfs(int m[10][10], int v, int source) {
int queue[20];
int front = 0, rear = 0, u, i;
int visited[10];
// Initialize visited array
for (i = 0; i < v; i++)
visited[i] = 0;
queue[rear] = source; // Start with the source node
visited[source] = 1;
cout << "The BFS Traversal is... \n";
while (front <= rear) {
u = queue[front];
cout << u << "\t";
front++;
// Traverse all adjacent nodes of u
for (i = 0; i < v; i++) {
if (m[u][i] == 1 && visited[i] == 0) {
visited[i] = 1;
rear++;
queue[rear] = i;
}
}
}
}
int main() {
int v = 5;
int m[10][10] = {
{0,1,1,0,0},
{1,0,0,1,1},
{1,0,0,0,1},
{0,1,0,0,0},
{0,1,1,0,0}
};
int source;
cout << "Enter the source vertex: ";
cin >> source;
bfs(m, v, source)
return 0;
}
*Output:
Enter the source vertex: 3
The BFS Traversal is...
3 1 0 4 2
Execution Time: 3.191 seconds
*DFS Code Implementation
#include <iostream>
using namespace std;
int v = 5;
int m[10][10] = {
{0,1,1,0,0},
{1,0,0,1,1},
{1,0,0,0,1},
{0,1,0,0,0},
{0,1,1,0,0}
};
int visited[10];
void dfs(int m[10][10], int v, int source) {
visited[source] = 1;
for (int i = 0; i < v; i++) {
if (m[source][i] == 1 && visited[i] == 0) {
cout << i << "\t";
dfs(m, v, i); // Recursively explore the next node
}
}
}
int main() {
int source;
// Initialize visited array
for (int i = 0; i < v; i++)
visited[i] = 0;
cout << "Enter the source vertex: ";
cin >> source;
cout << "The DFS Traversal is... \n";
cout << source << "\t";
dfs(m, v, source);
return 0;
}
*Output:
Enter the source vertex: 3
The DFS Traversal is...
3 1 0 2 4
*BFS Applications:
Web Crawlers: BFS is used by web crawlers to visit and index web pages layer by layer, starting from the homepage and exploring linked pages step-by-step.
Social Networks: BFS helps in social network analysis by finding the shortest path between users, such as the degree of separation between two people.
*DFS Applications:
Solving Puzzles: DFS is used to solve problems like mazes, where it explores one path thoroughly before backtracking and trying other possibilities.
Task Scheduling: DFS aids in scheduling tasks with dependencies, such as topological sorting, where tasks must be completed in a specific order.
*Key Takeaways:
BFS: Ideal for problems requiring level-by-level exploration or finding the shortest path (e.g., navigation systems, network analysis). It is particularly effective when you need to explore each layer of the graph before moving deeper.
DFS: Best for deep exploration where you want to explore all possibilities along a path before backtracking (e.g., solving mazes, cycle detection). DFS is well-suited for problems that require exhaustive searches.
Time Complexity: Both BFS and DFS have a time complexity of O(V + E), where V is the number of vertices and E is the number of edges in the graph. However, they differ in space complexity and implementation. BFS uses a queue to track nodes, while DFS uses a stack.