GRAPH-TRAVERSAL.md

Main
next(Spanning Tree)

Graph Traversal

It's the process of visiting each vertex in a graph. There are two standard methods.

1. BFS ( Breadth First Search )
2. DFS ( Depth First Search )

1️⃣ BFS ( Breadth First Search )

2️⃣ DFS ( Depth First Search )

DFS produces a spanning tree as an final result , i.e a graph without loops .We uses a stack with maximum size of total no of vertices in the graph to implement the DFS

psuedocode

DFS(G,v)   ( v is the vertex where the search starts )    
        Stack S := {};   ( start with an empty stack )    
        for each vertex u, set visited[u] := false;    
        push S, v;    
        while (S is not empty) do    
           u := pop S;    
           if (not visited[u]) then    
              visited[u] := true;    
              for each unvisited neighbour w of uu    
                 push S, w;    
           end if    
        end while    
     END DFS()    

next(Spanning Tree)