In Prim's algorithm, we start with the _______ vertex r; it can be any vertex.

• A) Pivot
• B) Root
• C) Leaf
• D) negative

Edge weights can be interpreted as distance _________.

• A) in the shortest-paths
• B) in breadth-First Search
• C) in depth-First Search
• D) in Queue’s

We say that two vertices u and v are mutually _______ if u can reach v and vice versa.

• A) Not Reachable
• B) Reachable
• C) Crossed
• D) Forward

The key[u] is the weight of the __________ going from u to any vertex in S.

• A) lighter edge
• B) edge
• C) heavier edge
• D) lightest edge

Dijkstra’s algorithm works on a weighted directed graph G =(V, E) in which all_______weights are non-negative.

• A) links
• B) nodes
• C) vertices
• D) edges

A strongly connected component only apply to:

• A) Breadth First Search
• B) Undirected Graph
• C) Directed Graph
• D) Minimum Spanning Tree

Networks are ________ in the sense that it is possible from any location in the network to reach any other location in the digraph.

• A) Transportation
• B) Not graphs
• C) Complete
• D) Incomplete

Equivalence relation partitions the vertices into _________ classes of mutually reachable vertices and these are the strong components

• A) Equivalence
• B) Non classes
• C) Variance
• D) Non equivalence

In Kruskal’s algorithm, the vertices will be stored in ________.

• A) nodes
• B) sets
• C) loops
• D) links

___________is commonly the running time of Dijkstra’s Algorithm using the binary heap method.

• A) Θ(log E)
• B) Θ(E log V)
• C) Θ(Blog V)
• D) Θ(Vlog)

A digraph is strongly connected under what condition?

• A) A digraph is strongly connected if at least one third pair of vertices u, v e V, u can reach v and vice versa.
• B) A digraph is strongly connected if for every pair of vertices u, v e V, u can reach v and vice versa.
• C) A digraph is strongly connected if for every pair of vertices u, v e V, u can reach v .
• D) A digraph is strongly connected if for at least one pair of vertex u, v e V, u can reach v and vice versa.

A graph may contain ------------------------.

• A) Exactly one MST
• B) No MST
• C) One or zero MST
• D) More than one MST

In the shortest-paths problem, we are given a weighted of___________G = (V, E).

• A) Directed graph
• B) Line graph
• C) Weighted graph
• D) Un-directed graph

From the given option’s which one is correct regarding the time complexity of Dijkstra’s algorithm:

• A) O(log N)
• B) O(N^2)
• C) O(N)
• D) O(N^3)

Kruskal’s algorithm works by adding ________ in increasing order of weight (lightest edge first).

• A) Edges
• B) Trees
• C) Weights
• D) Vertices

Computing the strongly connected components of a digraph is a/an ___________ of the problem to determine whether a digraph is strongly connected or not.

• A) connection
• B) size
• C) optimization
• D) generalization

A topological sort of a DAG is a __________ ordering of the vertices of the DAG such that for each edge (u, v), u appears before v in the ordering.

• A) Linear
• B) Parallel
• C) Sequence
• D) Non-Linear

Digraphs ________ in communication and transportation networks.

• A) parts are used
• B) are not used
• C) are used
• D) final value is used

Timestamp structure of __________ is used in determining the strong components of a digraph.

• A) MST
• B) Both DFS & BFS
• C) DFS
• D) BFS

By breaking any edge on a cycle created in free tree, the free _________ is restored.

• A) Edge
• B) Tree
• C) Cycle
• D) Vertex