Graph traversal

Graph traversal is the process of visiting all the vertices (nodes) and edges (connections) of a graph in a systematic way. It's a fundamental operation in graph theory and is used to explore and analyze the structure of a graph. There are two primary methods for graph traversal: depth-first search (DFS) and breadth-first search (BFS).

Depth-First Search (DFS)

Depth-First Search (DFS) is a graph traversal algorithm that explores as far as possible along each branch before backtracking. It starts at a selected vertex and explores as deeply as possible along each branch before backtracking.

Depth-First Search Algorithm using Stack:

1. Initialization: Initialize an empty stack S and mark all vertices as unvisited.

2. Push Starting Vertex: Push the starting vertex s onto the stack S and mark it as visited.

3. Main Loop: While the stack S is not empty, do the following:
   - Visit Current Vertex: Pop the top vertex v from the stack S and mark it as visited.
   - Explore Neighbors: For each unvisited neighbor u of v, do the following:
      - Mark Neighbor as Visited: Mark the neighbor u as visited.
      - Push Neighbor onto Stack: Push the neighbor u onto the stack S.
   - Backtrack: If no unvisited neighbors are found for the current vertex, backtrack by popping vertices from the stack until a vertex with unvisited neighbors is found.

4. Termination: The algorithm terminates when the stack S becomes empty, indicating that all vertices have been visited.

Algorithm for Depth First Search

DFS(Graph, start):
    // Graph is represented as an adjacency list
    // start is the starting vertex for the DFS traversal

    Initialize an empty stack S
    Initialize an empty set visited to keep track of visited vertices
    
    Push start onto S
    Mark start as visited
    
    while S is not empty:
        current_vertex = S.pop() // Pop the top vertex from the stack
        
        // Process current_vertex (e.g., print it)
        print current_vertex
        
        for each neighbor in Graph[current_vertex]:
            if neighbor is not in visited:
                Push neighbor onto S
                Mark neighbor as visited

Find Depth First Search for Graph Given below:

Breadth-First Search (BFS)

Breadth-First Search (BFS) is a graph traversal algorithm that systematically explores all vertices and edges of a graph. It starts at a selected vertex (often called the "root" or "source") and explores all of its neighbors before moving on to the next level of vertices. BFS explores vertices level by level, visiting all the vertices at the current level before moving to the vertices at the next level.

Step by step working of BFS

Initialization: Choose a starting vertex s to begin the traversal. Mark all vertices as unvisited.

Visit the Starting Vertex: Mark the starting vertex s as visited and enqueue it into a queue.

Explore Neighbors: While the queue is not empty, dequeue a vertex v from the queue and visit all its unvisited neighbors. For each unvisited neighbor  u of  v, mark it as visited and enqueue it into the queue.

Repeat: Repeat step 3 until the queue becomes empty. This ensures that all vertices reachable from the starting vertex  s are visited.

Algorithm for Breadth First Search

BFS(Graph, start):
    // Graph is represented as an adjacency list
    // start is the starting vertex for the BFS traversal

    Initialize an empty queue Q
    Initialize an empty set visited to keep track of visited vertices
    
    Enqueue start into Q
    Mark start as visited
    
    while Q is not empty:
        current_vertex = dequeue(Q) // Dequeue a vertex from the queue
        
        // Process current_vertex (e.g., print it)
        print current_vertex
        
        // Traverse neighbors of current_vertex
        for each neighbor in Graph[current_vertex]:
            if neighbor is not in visited:
                Enqueue neighbor into Q
                Mark neighbor as visited

Find Breadth First Search for given graph
 

Topological Sorting

Topological sort of a directed acyclic graph (DAG) G is defined as a linear ordering of its nodes in which each node comes before all nodes to which it has outbound edges. Every DAG has one or more topological sorts.

A topological sort of a DAG G is an ordering of the vertices of G such that if G contains an edge (u, v), then u appears before v in the ordering. Note that topological sort is possible only on directed acyclic graphs that do not have any cycles. For a DAG that contains cycles, no linear ordering of its vertices is possible. In simple words, a topological ordering of a DAG G is an ordering of its vertices such that any directed path in G traverses the vertices in increasing order.

Topological sorting is widely used in scheduling applications, jobs, or tasks. The jobs that have to be completed are represented by nodes, and there is an edge from node u to v if job u must be completed before job v can be started. A topological sort of such a graph gives an order in which the given jobs must be performed.

Topological Sorting can be done by both DFS as well as BFS:

Topological sort using BFS

Algorithm for topological sort using BFS

Step 1: Find the in-degree INDEG(N) of every node in the graph
Step 2: Enqueue all the nodes with a zero in-degree
Step 3: Repeat Steps 4 and 5 until the QUEUE is empty
Step 4:Remove the front node N of the QUEUE by setting
                   FRONT = FRONT + 1
Step 5:Repeat for each neighbour M of node N:
          a) Delete the edge from N to M by setting
                   INDEG(M) = INDEG(M) - 1
         b) IF INDEG(M) = , then Enqueue M, that is, add M to the rear of the queue
        [END OF INNER LOOP]
      
   [END OF LOOP]
Step 6: Exit

Topological sort using: DFS

The pseudocode of topological sort is:

Step 1: Create the graph by calling addEdge(a,b).
Step 2: Call the topologicalSort( )
Step 2.1: Create a stack and a boolean array named as visited[ ];
Step 2.2: Mark all the vertices as not visited i.e. initialize visited[ ] with 'false' value.
Step 2.3: Call the recursive helper function topologicalSortUtil() to store Topological Sort starting from all vertices one by one.
Step 3: def topologicalSortUtil(int v, bool visited[],stack<int> &Stack):
Step 3.1: Mark the current node as visited.
Step 3.2: Recur for all the vertices adjacent to this vertex.
Step 3.3: Push current vertex to stack which stores result.
Step 4: Atlast after return from the utility function, print contents of stack.

Minimum Spanning Tree

A spanning tree of an undirected connected graph is its connected acyclic subgraph (i.e., a tree) that contains all the vertices of the graph. If such a graph has weights assigned to its edges, a minimum spanning tree is its spanning tree of the smallest weight, where the weight of a tree is defined as the sum of the weights on all its edges. The minimum spanning tree problem is the problem of finding a minimum spanning tree for a given weighted connected graph.