ℹ️ Select 'Choose Exercise', or randomize 'Next Random Exercise' in selected language.

Choose Exercise:
Timer 00:00
WPM --
Score --
Acc --
Correct chars --

Graph Traversal: Breadth-First Search (BFS)

C#

Goal -- WPM

Ready
Exercise Algorithm Area
1using System;

2using System.Collections.Generic;

3

4public class GraphBFS

5{

6private readonly Dictionary<int, List<int>> adjacencyList;

7

8public GraphBFS(int vertices)

9{

10adjacencyList = new Dictionary<int, List<int>>(vertices);

11for (int i = 0; i < vertices; i++)

12{

13adjacencyList.Add(i, new List<int>());

14}

15}

16

17public void AddEdge(int source, int destination)

18{

19if (!adjacencyList.ContainsKey(source) || !adjacencyList.ContainsKey(destination))

20{

21throw new ArgumentException("Vertices must exist in the graph.");

22}

23adjacencyList[source].Add(destination);

24// For an undirected graph, uncomment the line below:

25// adjacencyList[destination].Add(source);

26}

27

28public List<int> PerformBFS(int startNode)

29{

30if (!adjacencyList.ContainsKey(startNode))

31{

32throw new ArgumentException("Start node does not exist in the graph.");

33}

34

35var visited = new HashSet<int>();

36var queue = new Queue<int>();

37var traversalOrder = new List<int>();

38

39// Start BFS from the given node

40queue.Enqueue(startNode);

41visited.Add(startNode);

42

43while (queue.Count > 0)

44{

45int currentNode = queue.Dequeue();

46traversalOrder.Add(currentNode);

47

48// Explore neighbors

49foreach (int neighbor in adjacencyList[currentNode])

50{

51if (!visited.Contains(neighbor))

52{

53visited.Add(neighbor);

54queue.Enqueue(neighbor);

55}

56}

57}

58

59// Handle disconnected components if necessary (optional: iterate through all nodes)

60// For this implementation, we only traverse reachable nodes from startNode.

61

62return traversalOrder;

63}

64

65// Example of how to handle disconnected components:

66public List<int> BFSForAllComponents()

67{

68var visited = new HashSet<int>();

69var traversalOrder = new List<int>();

70

71foreach (var node in adjacencyList.Keys)

72{

73if (!visited.Contains(node))

74{

75// Start a new BFS for an unvisited component

76var componentOrder = PerformBFS(node);

77traversalOrder.AddRange(componentOrder);

78// Mark all nodes in this component as visited

79foreach(var visitedNode in componentOrder)

80{

81visited.Add(visitedNode);

82}

83}

84}

85return traversalOrder;

86}

87}
Algorithm description viewbox

Graph Traversal: Breadth-First Search (BFS)

Algorithm description:

This C# code implements Breadth-First Search (BFS) for a graph represented by an adjacency list. BFS explores a graph level by level, starting from a given source node. It's widely used for finding the shortest path in unweighted graphs, network broadcasting, and web crawlers.

Algorithm explanation:

BFS uses a queue to manage nodes to visit and a set to track visited nodes. Starting from `startNode`, it enqueues the node, marks it as visited, and adds it to the traversal order. While the queue is not empty, it dequeues a node, processes it, and enqueues all its unvisited neighbors, marking them as visited. This ensures that nodes closer to the start node are visited first. The time complexity is O(V + E), where V is the number of vertices and E is the number of edges, as each vertex and edge is processed at most once. Space complexity is O(V) for the queue and visited set. The `BFSForAllComponents` method demonstrates how to handle disconnected graphs by iterating through all nodes and starting BFS if a node hasn't been visited yet.

Pseudocode:

Class `GraphBFS`:
  `adjacencyList` (Dictionary<int, List<int>>).

  Constructor(vertices):
    Initialize `adjacencyList` with empty lists for each vertex.

  Function `AddEdge(source, destination)`:
    Add `destination` to `adjacencyList[source]`.
    (Optional for undirected: Add `source` to `adjacencyList[destination]`)

  Function `PerformBFS(startNode)`:
    If `startNode` not in graph, throw error.
    Initialize `visited` set.
    Initialize `queue`.
    Initialize `traversalOrder` list.

    Enqueue `startNode` into `queue`.
    Add `startNode` to `visited`.

    While `queue` is not empty:
      `currentNode = Dequeue` from `queue`.
      Add `currentNode` to `traversalOrder`.

      For each `neighbor` in `adjacencyList[currentNode]`:
        If `neighbor` is not in `visited`:
          Add `neighbor` to `visited`.
          Enqueue `neighbor` into `queue`.

    Return `traversalOrder`.

  Function `BFSForAllComponents()`:
    Initialize `visited` set.
    Initialize `traversalOrder` list.
    For each `node` in `adjacencyList.Keys`:
      If `node` is not in `visited`:
        `componentOrder = PerformBFS(node)`.
        Add all elements from `componentOrder` to `traversalOrder`.
        Add all elements from `componentOrder` to `visited`.
    Return `traversalOrder`.