CODEWITHSUNDEEP
algorithmgraphtreebreadth-first-searchshortest-path
InChul Song
InChul Song

Reputation: 3

I cannot understand BFS Tree Edges in Algorithm Design Manual

I can't understand what this mean

The graph edges that do not appear in the breadth-first search tree also have special properties. For undirected graphs, non-tree edges can point only to vertices on the same level as the parent vertex, or to vertices on the level directly below the parent. These properties follow easily from the fact that each path in the tree must be a shortest path in the graph. For a directed graph, a back-pointing edge (u, v) can exist whenever v lies closer to the root than u does.

I understand that 'The graph edges that do not appear in the breadth-first search tree also have special properties.'. But how can I know the these property follow easily from the fact that each path in the tree must be a shortest path in graph? Also, for a directed graph, for a directed graph, how can I prove a back-pointing edge (u, v) can exist whenever v lies closer to the root than u does?

Upvotes: 0

Views: 1141

Answers (1)

templatetypedef
templatetypedef

Reputation: 373382

Because we’re working with a BFS tree, all nodes in the same level of the tree must be at the same distance from the root node. So, for example, a node at depth five must have distance five from the root node. Similarly, a node at depth ten must have distance ten from the root.

First, let’s talk undirected graphs. Imagine there’s an edge {u, v} not in the BFS tree. Now, suppose u and v are more than two levels apart in the tree, and specifically that v is at least two levels below u. That means that the distance from the root node s to v is two more than the distance from s to u. Consequently, the length of the shortest path from s to v is at least two edges more than the length of the shortest path from s to u (that’s the definition of shortest paths). But that’s not true here: we can get a path from s to v that’s only one edge longer than the shortest path from s to u by following the shortest path from s to u, then following the edge {u, v}. Something’s gone wrong here, and specifically it was our assumption that v is two or more levels below u.

For directed graphs, you can indeed have directed edges that jump back up to higher levels in the tree. A very simple way to see this: consider a triangle of nodes u, v, w where u has an edge to v, v has an edge to w, and w has an edge to u. What does the BFS tree look like?

Upvotes: 1

Related Questions