Consider the undirected graph below and Kruskal's algorithm for computing a minimum spanning tree. In which order are the edges added to the solution?

Consider the undirected graph below and Prim's algorithm for computing a minimum spanning tree using node S as the source node. In which order are the edges added to the solution?

You are running the Kruskal's algorithm to obtain the minimum spanning tree of a connected, undirected, weighted graph with 10 vertices (ID-0 to ID-9). Given the following parent array state of the union-find data structure during the algorithm's run, which of the following statement(s) is true?

Consider the undirected graph below and Kruskal's algorithm for computing a minimum spanning tree. In which order are the edges added to the solution?

Consider the undirected graph below and Prim's algorithm for computing a minimum spanning tree using node S as the source node. In which order are the edges added to the solution?

Given a graph-G that has |V| vertices and |E| edges, that is:

• Connected.
• Directed.
• Weighted

What is the worst case time complexity to run Breadth-First Search (BFS), if G is implemented using adjacency matrix?

Given a graph-G that has |V| vertices and |E| edges, that is:

• Connected.
• Directed.
• Weighted

What is the worst case time complexity to obtain all of the outgoing edges from the vertex with the highest number of outgoing edges, if G is implemented using adjacency matrix?

Given a graph-G that has |V| vertices and |E| edges, that is:

• Connected.
• Directed.
• Weighted

What is the worst case time complexity to obtain the total number of incoming edges into vertex-v, if G is implemented using adjacency matrix?

Given a graph-G that has |V| vertices and |E| edges, that is:

• Connected.
• Directed.
• Weighted

What is the worst case time complexity to determine if there is an edge between vertex-u and vertex-v (incoming or outgoing), if G is implemented using adjacency matrix?

Recall the algorithm for shortest paths in an unweighted graph. We provide it below, as given in the course notes.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

function BFS(G = (V, E), s)
   dist[1..n] = ∞
   pred[1..n] = null
   queue = Queue()
   queue.push(s)
   dist[s] = 0
   while queue is not empty do
      u = queue.pop()
      for each vertex v adjacent to u do
         if dist[v] = ∞ then
            dist[v] = dist[u] + 1
            pred[v] = u
            queue.push(v)

Analyse this algorithm and provide:

• Its worst-case time complexity,
• Its auxiliary space complexity (excluding the input).

Assume the graph G is stored as an adjacency matrix. Make no assumption on the edge density of the graph.

Select one worst-case time complexity and one auxiliary space complexity from the list below. Two correct answers and zero incorrect answers are required to pass this question.