Page 1 of 1
Q1. Graph-Representation and Traversal (25 marks). i. Adjacency list and adjacency matrix are two standard ways to repre
Posted: Wed Apr 27, 2022 3:41 pm
by answerhappygod
- Q1 Graph Representation And Traversal 25 Marks I Adjacency List And Adjacency Matrix Are Two Standard Ways To Repre 1 (44.67 KiB) Viewed 92 times
Q1. Graph-Representation and Traversal (25 marks). i. Adjacency list and adjacency matrix are two standard ways to represent graphs. Show the space consumption, the cost to count the number of edges in the graph and the cost to check the existence of an edge with adjacency list and adjacency matrix respectively. ii. In Fig. 1 is an undirected graph G. Show the sequence of nodes in the breadth-first traversal starting from node vi, assuming that the neighbor nodes in the adjacency list of each node are in increasing order. Q2. Graph-Spanning Tree [25 marks). The edges of graph in Fig. 1 carry weights. Use Prim's Algorithm to generate the minimum cost of spanning tree step by step. (v1 V2 13! 11 V3 (V4 (v5 15 7 10 5 (V6 (V8 3 Fig. 1. A weighted graph G.