Depth First Search (DFS)
- It is like preorder traversal of tree.
- Traversal can start from any vertex vi.
- Vi is visited and then all vertices adjacent to vi are traversed recursively using DFS
DFS (G, 1) is given by
- Visit (1)
- DFS (G, 2) DFS (G, 3)
- DFS (G, 4)
- DFS (G, 5)
DFS traversal of given graph is:
1, 2, 6, 3, 8, 7, 4, 5
This procedure traverse the graph G inDFS manner. V is a starting vertex to be explored. S is a Stack, visited[] is an array which tells you whether particular vertex is visited or not. W is a adjacent node of vertex V. PUSH and POP are functions to insert and remove from stack respectively.
1.[Initialize TOP and Visited] visited[]<- 0 TOP <- 0
2.[Push vertex into stack]
PUSH (V)
3. [Repeat while stack is not empty]
Repeat step 3 while stack is not empty
v <- POP()
if visited[v] is 0
then visited [v] <- 1 for all W adjacent to v
if visited [w] is 0
then PUSH (W)
Breadth First Search (BFS)
- This methods starts from vertex v0.
- V0 is marked as visited. All vertices adjacent to v0 are visited next.
- Let vertices adjacent to v0 are v1, v2, v3, v4.
- v1, v2, v3 and v4 are marked visited.
- All unvisited vertices adjacent to v1, v2, v3, v4 are visited next.
- The method continuous until all vertices are visited.
- The algorithm for BFS has to maintain a list of vertices which have been visited but not explored for adjacent vertices. The vertices which have been visited but not explored for adjacent vertices can be stored in queue.
- Initially the queue contains the starting vertex.
- In every iteration, a vertex is removed from the queue and its adjacent vertices which are not visited as yet are added to the queue.
- The algorithm terminates when the queue becomes empty.
Graph G
BFS traversal of given graph is:
1 | 2, 3, 4, 5 | 6, 7 | 8
Procedure : BFS (Vertex V)
This procedure traverse the graph G in BFS manner. V is a starting vertex to be explored. Q is a queue, visited[] is an array which tells you whether particular vertex is visited or not. W is a adjacent node of vertex V.
1. Initialize Q
2. [Marks visited of V as 1]
visited [v]<- 1
3. [Add vertex v to Q]
InsertQueue(V)
4. [Repeat while Q is not empty]
Repeat while Q is not empty
v <- RemoveFromQueue()
For all vertices W adjacent to v
if visited[w] is 0
then visited[w]<-1
InsertQueue(w)
