) Exercises Ex. 7.1 Breadth first decomposition Let an undir direction that the
ID: 3706347 • Letter: #
Question
) Exercises Ex. 7.1 Breadth first decomposition Let an undir direction that the BFS used to cross the edge for the first time. So if the BFS explores the entries in Adilul before exploring Adilel, the edge becomes (u, v). Let each edge that the BFS uses to reach a vertex furst time be called a tree edge. See the figure on the right. a) Explain why the non-tree edges are all cross edge with respect to the BFS-tree: start only the tree edges, run between ancestors and descendants of the BFS-defined tree. start T Numbers indicate 2 ( 2) level in c the BFS. b) Explain why äll edges connect vertices that are either on the same layer-level of the graph as defined by the BFS, or run from one level to the next.Explanation / Answer
a>
non tree edges are all cross edges with respect to bfs tree as in bfs only thre tree edges run between ancestors and descendants of bfs defined trees .this is so because
non trees are undirected graphs and in bfs that is breath first search tree we need easy traversing/access of nodes.so in that parent to child edges are being made for eg. as shown above figure if you want it to be bfs remove two edges from node 2 ->2 and from node 3-> 2 then it will be a bfs tree having simple edges which makes it easier and cross edges in non-trees makes traversing hard and presence of cycle in non tree make double traversing of any node ,which wastes time and make system complex.
b>
all edges are on same level or on or run from one levvel to other in bfs . as bfs is directed graph /directed tree which is used for easy access of all nodes .so to make traversing easy for eg from left to right .
for eg in above figure after removing above two edges as stated in part a> it become a bfs tree .then we want to traverse /access node 3
this is how it can be done
on level 1 node present is ----1 (1->2)
on level two two nodes are present -----2 & 2 (2->2)
on level three ----3 & 2 (2->3)
so traversing order will be from one level to other in left to right manner
1->2-.>2->3
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.