Login
Register
Dark Mode
Brightness
Profile
Edit Profile
Messages
My favorites
My Updates
Logout
Search results for graph-algorithms
31
votes
6
answers
1
GATE CSE 2008 | Question: 19
The Breadth First Search algorithm has been implemented using the queue data structure. One possible order of visiting the nodes of the following graph is: $\text{MNOPQR}$ $\text{NQMPOR}$ $\text{QMNPRO}$ $\text{QMNPOR}$
The Breadth First Search algorithm has been implemented using the queue data structure. One possible order of visiting the nodes of the following graph is:$\text{MNOPQR}$...
Kathleen
35.3k
views
Kathleen
asked
Sep 11, 2014
Algorithms
gatecse-2008
normal
algorithms
graph-algorithms
graph-search
+
–
59
votes
7
answers
2
GATE CSE 2006 | Question: 12
To implement Dijkstra’s shortest path algorithm on unweighted graphs so that it runs in linear time, the data structure to be used is: Queue Stack Heap B-Tree
To implement Dijkstra’s shortest path algorithm on unweighted graphs so that it runs in linear time, the data structure to be used is:QueueStackHeapB-Tree
Rucha Shelke
31.4k
views
Rucha Shelke
asked
Sep 16, 2014
Algorithms
gatecse-2006
algorithms
graph-algorithms
easy
+
–
63
votes
11
answers
3
GATE CSE 2008 | Question: 45
Dijkstra's single source shortest path algorithm when run from vertex $a$ in the above graph, computes the correct shortest path distance to only vertex $a$ only vertices $a, e, f, g, h$ only vertices $a, b, c, d$ all the vertices
Dijkstra's single source shortest path algorithm when run from vertex $a$ in the above graph, computes the correct shortest path distance toonly vertex $a$only vertices $...
Kathleen
27.3k
views
Kathleen
asked
Sep 12, 2014
Algorithms
gatecse-2008
algorithms
graph-algorithms
normal
+
–
65
votes
9
answers
4
GATE CSE 2012 | Question: 40
Consider the directed graph shown in the figure below. There are multiple shortest paths between vertices $S$ and $T$. Which one will be reported by Dijkstra's shortest path algorithm? Assume that, in any iteration, the shortest path to a vertex $v$ is updated only ... a strictly shorter path to $v$ is discovered. $\text{SDT}$ $\text{SBDT}$ $\text{SACDT}$ $\text{SACET}$
Consider the directed graph shown in the figure below. There are multiple shortest paths between vertices $S$ and $T$. Which one will be reported by Dijkstra’s shortest...
gatecse
26.5k
views
gatecse
asked
Sep 26, 2014
Algorithms
gatecse-2012
algorithms
graph-algorithms
normal
+
–
61
votes
5
answers
5
GATE CSE 2016 Set 1 | Question: 11
Consider the following directed graph: The number of different topological orderings of the vertices of the graph is _____________.
Consider the following directed graph:The number of different topological orderings of the vertices of the graph is _____________.
Sandeep Singh
28.3k
views
Sandeep Singh
asked
Feb 12, 2016
Algorithms
gatecse-2016-set1
algorithms
graph-algorithm
normal
numerical-answers
topological-sort
+
–
38
votes
5
answers
6
GATE CSE 2020 | Question: 31
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 weighed edge $(u, v) \in V \times V$ is added to $G$. The worst case time complexity of determining if $T$ is still an MST ... $\Theta (\mid E \mid \mid V \mid) \\$ $\Theta(E \mid \log \mid V \mid) \\$ $\Theta( \mid V \mid)$
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 weighed edge $(u, v) ...
Arjun
18.8k
views
Arjun
asked
Feb 12, 2020
Algorithms
gatecse-2020
algorithms
minimum-spanning-tree
graph-algorithm
2-marks
+
–
90
votes
12
answers
7
GATE CSE 2006 | Question: 48
Let $T$ be a depth first search tree in an undirected graph $G$. Vertices $u$ and $ν$ are leaves of this tree $T$. The degrees of both $u$ and $ν$ in $G$ are at least $2$ ... exist a cycle in $G$ containing $u$ and $ν$ There must exist a cycle in $G$ containing $u$ and all its neighbours in $G$
Let $T$ be a depth first search tree in an undirected graph $G$. Vertices $u$ and $ν$ are leaves of this tree $T$. The degrees of both $u$ and $ν$ in $G$ are at least $...
Rucha Shelke
20.9k
views
Rucha Shelke
asked
Sep 26, 2014
Algorithms
gatecse-2006
algorithms
graph-algorithms
normal
+
–
86
votes
5
answers
8
GATE CSE 2003 | Question: 67
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 shortest path ... edges in the shortest paths from $v_1$ to all vertices of $G$ $G_1$ is connected $V_1$ forms a clique in $G$ $G_1$ is a tree
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_...
Kathleen
19.9k
views
Kathleen
asked
Sep 17, 2014
Algorithms
gatecse-2003
algorithms
graph-algorithms
normal
+
–
39
votes
6
answers
9
GATE CSE 2020 | Question: 40
Let $G = (V,E)$ be a directed, weighted graph with weight function $w: E \rightarrow \mathbb{R}$. For some function $f: V \rightarrow \mathbb{R}$, for each edge$(u,v)\in E$, define ${w}'(u,v)$ as $w(u,v)+f(u)-f(v)$. Which one of the ... from $s$ to $u$ in the graph obtained by adding a new vertex $s$ to $G$ and edges of zero weight from $s$ to every vertex of $G$
Let $G = (V,E)$ be a directed, weighted graph with weight function $w: E \rightarrow \mathbb{R}$. For some function $f: V \rightarrow \mathbb{R}$, for each edge$(u,v)\in ...
Arjun
17.8k
views
Arjun
asked
Feb 12, 2020
Algorithms
gatecse-2020
algorithms
graph-algorithm
2-marks
+
–
65
votes
11
answers
10
GATE IT 2005 | Question: 14
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 $k$ $k+1$ $n-k-1$ $n-k$
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$k$$k+1$$n-k-1$$n-k$
Ishrat Jahan
17.5k
views
Ishrat Jahan
asked
Nov 3, 2014
Algorithms
gateit-2005
algorithms
graph-algorithms
normal
graph-search
+
–
51
votes
10
answers
11
GATE CSE 2015 Set 1 | Question: 45
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 starting at $s$. Let $T$ be the ... that is not in $T$, then which one of the following CANNOT be the value of $d(u) - d(v)$? $-1$ $0$ $1$ $2$
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 ...
makhdoom ghaya
18.0k
views
makhdoom ghaya
asked
Feb 13, 2015
Algorithms
gatecse-2015-set1
algorithms
graph-algorithms
normal
graph-search
+
–
47
votes
7
answers
12
GATE CSE 2018 | Question: 30
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. No edge of $G$ is a cross edge with respect to $T_D$. (A cross edge in $G$ ... $\mid i-j \mid =1$. Which of the statements above must necessarily be true? I only II only Both I and II Neither I nor II
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.No...
gatecse
27.1k
views
gatecse
asked
Feb 14, 2018
Algorithms
gatecse-2018
algorithms
graph-algorithm
graph-search
normal
2-marks
+
–
63
votes
5
answers
13
GATE CSE 2018 | Question: 43
Let $G$ be a graph with $100!$ vertices, with each vertex labelled by a distinct permutation of the numbers $1, 2,\ldots, 100.$ There is an edge between vertices $u$ and $v$ if and only if the label of $u$ can be obtained by swapping two adjacent ... denote the degree of a vertex in $G$, and $z$ denote the number of connected components in $G$. Then, $y+10z=$ ______.
Let $G$ be a graph with $100!$ vertices, with each vertex labelled by a distinct permutation of the numbers $1, 2,\ldots, 100.$ There is an edge between vertices $u$ and ...
gatecse
19.7k
views
gatecse
asked
Feb 14, 2018
Algorithms
gatecse-2018
algorithms
graph-algorithm
numerical-answers
2-marks
+
–
49
votes
7
answers
14
GATE CSE 2009 | Question: 13
Which of the following statement(s) is/are correct regarding Bellman-Ford shortest path algorithm? P: Always finds a negative weighted cycle, if one exists. Q: Finds whether any negative weighted cycle is reachable from the source. $P$ only $Q$ only Both $P$ and $Q$ Neither $P$ nor $Q$
Which of the following statement(s) is/are correct regarding Bellman-Ford shortest path algorithm?P: Always finds a negative weighted cycle, if one exists.Q: Finds whethe...
Kathleen
16.5k
views
Kathleen
asked
Sep 22, 2014
Algorithms
gatecse-2009
algorithms
graph-algorithms
normal
+
–
52
votes
10
answers
15
GATE CSE 2011 | Question: 54
An undirected graph $G(V,E)$ contains $n \: (n>2)$ nodes named $v_1,v_2, \dots, v_n$. Two nodes $v_i, v_j$ are connected if and only if $ 0 < \mid i-j\mid \leq 2$. Each edge $(v_i,v_j)$ is assigned a weight $i+j$. A sample graph with $n=4$ is shown below. ... spanning tree (MST) of such a graph with $n$ nodes? $\frac{1}{12} (11n^2 - 5 n)$ $n^2-n+1$ $6n-11$ $2n+1$
An undirected graph $G(V,E)$ contains $n \: (n>2)$ nodes named $v_1,v_2, \dots, v_n$. Two nodes $v_i, v_j$ are connected if and only if $ 0 < \mid i-j\mid \leq 2$. Each ...
go_editor
17.0k
views
go_editor
asked
Sep 29, 2014
Algorithms
gatecse-2011
algorithms
graph-algorithms
spanning-tree
normal
+
–
20
votes
6
answers
16
GATE CSE 2021 Set 2 | Question: 1
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 distinct weight, then $G$ has a ... are true $S_1$ is true and $S_2$ is false $S_1$ is false and $S_2$ is true Both $S_1$ and $S_2$ are false
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...
Arjun
11.7k
views
Arjun
asked
Feb 18, 2021
Algorithms
gatecse-2021-set2
algorithms
graph-algorithm
minimum-spanning-tree
1-mark
+
–
93
votes
4
answers
17
GATE CSE 2016 Set 2 | Question: 41
In an adjacency list representation of an undirected simple graph $G=(V, E)$, each edge $(u, v)$ has two adjacency list entries: $[v]$ in the adjacency list of $u$, and $[u]$ in the adjacency list of $v$. These are called twins of each other. A twin pointer ... $\Theta\left(n+m\right)$ $\Theta\left(m^{2}\right)$ $\Theta\left(n^{4}\right)$
In an adjacency list representation of an undirected simple graph $G=(V, E)$, each edge $(u, v)$ has two adjacency list entries: $[v]$ in the adjacency list of $u$, and $...
Akash Kanase
19.5k
views
Akash Kanase
asked
Feb 12, 2016
Algorithms
gatecse-2016-set2
algorithms
graph-algorithms
normal
+
–
37
votes
3
answers
18
GATE CSE 2004 | Question: 44
Suppose we run Dijkstra’s single source shortest path algorithm on the following edge-weighted directed graph with vertex $P$ as the source. In what order do the nodes get included into the set of vertices for which the shortest path distances are finalized? $P,Q,R,S,T,U$ $P,Q,R,U,S,T$ $P,Q,R,U,T,S$ $P,Q,T,R,U,S$
Suppose we run Dijkstra’s single source shortest path algorithm on the following edge-weighted directed graph with vertex $P$ as the source.In what order do the nodes g...
Kathleen
15.4k
views
Kathleen
asked
Sep 18, 2014
Algorithms
gatecse-2004
algorithms
graph-algorithm
normal
dijkstras-algorithm
+
–
15
votes
3
answers
19
GATE CSE 2021 Set 2 | Question: 46
Consider the following directed graph: Which of the following is/are correct about the graph? The graph does not have a topological order A depth-first traversal starting at vertex $S$ classifies three directed edges as back edges The graph does not have a strongly connected component For each pair of vertices $u$ and $v$, there is a directed path from $u$ to $v$
Consider the following directed graph:Which of the following is/are correct about the graph?The graph does not have a topological orderA depth-first traversal starting at...
Arjun
8.6k
views
Arjun
asked
Feb 18, 2021
Algorithms
gatecse-2021-set2
multiple-selects
algorithms
graph-algorithm
2-marks
+
–
34
votes
4
answers
20
GATE CSE 2013 | Question: 19
What is the time complexity of Bellman-Ford single-source shortest path algorithm on a complete graph of n vertices? $\theta(n^2)$ $\theta(n^2\log n)$ $\theta(n^3)$ $\theta(n^3\log n)$
What is the time complexity of Bellman-Ford single-source shortest path algorithm on a complete graph of n vertices?$\theta(n^2)$ $\theta(n^2\log n)$ $\theta(n^3)...
Arjun
24.1k
views
Arjun
asked
Sep 23, 2014
Algorithms
gatecse-2013
algorithms
graph-algorithms
normal
+
–
Page:
1
2
next »
Email or Username
Show
Hide
Password
I forgot my password
Remember
Log in
Register