patternMinor
Graphs that cause DFS and BFS to process nodes in the exact same order
Viewed 0 times
exactnodesthesameorderprocessgraphsdfsbfsthat
Problem
For some graphs, DFS and BFS search algorithms process nodes in the exact same order provided that they both start at the same node. Two examples are graphs that are paths and graphs that are star-shaped (trees of depth $1$ with an arbitrary number of children). Is there some way for categorizing graphs that satisfy this property?
Solution
Assume our BFS and DFS have the rule to start from a specific node and both of them then visit the node with the lowest degree:
Start from left most black node, then both (BFS and DFS) traversals will visit left most red node, then they will visit next black node, and so on. To make it more general, you could add some paths in between triangles, or add star after finishing triangles.
Start from left most black node, then both (BFS and DFS) traversals will visit left most red node, then they will visit next black node, and so on. To make it more general, you could add some paths in between triangles, or add star after finishing triangles.
Context
StackExchange Computer Science Q#3263, answer score: 6
Revisions (0)
No revisions yet.