menu
Recent questions tagged graph-algorithms
Login
Register
My account
Edit my Profile
Private messages
My favorites
Register
Recent questions tagged graph-algorithms
All Activity
Q&A
Questions
Unanswered
Tags
Categories
Users
Ask a Question
Blogs
Previous Year
Recent questions tagged graph-algorithms
0
votes
0
answers
1.5k
views
GATE CSE 2021 Set 2 | Question: 1 | Video Solution
Arjun
asked
in
Algorithms
Feb 18, 2021
by
Arjun
1.4k
points
1.5k
views
gate2021-cse-set2
algorithms
graph-algorithms
minimum-spanning-trees
0
votes
0
answers
824
views
GATE CSE 2021 Set 2 | Question: 46 | Video Solution
Arjun
asked
in
Algorithms
Feb 18, 2021
by
Arjun
1.4k
points
824
views
gate2021-cse-set2
multiple-selects
algorithms
graph-algorithms
0
votes
0
answers
888
views
GATE CSE 2021 Set 2 | Question: 55 | Video Solution
Arjun
asked
in
Algorithms
Feb 18, 2021
by
Arjun
1.4k
points
888
views
gate2021-cse-set2
algorithms
graph-algorithms
dag
numerical-answers
0
votes
0
answers
863
views
GATE CSE 2021 Set 1 | Question: 17 | Video Solution
Arjun
asked
in
Algorithms
Feb 18, 2021
by
Arjun
1.4k
points
863
views
gate2021-cse-set1
algorithms
graph-algorithms
minimum-spanning-trees
numerical-answers
1
vote
1
answer
191
views
Self Doubt - Classification of Edges in DFS
Source: Cormen. Back edges are those edges (u,v) connecting a vertex u to an ancestor v in a depth-first tree. We consider self-loops, which may occur in directed graphs, to be back edges. Forward edges are those non-tree edges (u, ... doubt: Why there is a difference in the definition of the highlighted part? Back edges are also non-tree edges, isn't it?
KUSHAGRA गुप्ता
asked
in
DS
Sep 8, 2020
by
KUSHAGRA गुप्ता
1.4k
points
191
views
algorithms
graph-algorithms
dfs
0
votes
0
answers
37
views
GATE2016-1-11 Video Solution
Consider the following directed graph: The number of different topological orderings of the vertices of the graph is _____________.
admin
asked
in
Algorithms
Apr 18, 2020
by
admin
589
points
37
views
gate2016-1
algorithms
graph-algorithms
normal
numerical-answers
video-solution
0
votes
0
answers
21
views
GATE2006-12 Video Solution
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
admin
asked
in
Algorithms
Apr 18, 2020
by
admin
589
points
21
views
gate2006
algorithms
graph-algorithms
easy
video-solution
0
votes
0
answers
31
views
GATE2012-40 Video Solution
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 when a strictly shorter path to $v$ is discovered. $\text{SDT}$ $\text{SBDT}$ $\text{SACDT}$ $\text{SACET}$
admin
asked
in
Algorithms
Apr 18, 2020
by
admin
589
points
31
views
gate2012
algorithms
graph-algorithms
normal
video-solution
0
votes
0
answers
25
views
GATE2008-45 Video Solution
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
admin
asked
in
Algorithms
Apr 18, 2020
by
admin
589
points
25
views
gate2008
algorithms
graph-algorithms
normal
video-solution
0
votes
0
answers
24
views
GATE2016-2-41 Video Solution
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 is ... $\Theta\left(n^{2}\right)$ $\Theta\left(n+m\right)$ $\Theta\left(m^{2}\right)$ $\Theta\left(n^{4}\right)$
admin
asked
in
Algorithms
Apr 18, 2020
by
admin
589
points
24
views
gate2016-2
algorithms
graph-algorithms
normal
video-solution
0
votes
0
answers
25
views
GATE2018-43 Video Solution
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 numbers ... denote the degree of a vertex in $G$, and $z$ denote the number of connected components in $G$. Then, $y+10z$ = ____
admin
asked
in
Algorithms
Apr 18, 2020
by
admin
589
points
25
views
gate2018
algorithms
graph-algorithms
graph-connectivity
numerical-answers
video-solution
0
votes
0
answers
13
views
GATE2006-48 Video Solution
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$
admin
asked
in
Algorithms
Apr 18, 2020
by
admin
589
points
13
views
gate2006
algorithms
graph-algorithms
normal
video-solution
0
votes
0
answers
17
views
GATE2003-67 Video Solution
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
admin
asked
in
Algorithms
Apr 18, 2020
by
admin
589
points
17
views
gate2003
algorithms
graph-algorithms
normal
video-solution
0
votes
0
answers
30
views
GATE2011-54 Video Solution
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$
admin
asked
in
Algorithms
Apr 18, 2020
by
admin
589
points
30
views
gate2011
algorithms
graph-algorithms
spanning-tree
normal
video-solution
0
votes
0
answers
21
views
GATE2015-1-45 Video Solution
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$
admin
asked
in
Algorithms
Apr 18, 2020
by
admin
589
points
21
views
gate2015-1
algorithms
graph-algorithms
normal
video-solution
0
votes
0
answers
23
views
GATE2018-47 Video Solution
Consider the following undirected graph $G$: Choose a value for $x$ that will maximize the number of minimum weight spanning trees (MWSTs) of $G$. The number of MWSTs of $G$ for this value of $x$ is ____.
admin
asked
in
Algorithms
Apr 18, 2020
by
admin
589
points
23
views
gate2018
algorithms
graph-algorithms
minimum-spanning-trees
numerical-answers
video-solution
0
votes
0
answers
26
views
GATE2009-13 Video Solution
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$
admin
asked
in
Algorithms
Apr 18, 2020
by
admin
589
points
26
views
gate2009
algorithms
graph-algorithms
normal
video-solution
0
votes
0
answers
28
views
GATE2003-70 Video Solution
Let $G= (V,E)$ be a directed graph with $n$ vertices. A path from $v_i$ to $v_j$ in $G$ is a sequence of vertices ($v_{i},v_{i+1}, \dots , v_j$) such that $(v_k, v_{k+1}) \in E$ for all $k$ in $i$ through $j-1$. A simple path is a path in ... length from $j$ to $k$ If there exists a path from $j$ to $k$, every simple path from $j$ to $k$ contains at most $A[j,k]$ edges
admin
asked
in
Algorithms
Apr 18, 2020
by
admin
589
points
28
views
gate2003
algorithms
graph-algorithms
normal
video-solution
0
votes
0
answers
20
views
GATE2007-41 Video Solution
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 Dijkstra’s algorithm starting from $S$. Warshall’s algorithm. Performing a DFS starting from $S$. Performing a BFS starting from $S$.
admin
asked
in
Algorithms
Apr 18, 2020
by
admin
589
points
20
views
gate2007
algorithms
graph-algorithms
easy
video-solution
0
votes
0
answers
19
views
GATE2005-IT-14 Video Solution
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$
admin
asked
in
Algorithms
Apr 18, 2020
by
admin
589
points
19
views
gate2005-it
algorithms
graph-algorithms
normal
video-solution
0
votes
0
answers
19
views
GATE2005-38 Video Solution
Let $G(V,E)$ be 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: $O\left(|V|^2\right)$ $O\left(|E|+|V|\log |V|\right)$ $O\left(|V|\log|V|\right)$ $O\left(\left(|E|+|V|\right)\log|V|\right)$
admin
asked
in
Algorithms
Apr 18, 2020
by
admin
589
points
19
views
gate2005
algorithms
graph-algorithms
normal
video-solution
0
votes
0
answers
19
views
GATE2013-19 Video Solution
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)$
admin
asked
in
Algorithms
Apr 18, 2020
by
admin
589
points
19
views
gate2013
algorithms
graph-algorithms
normal
video-solution
0
votes
0
answers
22
views
GATE2011-55 Video Solution
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. The length of the path from $v_5$ to $v_6$ in the MST of previous question with $n=10$ is $11$ $25$ $31$ $41$
admin
asked
in
Algorithms
Apr 18, 2020
by
admin
589
points
22
views
gate2011
algorithms
graph-algorithms
spanning-tree
normal
video-solution
0
votes
0
answers
17
views
GATE2007-IT-24 Video Solution
A depth-first search is performed on a directed acyclic graph. Let $d[u]$ denote the time at which vertex $u$ is visited for the first time and $f[u]$ the time at which the DFS call to the vertex $u$ terminates. Which of the following statements is always TRUE for all edges $(u, v)$ in the graph ? $d[u] < d[v]$ $d[u] < f[v]$ $f[u] < f[v]$ $f[u] > f[v]$
admin
asked
in
Algorithms
Apr 18, 2020
by
admin
589
points
17
views
gate2007-it
algorithms
graph-algorithms
normal
video-solution
0
votes
0
answers
20
views
GATE2017-1-26 Video Solution
Let $G=\left ( V,E \right )$ be $any$ connected, undirected, edge-weighted graph. The weights of the edges in $E$ are positive and distinct. Consider the following statements: Minimum Spanning Tree of $G$ is always unique. Shortest path between any ... is always unique. Which of the above statements is/are necessarily true? I only II only both I and II neither I nor II
admin
asked
in
Algorithms
Apr 18, 2020
by
admin
589
points
20
views
gate2017-1
algorithms
graph-algorithms
normal
video-solution
0
votes
0
answers
34
views
GATE2006-IT-46 Video Solution
Which of the following is the correct decomposition of the directed graph given below into its strongly connected components? $\left \{ P, Q, R, S \right \}, \left \{ T \right \},\left \{ U \right \}, \left \{ V \right \}$ ... $\left \{ P, Q, R, S, T, U, V \right \}$
admin
asked
in
Algorithms
Apr 18, 2020
by
admin
589
points
34
views
gate2006-it
algorithms
graph-algorithms
normal
video-solution
0
votes
0
answers
29
views
GATE1998-1.21, ISRO2008-16 Video Solution
Which one of the following algorithm design techniques is used in finding all pairs of shortest distances in a graph? Dynamic programming Backtracking Greedy Divide and Conquer
admin
asked
in
Algorithms
Apr 18, 2020
by
admin
589
points
29
views
gate1998
algorithms
graph-algorithms
easy
isro2008
video-solution
0
votes
0
answers
17
views
GATE2004-81 Video Solution
Let $G_1=(V,E_1)$ and $G_2 =(V,E_2)$ be connected graphs on the same vertex set $V$ with more than two vertices. If $G_1 \cap G_2= (V,E_1\cap E_2)$ is not a connected graph, then the graph $G_1\cup G_2=(V,E_1\cup E_2)$ cannot have a cut vertex must have a cycle must have a cut-edge (bridge) has chromatic number strictly greater than those of $G_1$ and $G_2$
admin
asked
in
Algorithms
Apr 18, 2020
by
admin
589
points
17
views
gate2004
algorithms
graph-algorithms
normal
video-solution
0
votes
0
answers
20
views
GATE2014-3-13 Video Solution
Suppose depth first search is executed on the graph below starting at some unknown vertex. Assume that a recursive call to visit a vertex is made only after first checking that the vertex has not been visited earlier. Then the maximum possible recursion depth (including the initial call) is _________.
admin
asked
in
Algorithms
Apr 18, 2020
by
admin
589
points
20
views
gate2014-3
algorithms
graph-algorithms
numerical-answers
normal
video-solution
0
votes
0
answers
55
views
GATE2016-2-11 Video Solution
Breadth First Search (BFS) is started on a binary tree beginning from the root vertex. There is a vertex $t$ at a distance four from the root. If $t$ is the $n^{th}$ vertex in this BFS traversal, then the maximum possible value of $n$ is __________
admin
asked
in
Algorithms
Apr 18, 2020
by
admin
589
points
55
views
gate2016-2
algorithms
graph-algorithms
normal
numerical-answers
video-solution
0
votes
0
answers
24
views
GATE2001-2.14 Video Solution
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 visited before $v$ during the breadth-first ... correct? $d(r,u) < d(r,v)$ $d(r,u) > d(r,v)$ $d(r,u) \leq d(r,v)$ None of the above
admin
asked
in
Algorithms
Apr 18, 2020
by
admin
589
points
24
views
gate2001
algorithms
graph-algorithms
normal
video-solution
0
votes
0
answers
15
views
GATE2005-82a Video Solution
Let $s$ and $t$ be two vertices in a undirected graph $G=(V,E)$ having distinct positive edge weights. Let $[X,Y]$ be a partition of $V$ such that $s \in X$ and $t \in Y$. Consider the edge $e$ having the minimum weight amongst all those edges that ... of $G$ the weighted shortest path from $s$ to $t$ each path from $s$ to $t$ the weighted longest path from $s$ to $t$
admin
asked
in
Algorithms
Apr 18, 2020
by
admin
589
points
15
views
gate2005
algorithms
graph-algorithms
normal
video-solution
0
votes
0
answers
17
views
GATE2005-IT-84a Video Solution
A sink in a directed graph is a vertex i such that there is an edge from every vertex $j \neq i$ to $i$ and there is no edge from $i$ to any other vertex. A directed graph $G$ with $n$ vertices is represented by its adjacency matrix $A$, where $A[i] [j] = 1$ if there is an edge ... $E_1:\ !A[i][j]$ and $E_2 : i = j$; $E_1 : A[i][j]$ and $E_2 : i = j + 1$;
admin
asked
in
Algorithms
Apr 18, 2020
by
admin
589
points
17
views
gate2005-it
algorithms
graph-algorithms
normal
video-solution
0
votes
0
answers
28
views
GATE2007-IT-3, UGCNET-June2012-III-34 Video Solution
admin
asked
in
Algorithms
Apr 18, 2020
by
admin
589
points
28
views
gate2007-it
algorithms
graph-algorithms
normal
ugcnetjune2012iii
video-solution
0
votes
0
answers
17
views
GATE2008-7 Video Solution
The most efficient algorithm for finding the number of connected components in an undirected graph on $n$ vertices and $m$ edges has time complexity $\Theta(n)$ $\Theta(m)$ $\Theta(m+n)$ $\Theta(mn)$
admin
asked
in
Algorithms
Apr 18, 2020
by
admin
589
points
17
views
gate2008
algorithms
graph-algorithms
time-complexity
normal
video-solution
0
votes
0
answers
18
views
GATE2014-2-14 Video Solution
Consider the tree arcs of a BFS traversal from a source node $W$ in an unweighted, connected, undirected graph. The tree $T$ ... graph. the shortest paths from $W$ to only those nodes that are leaves of $T$. the longest path in the graph.
admin
asked
in
Algorithms
Apr 18, 2020
by
admin
589
points
18
views
gate2014-2
algorithms
graph-algorithms
normal
video-solution
0
votes
0
answers
19
views
GATE1994-1.22 Video Solution
Which of the following statements is false? Optimal binary search tree construction can be performed efficiently using dynamic programming Breadth-first search cannot be used to find connected components of a graph Given the prefix and postfix walks ... binary tree cannot be uniquely constructed. Depth-first search can be used to find connected components of a graph
admin
asked
in
Algorithms
Apr 18, 2020
by
admin
589
points
19
views
gate1994
algorithms
normal
graph-algorithms
video-solution
0
votes
0
answers
67
views
GATE2008-IT-45 Video Solution
For the undirected, weighted graph given below, which of the following sequences of edges represents a correct execution of Prim's algorithm to construct a Minimum Spanning Tree? $\text{(a, b), (d, f), (f, c), (g, i), (d, a), (g, h), (c, e), (f, h)}$ ... $\text{(h, g), (g, i), (h, f), (f, c), (f, d), (d, a), (a, b), (c, e)}$
admin
asked
in
Algorithms
Apr 18, 2020
by
admin
589
points
67
views
gate2008-it
algorithms
graph-algorithms
spanning-tree
normal
video-solution
0
votes
0
answers
33
views
GATE2004-44 Video Solution
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$
admin
asked
in
Algorithms
Apr 18, 2020
by
admin
589
points
33
views
gate2004
algorithms
graph-algorithms
normal
video-solution
0
votes
0
answers
42
views
GATE2008-19 Video Solution
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: $MNOPQR$ $NQMPOR$ $QMNPRO$ $QMNPOR$
admin
asked
in
Algorithms
Apr 18, 2020
by
admin
589
points
42
views
gate2008
normal
algorithms
graph-algorithms
video-solution
Page:
1
2
next »
Ask a Question
Quick search syntax
tags
tag:apple
author
user:martin
title
title:apple
content
content:apple
exclude
-tag:apple
force match
+apple
views
views:100
score
score:10
answers
answers:2
is accepted
isaccepted:true
is closed
isclosed:true
Welcome to GATE CSE Doubts, where you can ask questions and receive answers from other members of the community.
Recent Posts
New GATEOverflow PDFs
Guidelines to users
No Recent Blog Comments
Search GATE CSE Video Solutions