Exercises
Generate an adjacency matrix and an adjacency list for the following graph:
Generate a DFS and BFS tree for the preceding graph.
Prove the following hypothesis: An acyclic undirected graph with n nodes has no more than n-1 edges.
Find the MST for the graph given in Figure 8.13 using Prim's and Kruskal's algorithm. Do they give the same MSTs? If no, in what type of situations do they give different MSTs.
Starting from vertex B, can you obtain single-source shortest paths using Dijkstra's algorithm? Do the edges obtained in question 4 of Exercises overlap with the edges obtained using Dijkstra's algorithm? If yes, explain the logic behind the overlap.
