Graph Traversal presentation | BFS and DFS

Graph traversal

1. Graph Traversal Introduction to Graphs, BFS, and DFS (C++ Implementation)

2. Introduction to Graphs • A Graph is a collection of nodes (vertices) and edges. • Types of Graphs: - Directed & Undirected - Weighted & Unweighted • Applications: Social Networks, Maps, Web Crawling, etc.

3. Graph Traversal • Traversal means visiting all the vertices of a graph. • Two main methods: - Breadth-First Search (BFS) - Depth-First Search (DFS)

4. Breadth-First Search (BFS) • BFS explores nodes level by level. • Uses a queue (FIFO) data structure. • Applications: - Shortest Path in unweighted graphs - Web Crawling

5. BFS Code in C++ #include <bits/stdc++.h> using namespace std; void BFS(int start, vector<vector<int>>& adj, int n) { vector<bool> visited(n, false); queue<int> q; visited[start] = true; q.push(start); while (!q.empty()) { int node = q.front(); q.pop(); cout << node << " "; for (int neigh : adj[node]) { if (!visited[neigh]) { visited[neigh] = true; q.push(neigh); } } } }

6. Depth-First Search (DFS) • DFS explores nodes as deep as possible before backtracking. • Uses recursion or stack. • Applications: - Detecting cycles - Topological Sorting - Path Finding

7. DFS Code in C++ #include <bits/stdc++.h> using namespace std; void DFSUtil(int node, vector<vector<int>>& adj, vector<bool>& visited) { visited[node] = true; cout << node << " "; for (int neigh : adj[node]) { if (!visited[neigh]) { DFSUtil(neigh, adj, visited); } } } void DFS(int start, vector<vector<int>>& adj, int n) { vector<bool> visited(n, false); DFSUtil(start, adj, visited); }