CODEWITHSUNDEEP
algorithmgraphdepth-first-searchbreadth-first-search
Bob John
Bob John

Reputation: 3878

Performing DFS and BFS on a directed graph

Suppose we have a graph such as:

graph

If you wanted a path from 0 to 5, in what order will we visit the nodes if we perform DFS and BFS on this graph (assume the lowest element is always pushed first). I'm having trouble conceptualizing how the algorithms will work for a graph with cycles, and I was hoping someone could outline the procedure each takes on such a graph.

Upvotes: 7

Views: 16345

Answers (2)

Naflan Mohamed
Naflan Mohamed

Reputation: 11

DFS Answer 1: 0,1,3,4,2,5 Answer 2: 0,2,5,4,3,1

BFS Answer: 0,1,2,3,5,4

Upvotes: 1

Adrian
Adrian

Reputation: 1176

Common technique which is used to deal with cycles is having set of already visited vertices. Before you push vertex to the queue/stack check if it was visited. If it was don't do any action, otherwise start from adding it to visited set and then continue traversing graph.

Stack from top to bottom.

DFS:

empty stack
visiting 0: stack: 2, 1, visited: 0
visiting 2: stack: 5, 3, 1 visited: 0, 2
visiting 5: stack: 4, 3, 1 visited: 0, 2, 5
visiting 4: stack: 3, 2, 3, 1 visited: 0, 2, 4, 5
visiting 3: stack: 4, 2, 3, 1 visited: 0, 2, 3, 4, 5
visiting 4: (nothing to do) - stack: 2, 3, 1 visited: 0, 2, 3, 4, 5
visiting 2: (nothing to do) - stack: 3, 1 visited: 0, 2, 3, 4, 5
visiting 3: (nothing to do) - stack: 3, 1 visited: 0, 2, 3, 4, 5
visiting 1: stack: 3, 0 visited: 0, 1, 2, 3, 4, 5
visiting 3: (nothing to do) - stack: 1 visited: 0, 1, 2, 3, 4, 5
visiting 1: (nothing to do) - stack empty visited: 0, 1, 2, 3, 4, 5
DONE

In similar fashion do for BFS.

Upvotes: 5

Related Questions