Graph Algorithms

Consider the following pseudocode for depth-first search (DFS) algorithm which takes a directed graph $G(V, E)$ as input, where $d[v]$ and $f[v]$ are the discovery time and finishing time, respectively, of the vertex $v...

Let $G$ be a weighted directed acyclic graph with $m$ edges and $n$ vertices. Given $G$ and a source vertex $s$ in $G$, which one of the following options gives the worst case time complexity of the fastest algorithm to...

Let $G(V, E)$ be a simple, undirected, edge-weighted graph with unique edge weights. Which of the following statements about the minimum spanning trees (MST) of $G$ is/are true?

Let $G(V, E)$ be an undirected, edge-weighted graph with integer weights. The weight of a path is the sum of the weights of the edges in that path. The length of a path is the number of edges in that path. Let $s \in V$...

Let $G(V, E)$ be an undirected and unweighted graph with 100 vertices. Let $d(u, v)$ denote the number of edges in a shortest path between vertices $u$ and $v$ in $V$. Let the maximum value of $d(u, v), u, v \in V$ such...

Which of the following statements regarding Breadth First Search (BFS) and Depth First Search (DFS) on an undirected simple graph G is/are TRUE?

Let $G$ be any undirected graph with positive edge weights, and $T$ be a minimum spanning tree of $G$. For any two vertices, $u$ and $v$, let $d_1(u, v)$ and $d_2(u, v)$ be the shortest distances between $u$ and $v$ in $...

Let $G$ be an edge-weighted undirected graph with positive edge weights. Suppose a positive constant $\alpha$ is added to the weight of every edge. Which ONE of the following statements is TRUE about the minimum spanning...

Let G be a directed graph and T a depth first search (DFS) spanning tree in G that is rooted at a vertex v. Suppose T is also a breadth first search (BFS) tree in G, rooted at v. Which of the following statements is/are...

Let $G$ be an undirected connected graph in which every edge has a positive integer weight. Suppose that every spanning tree in $G$ has even weight. Which of the following statements is/are TRUE for every such graph $G$?

Let $$U = \{ 1,2,3\} $$. Let 2$$^U$$ denote the powerset of U. Consider an undirected graph G whose vertex set is 2$$^U$$. For any $$A,B \in {2^U},(A,B)$$ is an edge in G if and only if (i) $$A \ne B$$, and (ii) either $...

An articulation point in a connected graph is a vertex such that removing the vertex and its incident edges disconnects the graph into two or more connected components. Let T be a DFS tree obtained by doing DFS in a conn...

Let G be a connected undirected weighted graph. Consider the following two statements. S 1 : There exists a minimum weight edge in G which is present in every minimum spanning tree of G. S 2 : If every edge in G has dist...

Consider a complete binary tree with 7 nodes. Let A denote the set of first 3 elements obtained by performing Breadth-First Search (BFS) starting from the root. Let B denote the set of first 3 elements obtained by perfor...

Consider a graph G = (V, E), where V = {v 1 , v 2 , ...., v 100 }, E = {(v i , v j ) | 1 ≤ i < j ≤ 100}, and weight of the edge (v i , v j ) is |i - j|. The weight of the minimum spanning tree of G is ______.

Let G = (V, E) be a weighted undirected graph and let T be a Minimum Spanning Tree (MST) of G maintained using adjacency lists. Suppose a new weighted edge (u, v) $$ \in $$ V $$ \times $$ V is added to G. The worst case...

Let G = (V, E) be a directed, weighted graph with weight function w: E $$ \to $$ R. For some function f: V $$ \to $$ R, for each edge (u, v) $$ \in $$ E, define w'(u, v) as w(u, v) + f(u) - f(v). Which one of the options...

Let $$G$$ be a simple undirected graph. Let $${T_D}$$ be a depth first search tree of $$G.$$ Let $${T_B}$$ be a breadth first search tree of $$G.$$ Consider the following statements. $$(I)$$ No edge of $$G$$ is a cross e...

Consider the following table : Algorithms Design Paradigms (P) Kruskal (ii) Greedy (Q) Quicksort (i) Divide and Conquer (R) Floyd–Warshall (iii) Dynamic Programming Match the algorithms to the design paradigms they are b...

$$G = (V,E)$$ is an undirected simple graph in which each edge has a distinct weight, and e is a particular edge of G. Which of the following statements about the minimum spanning trees $$(MSTs)$$ of $$G$$ is/are TRUE ?...

Let $$G$$ be a weighted connected undirected graph with distinct positive edge weights. If every edge weight is increased by the same value, then which of the following statements is/are TRUE ? $$P:$$ Minimum spanning tr...

Consider the weighted undirected graph with $$4$$ vertices, where the weight of edge $$\left\{ {i,j} \right\}$$ is given by the entry $${W_{ij}}$$ in the matrix $$W.$$ $$$W = \left[ {\matrix{ 0 & 2 & 8 & 5 \cr 2 & 0 & 5...

Given below are some algorithms, and some algorithm design paradigms. GROUP 1 GROUP 2 1. Dijkstra's Shortest Path i. Divide and Conquer 2. Floyd-Warshall algorithm to compute all pairs shortest path ii. Dynamic Programmi...

Let G = (V, E) be a simple undirected graph, and s be a particular vertex in it called the source. For $$x \in V$$, let d(x) denote the shortest distance in G from s to x. A breadth first search (BFS) is performed starti...

Match the following: List 1 (P) Prim’s algorithm for minimum spanning tree (Q) Floyd-Warshall algorithm for all pairs shortest paths (R) Mergesort (S) Hamiltonian circuit List 2 (i) Backtracking (ii) Greedy method (iii)...

Let G be a graph with n vertices and m edges. What is the tightest upper bound on the running time of Depth First Search on G, when G is represented as an adjacency matrix?

Let $$G = \left( {V,E} \right)$$ be a directed graph where $$V$$ is the set of vertices and $$E$$ the set of edges. Then which one of the following graphs has the same strongly connected components as $$G$$?

Consider the tree arcs of a BFS traversal from a source node W in an unweighted, connected, undirected graph. The tree T formed by the tree arcs is a data structure for computing

What is the time complexity of Bellman-Ford single-source shortest path algorithm on a complete graph of n vertices?

Let G be a weighted graph with edge weights greater than one and G' be the graph constructed by squaring the weights of edges in G. Let T and T' be the minimum spanning trees of G and G' respectively, with total weights...

Consider a complete undirected graph with vertex set {0, 1, 2, 3, 4}. Entry W(ij) in the matrix W below is the weight of the edge {i, j}. $$$w = \left( {\matrix{ 0 & 1 & 8 & 1 & 4 \cr 1 & 0 & {12} & 4 & 9 \cr 8 & {12} &...

Consider a complete undirected graph with vertex set {0, 1, 2, 3, 4}. Entry W(ij) in the matrix W below is the weight of the edge {i, j}. $$$w = \left( {\matrix{ 0 & 1 & 8 & 1 & 4 \cr 1 & 0 & {12} & 4 & 9 \cr 8 & {12} &...

Consider a complete undirected graph with vertex set {0,1,2,3,4}. Entry W ij in the matrix W below is the weight of the edge {i, j} $$$W = \left( {\matrix{ 0 & 1 & 8 & 1 & 4 \cr 1 & 0 & {12} & 4 & 9 \cr 8 & {12} & 0 & 7...

Consider a complete undirected graph with vertex set {0,1,2,3,4}. Entry W ij in the matrix W below is the weight of the edge {i, j} $$$W = \left( {\matrix{ 0 & 1 & 8 & 1 & 4 \cr 1 & 0 & {12} & 4 & 9 \cr 8 & {12} & 0 & 7...

Which of the following statement(s) is / are correct regarding Bellman-Ford shortest path algorithm? P: Always finds a negative weighted cycle, if one exist s. Q: Finds whether any negative weighted cycle is reachable fr...

The most efficient algorithm for finding the number of connected components in an undirected graph on n vertices and m edges has time complexity

Let w be the minimum weight among all edge weights in an undirected connected graph. Let e be a specific edge of weight w . Which of the following is FALSE?

In an unweighted, undirected connected graph, the shortest path from a node S to every other node is computed most efficiently, in terms of time complexity by

Consider a weighted undirected graph with positive edge weights and let $$uv$$ be an edge in the graph. It is known that the shortest path from the source vertex $$s$$ to $$u$$ has weight 53 and the shortest path from $$...

Let T be a depth-first search tree in an undirected graph G. Vertices u and v are leaves of this tree T. The degrees of both u and v in G are at least 2. Which one of the following statements is true?

Consider the depth-first-search of an undirected graph with 3 vertices P, Q, and R. Let discovery time d(u) represent the time instant when the vertex u is first visited, and finish time f(u) represent the time instant w...

Consider a weighted complete graph G on the vertex set {v1, v2, ..vn} such that the weight of the edge (vi, vj) is $$2|i-j|$$. The weight of a minimum spanning tree of G is:

Let T be a depth first search tree in an undirected graph G. Vertices u and v are leaves of this tree T. The degrees of both u and v in G are at least 2. which one of the following statements is true?

To implement Dijkstra’s shortest path algorithm on unweighted graphs so that it runs in linear time, the data structure to be used is:

Let G(V, E) an undirected graph with positive edge weights. Dijkstra's single-source shortest path algorithm can be implemented using the binary heap data structure with time complexity:

The time complexity of computing the transitive closure of a binary relation on a set of elements is known to be:

Level order traversal of a rooted tree can be done by starting from the root and performing

In a depth-first traversal of a graph G with n vertices,k edges are marked as tree edges. The number of connected components in G is

Let G=(V,E) be an undirected graph with a subgraph G 1 =(V 1 ,E 1 ). Weights are assigned to edges of G as follows. $$$w(e) = \begin{cases} 0 \text{, if } e \in E_1 \\1 \text{, otherwise} \end{cases}$$$ A single-source s...

Let G = (V, E) be a directed graph with n vertices. A path from v i to v j in G is sequence of vertices (v i , v i +1, ……., v j ) such that (v k , v k +1) ∈ E for all k in i through j – 1. A simple path is a path in whic...

Consider an undirected unweighted graph G. Let a breadth-first traversal of G be done starting from a node r. Let d(r, u) and d(r, v) be the lengths of the shortest paths from r to u and v respectively in G. If u is visi...

Let G be an undirected graph. Consider a depth-first traversal of G, and let T be the resulting depth-first search tree. Let u be a vertex in G and let v be the first new (unvisited) vertex visited after visiting u in th...

Let G be an undirected connected graph with distinct edge weight. Let emax be the edge with maximum weight and emin the edge with minimum weight. Which of the following statements is false?

Which one of the following algorithm design techniques is used in finding all pairs of shortest distances in a graph?

The correct matching for the following pairs is A. All pairs shortest path 1. Greedy B. Quick Sort 2. Depth-First Search C. Minimum weight spanning tree 3. Dynamic Programming D. Connected Components 4. Divide and Conque...

Which one of the following statements is false?

Complexity of Kruskal’s algorithm for finding the minimum spanning tree of an undirected graph containing n vertices and m edges if the edges are sorted is _______.

Kruskal’s algorithm for finding a minimum spanning tree of a weighted graph G with n vertices and m edges has the time complexity of:

Match the pairs in the following: List - I (a) Straseen's matrix multiplication algorithm (b) Kruskal's minimum spanning tree algorithm (c) Bioconnected components algorithm (d) Floyd's shortest path algorithm List - II...