CODEWITHSUNDEEP
graphgraph-algorithmdepth-first-searchbreadth-first-search
alkabary
alkabary

Reputation: 177

Breadth and depth first search on a graph with returning edges

enter image description here

I do understand depth and breadth first search but this graph got me confused as there is nodes that points to preceding nodes in the graph.

So let's say for instant that N is a goal state, then using Depth first search we would have

A B E J K L F G M N

So we is it correct this way ? I don't repeat the A because it was visited before right.

And using breadth first search I would go level by level and so I would have

A B C D E F G H I J K L M N

Is this correct ?

And if we change the Goal state to P

then DFS will give us A B E J K L F G M N H O P

and BFS will give us A B C D E F G H I J K L M N O P

I feel I got this right, I am just uncertain if I am right because of the returning edges in this graph. So I just want someone to confirm that I am on the right track here.

Upvotes: 0

Views: 129

Answers (1)

Andrew Shirley
Andrew Shirley

Reputation: 417

That sounds correct to me. When pointing to a node that's already in your result set, it should not be added into the result set a second time.

Upvotes: 1

Related Questions