1,454 views
1 votes
1 votes
Give an example of a directed graph $G=(V, E)$, a source vertex $s\ \epsilon\ V$ , and a set of tree edges $E_{\Pi}\subseteq E$ such that for each vertex $v\ \epsilon\ V$ , the unique simple path in the graph $(V, E_{\Pi})$ from s to v is a shortest path in G, yet the set of edges $E_{\Pi}$ cannot be produced by running BFS on G, no matter how the vertices are ordered in each adjacency list.

1 Answer

Related questions

0 votes
0 votes
1 answer
4
akash.dinkar12 asked Apr 7, 2019
1,190 views
Give an adjacency-list representation for a complete binary tree on $7$ vertices. Give an equivalent adjacency-matrix representation. Assume that vertices are numbered fr...