1. What is the running time of a. Breadth-first search b. Depth-first search as afunction of |V I and |El, ifthe input graph is represented by an adjacency matrix instead of an adjacency list? 2. Drawthe weighted directed graphs whose edges-weights are given by Perform Dijkstra's algorithm to determine the distances and shortest paths from a to every other node. 3. Drawthe weighted undirected graphs whose edges-weights aregiven by E-[la,b,2), sa,c,13, sb,f,33, sc,b,13, sc,g,43, sd,c,2), sd,e,3), se,f,7], sg,f,5], [g,h,43] E-[la, b, 3], [a, d, 4], [a,e, 4), [b, c, 10], [b, e, 2), [b,f, 3], [c, f, 6], [c, g, 13, [d, e, 5], d, h, 6], se,f,11), se, h, 2), se, i, 13, sf, g, 2), ff, i, 13, sf, j, 11), sh, i, 4], si, j, 7)3. a. Perform Kruskal'salgorithm b. Perform Prim's algorithm to obtain a minimum spanning tree (MST) for G