Graph Traversal - potatoscript/dsa GitHub Wiki

🧩 What is Graph Traversal?

Graph traversal involves visiting all the nodes and edges of a graph. There are two common approaches to traversal:

DFS (Depth-First Search): This method explores as deeply as possible along one branch before backtracking and exploring other branches.
BFS (Breadth-First Search): This method explores all nodes at the present depth level before moving on to the nodes at the next depth level.

🧩 Depth-First Search (DFS) – Exploring Deeply

DFS is like going down a maze: you start at a point, take the first path you find, and keep going until you reach a dead end. Once you hit a dead end, you backtrack and try a different path.

Steps of DFS

Start at the root node (or any node in the graph).
Visit the node.
Visit all the unvisited adjacent nodes by exploring as far as possible down each path before backtracking.
Repeat the process until all nodes are visited.

DFS Example

Consider the following graph:

       A
      / \
     B   C
    / \   \
   D   E   F

DFS Traversal: We start at node A, then go to B, then to D. After reaching D (a dead end), we backtrack to B and visit E. Once we finish all nodes connected to B, we backtrack to A and visit C, and finally, we visit F.

DFS Traversal: A → B → D → E → C → F

C# Code for DFS

using System;
using System.Collections.Generic;

public class GraphNode
{
    public string Name;
    public List<GraphNode> Neighbors;

    public GraphNode(string name)
    {
        Name = name;
        Neighbors = new List<GraphNode>();
    }

    public void AddEdge(GraphNode node)
    {
        Neighbors.Add(node);
    }
}

public class GraphTraversal
{
    public void DFS(GraphNode node, HashSet<GraphNode> visited)
    {
        if (node == null || visited.Contains(node)) return;

        // Visit the node
        Console.Write(node.Name + " ");
        visited.Add(node);

        // Recursively visit all neighbors
        foreach (var neighbor in node.Neighbors)
        {
            DFS(neighbor, visited);
        }
    }
}

public class Program
{
    public static void Main()
    {
        // Create graph nodes
        var A = new GraphNode("A");
        var B = new GraphNode("B");
        var C = new GraphNode("C");
        var D = new GraphNode("D");
        var E = new GraphNode("E");
        var F = new GraphNode("F");

        // Add edges
        A.AddEdge(B);
        A.AddEdge(C);
        B.AddEdge(D);
        B.AddEdge(E);
        C.AddEdge(F);

        // Create a graph traversal object
        var graphTraversal = new GraphTraversal();

        // Perform DFS
        var visited = new HashSet<GraphNode>();
        graphTraversal.DFS(A, visited);
    }
}

DFS Time Complexity

Time Complexity: O(V + E)
- V is the number of vertices (nodes).
- E is the number of edges.

DFS visits each vertex once and each edge once, making it O(V + E).

🧩 Breadth-First Search (BFS) – Exploring Level by Level

BFS is like exploring a maze level by level. You first explore all the nodes that are closest to the starting point, then move to the next level and explore all those nodes, and so on.

Steps of BFS

Start at the root node (or any node in the graph).
Visit the node.
Explore all the neighboring nodes at the current depth level.
Move to the next level and repeat the process until all nodes are visited.

BFS Example

Consider the following graph:

       A
      / \
     B   C
    / \   \
   D   E   F

BFS Traversal: We start at node A, then visit nodes B and C (level 1). After that, we visit nodes D, E, and F (level 2).

BFS Traversal: A → B → C → D → E → F

C# Code for BFS

using System;
using System.Collections.Generic;

public class GraphNode
{
    public string Name;
    public List<GraphNode> Neighbors;

    public GraphNode(string name)
    {
        Name = name;
        Neighbors = new List<GraphNode>();
    }

    public void AddEdge(GraphNode node)
    {
        Neighbors.Add(node);
    }
}

public class GraphTraversal
{
    public void BFS(GraphNode startNode)
    {
        if (startNode == null) return;

        Queue<GraphNode> queue = new Queue<GraphNode>();
        HashSet<GraphNode> visited = new HashSet<GraphNode>();

        // Start with the root node
        queue.Enqueue(startNode);
        visited.Add(startNode);

        while (queue.Count > 0)
        {
            var currentNode = queue.Dequeue();
            Console.Write(currentNode.Name + " ");

            // Enqueue all unvisited neighbors
            foreach (var neighbor in currentNode.Neighbors)
            {
                if (!visited.Contains(neighbor))
                {
                    queue.Enqueue(neighbor);
                    visited.Add(neighbor);
                }
            }
        }
    }
}

public class Program
{
    public static void Main()
    {
        // Create graph nodes
        var A = new GraphNode("A");
        var B = new GraphNode("B");
        var C = new GraphNode("C");
        var D = new GraphNode("D");
        var E = new GraphNode("E");
        var F = new GraphNode("F");

        // Add edges
        A.AddEdge(B);
        A.AddEdge(C);
        B.AddEdge(D);
        B.AddEdge(E);
        C.AddEdge(F);

        // Create a graph traversal object
        var graphTraversal = new GraphTraversal();

        // Perform BFS
        graphTraversal.BFS(A);
    }
}

BFS Time Complexity

Time Complexity: O(V + E)
- V is the number of vertices (nodes).
- E is the number of edges.

BFS visits each vertex once and each edge once, making it O(V + E).

🧩 BFS vs DFS

Let’s compare BFS and DFS:

Feature	BFS	DFS
Traversal Pattern	Level by level (breadth-first)	Deeply along each branch (depth-first)
Data Structure Used	Queue (FIFO)	Stack (LIFO) or Recursion
Memory Complexity	O(V) (due to the queue)	O(V) (due to the recursion stack)
Use Case	Shortest path, network traversal	Solving puzzles, pathfinding, topological sorting
Time Complexity	O(V + E)	O(V + E)

🧩 Real-World Applications

DFS:
- Solving puzzles like mazes.
- Topological sorting in directed acyclic graphs (DAGs).
- Cycle detection in graphs.
BFS:
- Finding the shortest path in an unweighted graph (e.g., Google Maps).
- Web crawlers to discover websites.
- Social networks to find all connections within a certain number of degrees.