2 - Graph Traversal Algorithms

Graph traversal is the process of visiting (checking and/or updating) each vertex in a graph. Traversal algorithms are fundamental to graph theory and form the basis for many more complex graph algorithms.

Depth-First Search (DFS)

Depth-First Search explores as far as possible along each branch before backtracking. It's like exploring a maze by following a path until you reach a dead end, then backtracking to the last junction and trying a different path.

How DFS Works

1. Start at a source vertex.
2. Mark the current vertex as visited.
3. Recursively visit all adjacent unvisited vertices.
4. Backtrack when all adjacent vertices have been visited.

Implementation

Recursive Implementation

/// <summary>
/// Represents a graph using an adjacency list representation and provides
/// methods for graph traversal using Depth-First Search (DFS).
/// </summary>
public class Graph
{
    private readonly int vertices; // Number of vertices
    private readonly List<int>[] adjacencyList;
    
    /// <summary>
    /// Initializes a new instance of the Graph class with the specified number of vertices.
    /// </summary>
    /// <param name="vertices">The number of vertices in the graph.</param>
    /// <exception cref="ArgumentOutOfRangeException">
    /// Thrown when the number of vertices is negative.
    /// </exception>
    public Graph(int vertices)
    {
        if (vertices < 0)
        {
            throw new ArgumentOutOfRangeException(nameof(vertices), "Number of vertices must be non-negative.");
        }
        
        this.vertices = vertices;
        adjacencyList = new List<int>[vertices];
        
        // Initialize each adjacency list
        for (int i = 0; i < vertices; i++)
        {
            adjacencyList[i] = new List<int>();
        }
    }
    
    /// <summary>
    /// Adds a directed edge from the source vertex to the destination vertex.
    /// </summary>
    /// <param name="source">The source vertex.</param>
    /// <param name="destination">The destination vertex.</param>
    /// <exception cref="ArgumentOutOfRangeException">
    /// Thrown when either source or destination is outside the valid range of vertices.
    /// </exception>
    public void AddEdge(int source, int destination)
    {
        ValidateVertex(source);
        ValidateVertex(destination);
        
        adjacencyList[source].Add(destination);
        
        // For undirected graph, uncomment the following line:
        // adjacencyList[destination].Add(source);
    }
    
    /// <summary>
    /// Performs a Depth-First Search (DFS) traversal starting from the specified vertex.
    /// </summary>
    /// <param name="startVertex">The vertex to start the traversal from.</param>
    /// <returns>A list of vertices in the order they were visited.</returns>
    /// <exception cref="ArgumentOutOfRangeException">
    /// Thrown when the start vertex is outside the valid range.
    /// </exception>
    public List<int> DFS(int startVertex)
    {
        ValidateVertex(startVertex);
        
        bool[] visited = new bool[vertices];
        List<int> result = new List<int>();
        
        // Call the recursive helper function
        DFSUtil(startVertex, visited, result);
        
        return result;
    }
    
    /// <summary>
    /// Helper method for DFS traversal that recursively visits all vertices
    /// reachable from the current vertex.
    /// </summary>
    /// <param name="vertex">The current vertex being visited.</param>
    /// <param name="visited">Array to track visited vertices.</param>
    /// <param name="result">List to store the traversal order.</param>
    private void DFSUtil(int vertex, bool[] visited, List<int> result)
    {
        // Mark the current vertex as visited and add it to the result
        visited[vertex] = true;
        result.Add(vertex);
        Console.WriteLine($"Visited vertex: {vertex}");
        
        // Recursively visit all adjacent vertices that haven't been visited yet
        foreach (int adjacentVertex in adjacencyList[vertex])
        {
            if (!visited[adjacentVertex])
            {
                DFSUtil(adjacentVertex, visited, result);
            }
        }
    }
    
    /// <summary>
    /// Performs a DFS traversal on the entire graph, including disconnected components.
    /// </summary>
    /// <returns>A list of vertices in the order they were visited.</returns>
    public List<int> DFSDisconnected()
    {
        bool[] visited = new bool[vertices];
        List<int> result = new List<int>();
        
        // Visit each vertex that hasn't been visited yet
        for (int i = 0; i < vertices; i++)
        {
            if (!visited[i])
            {
                DFSUtil(i, visited, result);
            }
        }
        
        return result;
    }
    
    /// <summary>
    /// Gets the number of vertices in the graph.
    /// </summary>
    public int VertexCount => vertices;
    
    /// <summary>
    /// Validates that a vertex index is within the valid range.
    /// </summary>
    /// <param name="vertex">The vertex index to validate.</param>
    /// <exception cref="ArgumentOutOfRangeException">
    /// Thrown when the vertex is outside the valid range.
    /// </exception>
    private void ValidateVertex(int vertex)
    {
        if (vertex < 0 || vertex >= vertices)
        {
            throw new ArgumentOutOfRangeException(nameof(vertex), 
                $"Vertex must be between 0 and {vertices - 1}.");
        }
    }
}

Iterative Implementation (Using Stack)

/// <summary>
/// Performs an iterative Depth-First Search (DFS) traversal starting from the specified vertex.
/// This implementation uses a stack instead of recursion.
/// </summary>
/// <param name="startVertex">The vertex to start the traversal from.</param>
/// <returns>A list of vertices in the order they were visited.</returns>
/// <exception cref="ArgumentOutOfRangeException">
/// Thrown when the start vertex is outside the valid range.
/// </exception>
public List<int> DFSIterative(int startVertex)
{
    ValidateVertex(startVertex);
    
    bool[] visited = new bool[vertices];
    List<int> result = new List<int>();
    Stack<int> stack = new Stack<int>();
    
    // Push the starting vertex
    stack.Push(startVertex);
    
    while (stack.Count > 0)
    {
        // Pop a vertex from the stack
        int currentVertex = stack.Pop();
        
        // If the vertex hasn't been visited yet
        if (!visited[currentVertex])
        {
            // Mark it as visited and add it to the result
            visited[currentVertex] = true;
            result.Add(currentVertex);
            Console.WriteLine($"Visited vertex: {currentVertex}");
            
            // Push all adjacent vertices in reverse order
            // (to match the recursive version's visit order)
            // We process them in reverse order because the stack is LIFO (Last In, First Out)
            for (int i = adjacencyList[currentVertex].Count - 1; i >= 0; i--)
            {
                int adjacentVertex = adjacencyList[currentVertex][i];
                
                if (!visited[adjacentVertex])
                {
                    stack.Push(adjacentVertex);
                }
            }
        }
    }
    
    return result;
}

/// <summary>
/// Performs an iterative DFS traversal on the entire graph, including disconnected components.
/// </summary>
/// <returns>A list of vertices in the order they were visited.</returns>
public List<int> DFSIterativeDisconnected()
{
    bool[] visited = new bool[vertices];
    List<int> result = new List<int>();
    
    // Visit each vertex that hasn't been visited yet
    for (int i = 0; i < vertices; i++)
    {
        if (!visited[i])
        {
            // Use a local stack for each component
            Stack<int> stack = new Stack<int>();
            stack.Push(i);
            
            while (stack.Count > 0)
            {
                int currentVertex = stack.Pop();
                
                if (!visited[currentVertex])
                {
                    visited[currentVertex] = true;
                    result.Add(currentVertex);
                    Console.WriteLine($"Visited vertex: {currentVertex}");
                    
                    for (int j = adjacencyList[currentVertex].Count - 1; j >= 0; j--)
                    {
                        int adjacentVertex = adjacencyList[currentVertex][j];
                        
                        if (!visited[adjacentVertex])
                        {
                            stack.Push(adjacentVertex);
                        }
                    }
                }
            }
        }
    }
    
    return result;
}

Applications of DFS

1. Topological Sorting: Finding a linear ordering of vertices in a directed acyclic graph.
2. Detecting Cycles: Determining if a graph contains cycles.
3. Finding Connected Components: Identifying subgraphs where any two vertices are connected.
4. Solving Puzzles: Many puzzles like mazes can be solved using DFS.
5. Finding Paths: Discovering paths between two vertices.
6. Strongly Connected Components: Finding strongly connected components in directed graphs.

Time and Space Complexity

• Time Complexity: O(V + E) where V is the number of vertices and E is the number of edges.
• Space Complexity: O(V) for the visited array and the recursion stack or explicit stack.

Breadth-First Search (BFS)

Breadth-First Search explores all neighbors at the present depth before moving to vertices at the next depth level. It's like exploring a maze by examining all possible paths one step away, then all paths two steps away, and so on.

How BFS Works

1. Start at a source vertex and mark it as visited.
2. Explore all unvisited neighbors of the current vertex.
3. For each of those neighbors, explore their unvisited neighbors, and so on.
4. Use a queue to keep track of the vertices to be explored.

Implementation

/// <summary>
/// Performs a Breadth-First Search (BFS) traversal starting from the specified vertex.
/// BFS explores all neighbors at the present depth before moving to vertices at the next depth level.
/// </summary>
/// <param name="startVertex">The vertex to start the traversal from.</param>
/// <returns>A list of vertices in the order they were visited.</returns>
/// <exception cref="ArgumentOutOfRangeException">
/// Thrown when the start vertex is outside the valid range.
/// </exception>
public List<int> BFS(int startVertex)
{
    ValidateVertex(startVertex);
    
    bool[] visited = new bool[vertices];
    List<int> result = new List<int>();
    Queue<int> queue = new Queue<int>();
    
    // Mark the starting vertex as visited and enqueue it
    visited[startVertex] = true;
    queue.Enqueue(startVertex);
    
    while (queue.Count > 0)
    {
        // Dequeue a vertex from the queue
        int currentVertex = queue.Dequeue();
        
        // Add it to the result and process it
        result.Add(currentVertex);
        Console.WriteLine($"Visited vertex: {currentVertex}");
        
        // Visit all adjacent vertices that haven't been visited yet
        foreach (int adjacentVertex in adjacencyList[currentVertex])
        {
            if (!visited[adjacentVertex])
            {
                // Mark as visited and enqueue
                visited[adjacentVertex] = true;
                queue.Enqueue(adjacentVertex);
            }
        }
    }
    
    return result;
}

/// <summary>
/// Performs a BFS traversal on the entire graph, including disconnected components.
/// </summary>
/// <returns>A list of vertices in the order they were visited.</returns>
public List<int> BFSDisconnected()
{
    bool[] visited = new bool[vertices];
    List<int> result = new List<int>();
    
    // Visit each vertex that hasn't been visited yet
    for (int i = 0; i < vertices; i++)
    {
        if (!visited[i])
        {
            // Use BFSUtil to visit all vertices reachable from i
            BFSUtil(i, visited, result);
        }
    }
    
    return result;
}

/// <summary>
/// Helper method for BFS traversal that visits all vertices reachable from the start vertex.
/// </summary>
/// <param name="startVertex">The vertex to start the traversal from.</param>
/// <param name="visited">Array to track visited vertices.</param>
/// <param name="result">List to store the traversal order.</param>
private void BFSUtil(int startVertex, bool[] visited, List<int> result)
{
    // Create a queue for BFS
    Queue<int> queue = new Queue<int>();
    
    // Mark the starting vertex as visited and enqueue it
    visited[startVertex] = true;
    queue.Enqueue(startVertex);
    
    while (queue.Count > 0)
    {
        // Dequeue a vertex from the queue
        int currentVertex = queue.Dequeue();
        
        // Add it to the result and process it
        result.Add(currentVertex);
        Console.WriteLine($"Visited vertex: {currentVertex}");
        
        // Visit all adjacent vertices that haven't been visited yet
        foreach (int adjacentVertex in adjacencyList[currentVertex])
        {
            if (!visited[adjacentVertex])
            {
                // Mark as visited and enqueue
                visited[adjacentVertex] = true;
                queue.Enqueue(adjacentVertex);
            }
        }
    }
}

/// <summary>
/// Finds the shortest path from the source vertex to the destination vertex using BFS.
/// This works only for unweighted graphs where each edge has the same weight.
/// </summary>
/// <param name="source">The source vertex.</param>
/// <param name="destination">The destination vertex.</param>
/// <returns>A list representing the shortest path from source to destination, or an empty list if no path exists.</returns>
/// <exception cref="ArgumentOutOfRangeException">
/// Thrown when either source or destination is outside the valid range.
/// </exception>
public List<int> ShortestPath(int source, int destination)
{
    ValidateVertex(source);
    ValidateVertex(destination);
    
    // If source and destination are the same, return a path with just the source
    if (source == destination)
    {
        return new List<int> { source };
    }
    
    // Array to store visited vertices
    bool[] visited = new bool[vertices];
    
    // Array to store the previous vertex in the shortest path
    int[] previous = new int[vertices];
    for (int i = 0; i < vertices; i++)
    {
        previous[i] = -1; // Initialize with -1 (no previous vertex)
    }
    
    // Queue for BFS
    Queue<int> queue = new Queue<int>();
    
    // Mark source as visited and enqueue it
    visited[source] = true;
    queue.Enqueue(source);
    
    // Flag to indicate if destination is found
    bool foundDestination = false;
    
    // BFS traversal
    while (queue.Count > 0 && !foundDestination)
    {
        int currentVertex = queue.Dequeue();
        
        // Check all adjacent vertices
        foreach (int adjacentVertex in adjacencyList[currentVertex])
        {
            if (!visited[adjacentVertex])
            {
                // Mark as visited and enqueue
                visited[adjacentVertex] = true;
                queue.Enqueue(adjacentVertex);
                
                // Set the previous vertex
                previous[adjacentVertex] = currentVertex;
                
                // If we've reached the destination, we can stop
                if (adjacentVertex == destination)
                {
                    foundDestination = true;
                    break;
                }
            }
        }
    }
    
    // If destination was not found, return an empty path
    if (!foundDestination)
    {
        return new List<int>();
    }
    
    // Reconstruct the path from destination to source
    List<int> path = new List<int>();
    for (int at = destination; at != -1; at = previous[at])
    {
        path.Add(at);
    }
    
    // Reverse the path to get it from source to destination
    path.Reverse();
    
    return path;
}

Applications of BFS

1. Shortest Path in Unweighted Graphs: Finding the shortest path between two vertices.
2. Web Crawlers: Exploring web pages by following links.
3. Social Networking: Finding people within a certain degree of connection.
4. Garbage Collection: Identifying and collecting unreachable objects.
5. Broadcasting in Networks: Efficiently broadcasting messages to all nodes.
6. Finding Connected Components: Identifying connected subgraphs.
7. Bipartite Graph Testing: Determining if a graph is bipartite.

Time and Space Complexity

• Time Complexity: O(V + E) where V is the number of vertices and E is the number of edges.
• Space Complexity: O(V) for the visited array and the queue.

Comparison of DFS and BFS

Aspect	DFS	BFS
Data Structure	Stack (explicit or call stack)	Queue
Space Complexity	O(h) where h is the height of the tree	O(w) where w is the maximum width of the tree
Completeness	Not complete (may not find a solution if there are infinite paths)	Complete (will find a solution if one exists)
Path Finding	May not find the shortest path	Finds the shortest path in unweighted graphs
Implementation	Simpler with recursion	Requires explicit queue
Use Cases	Topological sorting, cycle detection, path existence	Shortest path, level-order traversal, connected components

Advanced Traversal Techniques

Bidirectional Search

Bidirectional search runs two simultaneous BFS searches: one from the source and one from the destination. The search terminates when the two searches meet.

public bool BidirectionalSearch(int source, int destination)
{
    if (source == destination)
        return true;
    
    bool[] visitedSource = new bool[V];
    bool[] visitedDest = new bool[V];
    
    Queue<int> queueSource = new Queue<int>();
    Queue<int> queueDest = new Queue<int>();
    
    queueSource.Enqueue(source);
    visitedSource[source] = true;
    
    queueDest.Enqueue(destination);
    visitedDest[destination] = true;
    
    while (queueSource.Count > 0 && queueDest.Count > 0)
    {
        // One step in forward direction
        int vertexSource = queueSource.Dequeue();
        
        foreach (int adjVertex in adjacencyList[vertexSource])
        {
            if (!visitedSource[adjVertex])
            {
                visitedSource[adjVertex] = true;
                queueSource.Enqueue(adjVertex);
            }
            
            // If this vertex is already visited by the backward search
            if (visitedDest[adjVertex])
                return true; // Path found
        }
        
        // One step in backward direction
        int vertexDest = queueDest.Dequeue();
        
        foreach (int adjVertex in adjacencyList[vertexDest])
        {
            if (!visitedDest[adjVertex])
            {
                visitedDest[adjVertex] = true;
                queueDest.Enqueue(adjVertex);
            }
            
            // If this vertex is already visited by the forward search
            if (visitedSource[adjVertex])
                return true; // Path found
        }
    }
    
    return false; // No path found
}

Iterative Deepening Depth-First Search (IDDFS)

IDDFS combines the space efficiency of DFS with the completeness of BFS by performing DFS with increasing depth limits.

public bool IDDFS(int source, int destination, int maxDepth)
{
    for (int depth = 0; depth <= maxDepth; depth++)
    {
        if (DFSWithDepthLimit(source, destination, depth))
            return true;
    }
    
    return false;
}

private bool DFSWithDepthLimit(int vertex, int destination, int depthLimit)
{
    if (vertex == destination)
        return true;
    
    if (depthLimit <= 0)
        return false;
    
    foreach (int adjVertex in adjacencyList[vertex])
    {
        if (DFSWithDepthLimit(adjVertex, destination, depthLimit - 1))
            return true;
    }
    
    return false;
}

Depth-Limited Search

Depth-Limited Search is DFS with a depth limit to prevent infinite recursion in infinite or very deep graphs.

public bool DepthLimitedSearch(int source, int destination, int depthLimit)
{
    return DFSWithDepthLimit(source, destination, depthLimit);
}

Practical Applications and Examples

Finding Connected Components

public List<List<int>> FindConnectedComponents()
{
    bool[] visited = new bool[V];
    List<List<int>> components = new List<List<int>>();
    
    for (int i = 0; i < V; i++)
    {
        if (!visited[i])
        {
            List<int> component = new List<int>();
            DFSComponent(i, visited, component);
            components.Add(component);
        }
    }
    
    return components;
}

private void DFSComponent(int vertex, bool[] visited, List<int> component)
{
    visited[vertex] = true;
    component.Add(vertex);
    
    foreach (int adjVertex in adjacencyList[vertex])
    {
        if (!visited[adjVertex])
        {
            DFSComponent(adjVertex, visited, component);
        }
    }
}

Cycle Detection

public bool HasCycle()
{
    bool[] visited = new bool[V];
    bool[] recursionStack = new bool[V];
    
    for (int i = 0; i < V; i++)
    {
        if (IsCyclicUtil(i, visited, recursionStack))
            return true;
    }
    
    return false;
}

private bool IsCyclicUtil(int vertex, bool[] visited, bool[] recursionStack)
{
    // Mark the current node as visited and part of recursion stack
    if (recursionStack[vertex])
        return true;
    
    if (visited[vertex])
        return false;
    
    visited[vertex] = true;
    recursionStack[vertex] = true;
    
    foreach (int adjVertex in adjacencyList[vertex])
    {
        if (IsCyclicUtil(adjVertex, visited, recursionStack))
            return true;
    }
    
    recursionStack[vertex] = false; // Remove the vertex from recursion stack
    return false;
}

Topological Sorting

public List<int> TopologicalSort()
{
    bool[] visited = new bool[V];
    Stack<int> stack = new Stack<int>();
    
    for (int i = 0; i < V; i++)
    {
        if (!visited[i])
        {
            TopologicalSortUtil(i, visited, stack);
        }
    }
    
    List<int> result = new List<int>();
    while (stack.Count > 0)
    {
        result.Add(stack.Pop());
    }
    
    return result;
}

private void TopologicalSortUtil(int vertex, bool[] visited, Stack<int> stack)
{
    visited[vertex] = true;
    
    foreach (int adjVertex in adjacencyList[vertex])
    {
        if (!visited[adjVertex])
        {
            TopologicalSortUtil(adjVertex, visited, stack);
        }
    }
    
    // Push current vertex to stack which stores the result
    stack.Push(vertex);
}

Bipartite Graph Check

public bool IsBipartite()
{
    int[] color = new int[V];
    for (int i = 0; i < V; i++)
    {
        color[i] = -1; // No color assigned yet
    }
    
    for (int i = 0; i < V; i++)
    {
        if (color[i] == -1)
        {
            if (!IsBipartiteUtil(i, color))
                return false;
        }
    }
    
    return true;
}

private bool IsBipartiteUtil(int vertex, int[] color)
{
    Queue<int> queue = new Queue<int>();
    queue.Enqueue(vertex);
    color[vertex] = 1; // Assign first color
    
    while (queue.Count > 0)
    {
        int u = queue.Dequeue();
        
        foreach (int v in adjacencyList[u])
        {
            if (color[v] == -1)
            {
                // Assign alternate color
                color[v] = 1 - color[u];
                queue.Enqueue(v);
            }
            else if (color[v] == color[u])
            {
                // If adjacent vertices have same color, not bipartite
                return false;
            }
        }
    }
    
    return true;
}

Best Practices and Optimization

Choosing Between DFS and BFS

• Use DFS when:

  • You need to find a path to a destination (not necessarily the shortest)
  • You're working with deep graphs
  • You're checking for cycles
  • You need to perform topological sorting
  • Memory usage is a concern

• Use BFS when:

  • You need to find the shortest path in an unweighted graph
  • You're working with shallow but wide graphs
  • You need to find all nodes at a certain distance
  • You're testing if a graph is bipartite
  • Completeness is important

Optimizing Traversal Algorithms

1. Use Appropriate Data Structures: Choose the right graph representation (adjacency list for sparse graphs, adjacency matrix for dense graphs).
2. Avoid Redundant Visits: Ensure proper marking of visited vertices.
3. Consider Iterative Implementations: For very deep graphs, iterative implementations avoid stack overflow.
4. Use Bidirectional Search: For path finding between two known vertices, bidirectional search can be much faster.
5. Prune Search Space: Use domain knowledge to eliminate unnecessary paths.
6. Parallel Processing: For large graphs, consider parallel traversal algorithms.

Conclusion

Graph traversal algorithms are fundamental tools in graph theory and have numerous applications across computer science. Understanding both DFS and BFS, along with their variations and applications, provides a solid foundation for solving complex graph problems.

By choosing the appropriate traversal algorithm and optimizing its implementation for your specific problem, you can efficiently navigate even the most complex graph structures.