Welcome to our session on Graph Algorithms Implementation. A large proportion of real-world problems, from social networking to routing applications, can be represented by graphs. Understanding and implementing graph algorithms is thus a key skill to have in your programming toolkit. In this lesson, we introduce and explore one of the most fundamental graph traversal algorithms — the Breadth-First Search (BFS
).
Let's take a sneak peek at the BFS
algorithm. Given a graph and a starting vertex, BFS
systematically explores the edges of the graph to "visit" each reachable vertex. It does this by managing a queue of vertices yet to be explored and consistently visiting all vertices adjacent to the current one before moving on. BFS
is particularly efficient because it can find the shortest distance between the starting vertex and all other vertices in a graph.
Here's a sample BFS
algorithm implemented in C# that we will dissect in depth and master:
C#1using System; 2using System.Collections.Generic; 3 4public class Graph 5{ 6 // Dictionary to store adjacency list of the graph 7 private Dictionary<int, List<int>> adjList = new Dictionary<int, List<int>>(); 8 9 public void AddEdge(int src, int dest) 10 { 11 if (!adjList.ContainsKey(src)) 12 { 13 adjList[src] = new List<int>(); 14 } 15 if (!adjList.ContainsKey(dest)) 16 { 17 adjList[dest] = new List<int>(); 18 } 19 adjList[src].Add(dest); 20 adjList[dest].Add(src); 21 } 22 23 // Method to perform Breadth-First Search from a given starting vertex 24 public List<int> Bfs(int start) 25 { 26 var visited = new HashSet<int>(); 27 var queue = new Queue<int>(); 28 var result = new List<int>(); 29 30 queue.Enqueue(start); // Start the BFS with the starting vertex 31 32 while (queue.Count > 0) 33 { 34 int node = queue.Dequeue(); // Remove the vertex at the front of the queue 35 if (!visited.Contains(node)) 36 { 37 visited.Add(node); 38 result.Add(node); 39 foreach (var neighbor in adjList[node]) 40 { 41 // Add unvisited neighbors to the queue 42 if (!visited.Contains(neighbor)) 43 { 44 queue.Enqueue(neighbor); 45 } 46 } 47 } 48 } 49 50 return result; 51 } 52 53 public static void Main(string[] args) 54 { 55 Graph graph = new Graph(); 56 // Create graph by adding edges between vertices 57 graph.AddEdge(0, 1); 58 graph.AddEdge(0, 2); 59 graph.AddEdge(1, 2); 60 graph.AddEdge(2, 0); // multi-edge between 0 and 2 61 graph.AddEdge(2, 3); 62 graph.AddEdge(3, 3); 63 64 Console.WriteLine("BFS traversal starting from node 2:"); 65 // Perform BFS starting from vertex 2 and print the result 66 Console.WriteLine(string.Join(", ", graph.Bfs(2))); 67 } 68}
As we delve into this session, we will understand the mechanics behind BFS
. Our study will include the concepts of traversal, the queue data structure's usefulness in BFS
, and how to handle the discovery and processing of nodes. Equipped with these fundamentals, we'll practice on a variety of problems calling for BFS
to perform node-level searches or find connected components in a graph. Let's dive in and uncover the power of graph algorithms!