Data structures and algorithms

The graph G, given above, is converted into a weighted graph wG - , as follows: {(A, (1, 23)), (B, (2, 17), (C, (3, 14), (D, (4, 6)), (J, (5, 13)), (K, (6, 10), (P, (5,1))/Q (3,7), Do the following problems: a. Draw the weighted graph wG. b. Draw an adjacency matrix representation of wo. c. Draw a linked list implementation of the adjacency list representation of wG d. Find the least cost path from node A to all the other nodes, using Dijkstra's algorithm. e. Sort the weight values in the second position of each 2-tuple node weight, using (x1) Treesort, 2. f. g. (x2) Quicksort, and (x3) Mergesort. Use a hash table (of size 10) to store all the edge weights of wG Use a heap to store the weight values in the first position of each 2-tuple node weight. 3. Explain what it means to state that a graph algorithm for a graph G , with m IVI, and n [E], has the complexity as given in each of the following: b. O(mn) O(n/m) c. d. Qtlog(n/m) f, mn ~ O(m3) ~ ? (n2)