HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Graphs that cause DFS and BFS to process nodes in the exact same order

Submitted by: @import:stackexchange-cs··
0
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.

Context

StackExchange Computer Science Q#3263, answer score: 6

Revisions (0)

No revisions yet.