Pages

Thursday, 14 June 2012

CS502 Assignment no 4 Spring 2012 Idea solution


Assignment Statements:

Question:

Give an example of a directed graph G = (V, E), a source vertex s Description: symbol for belongs to V, and a set of tree edges Eπ E such that for each vertex v Description: symbol for belongs to V, the unique path in the graph (V, Eπ) from s to v is a shortest path in G, yet the set of edges Eπ cannot be produced by running BFS on G, no matter how the vertices are ordered in each adjacency list.