Recent questions tagged graph-algorithms / GATE Overflow for GATE CSE

1 votes

1 answer

61

Cormen Edition 3 Exercise 22.2 Question 6 (Page No. 539)
Give an example of a directed graph $G=(V, E)$, a source vertex $s\ \epsilon\ V$ , and a set of tree edges $E_{\Pi}\subseteq E$ such that for each vertex $v\ \epsilon\ V$ ... set of edges $E_{\Pi}$ cannot be produced by running BFS on G, no matter how the vertices are ordered in each adjacency list.

Give an example of a directed graph $G=(V, E)$, a source vertex $s\ \epsilon\ V$ , and a set of tree edges $E_{\Pi}\subseteq E$ such that for each vertex $v\ \epsilon\ V$...

KUSHAGRA गुप्ता

1.7k views

KUSHAGRA गुप्ता asked Nov 12, 2019

1 votes

2 answers

62

KPGCET-CSE-2019-33
The least running time of creating spanning tree from connected graph in G(E, V) is O (V log V) O (E + V log V) O (E log V) O (V log V + E log V) Where E, V are respectively number of edges & vertices in the graph.

The least running time of creating spanning tree from connected graph in G(E, V) is O (V log V) O (E + V log V)O (E log V) O (V log V + E log V)Where E, V are respect...

gatecse

491 views

gatecse asked Aug 4, 2019

2 votes

2 answers

63

UGC NET CSE | June 2019 | Part 2 | Question: 61
Match List-I with List-II: ... ii) (a) - (ii); (b)-(i); (c)-(iv); (d)-(iii) (a) - (iii); (b)-(i); (c)-(iv); (d)-(ii)

Match List-I with List-II:$$\begin{array}{|c|c|c|c|} \hline {} & \text{List-I} & {} & \text{List-II} \\ \hline (a) & \text{Prim’s algorithm} & (i) & O(V^3 \log V) \\ \h...

Arjun

1.7k views

Arjun asked Jul 2, 2019

4 votes

3 answers

64

GEEKS FOR GEEKS GATE 2017 MOCK
If Kruskal’s algorithm is used for finding a minimum spanning tree of a weighted graph G with n vertices and m edges and edge weights are already given in a sorted list, then, What will be the time complexity to compute the minimum cost spanning tree given that union and find operations take amortized O(1) ? A O(m logn) B O(n) C O(m) D O(n logm)

If Kruskal’s algorithm is used for finding a minimum spanning tree of a weighted graph G with n vertices and m edges and edge weights are already given in a sorted list...

Hirak

3.6k views

Hirak asked Jun 9, 2019

0 votes

1 answer

65

Doubt on Bipartite Graph
What is T.C. to find maximum number of edges to be added to a tree so that it stays as a bipartite graph? Now my question is, why do we need to add edges to make a tree bipartite? A tree is already bipartite graph. Right?? Again how do we add edges in it?? Is BFS or DFS do any improvement in such a tree?? How to think such a question??

What is T.C. to find maximum number of edges to be added to a tree so that it stays as a bipartite graph?Now my question is, why do we need to add edges to make a tree b...

srestha

629 views

srestha asked Jun 2, 2019

0 votes

1 answer

66

Made Easy Test Series:Algorithm- Minimum Weight Path
Consider the following statement: $A)$ If all edge weight of a graph are positive then any subset of edges that connect all vertices and has minimum total weight is a tree. $B)$ ... minimum weight graph?? and what about B)?? Is it just saying each minimum path between $2$ vertices makes total shortest path??

Consider the following statement:$A)$ If all edge weight of a graph are positive then any subset of edges that connect all vertices and has minimum total weight is a tree...

srestha

459 views

srestha asked May 10, 2019

2 votes

1 answer

67

Difference between DAG and Multi-stage graph
I have trouble understanding the difference between DAG and Multi-stage graph. I know what each of them is But I think that a multi-stage graph is also a DAG. Are multi-stage graphs a special kind of DAG?

I have trouble understanding the difference between DAG and Multi-stage graph. I know what each of them isBut I think that a multi-stage graph is also a DAG. Are multi-st...

gmrishikumar

846 views

gmrishikumar asked Apr 28, 2019

0 votes

0 answers

68

Cormen Edition 3 Exercise 22.1 Question 8 (Page No. 593)
Suppose that instead of a linked list, each array entry $adj[u]$ is a hash table containing the vertices $v$ for which $(u,v) \in E$. If all edge lookups are equally likely, what is the expected ... alternate data structure for each edge list that solves these problems. Does your alternative have disadvantages compared to the hash table ?

Suppose that instead of a linked list, each array entry $adj[u]$ is a hash table containing the vertices $v$ for which $(u,v) \in E$. If all edge lookups are equally like...

akash.dinkar12

252 views

akash.dinkar12 asked Apr 7, 2019

0 votes

0 answers

69

Cormen Edition 3 Exercise 22.1 Question 6 (Page No. 593)
Most graph algorithms that take an adjacency-matrix representation as input require time $\Omega(V^2)$,but there are some exceptions. Show how to determine whether a directed graph $G$ contains a universal link $-$ a vertex with in-degree $|V-1|$ and out-degree $0$ in time $O(V)$ , given an adjacency matrix for $G$.

Most graph algorithms that take an adjacency-matrix representation as input require time $\Omega(V^2)$,but there are some exceptions. Show how to determine whether a dire...

akash.dinkar12

267 views

akash.dinkar12 asked Apr 7, 2019

0 votes

0 answers

70

Cormen Edition 3 Exercise 22.1 Question 5 (Page No. 593)
The square of a directed graph $G=(V,E)$ is the graph $G^2=(V,E^2)$ such that $(u,v) \in E^2$ if and only $G$ contains a path with at most two edges between $u$ and $v$ .Describe efficient algorithms for computing $G^2$ and $G$ for both the adjacency list and adjacency-matrix representations of G. Analyze the running times of your algorithms.

The square of a directed graph $G=(V,E)$ is the graph $G^2=(V,E^2)$ such that $(u,v) \in E^2$ if and only $G$ contains a path with at most two edges between $u$ and $v$ ....

akash.dinkar12

289 views

akash.dinkar12 asked Apr 7, 2019

0 votes

1 answer

71

Cormen Edition 3 Exercise 22.1 Question 4 (Page No. 593)
Given an adjacency-list representation of a multi graph $G=(V,E)$, describe an $O(V+E)$ time algorithm to compute the adjacency-list representation of the equivalent undirected graph $G'=(V,E')$ , where $E'$ is ... the edges in $E$ with all multiple edges between two vertices replaced by a single edge and with all self-loops removed.

Given an adjacency-list representation of a multi graph $G=(V,E)$, describe an $O(V+E)$ time algorithm to compute the adjacency-list representation of the “equivalent�...

akash.dinkar12

1.1k views

akash.dinkar12 asked Apr 7, 2019

1 votes

1 answer

72

Cormen Edition 3 Exercise 22.1 Question 3 (Page No. 592)
The transpose of a directed graph $G=(V,E)$ is the graph $G^T=(V,E^T)$, where $E^T=\{(v,u) \in V * V :(u,v) \in E \ \}$ .Thus ,$G^T$ is $G$ with all its edges reversed . Describe ... algorithms for computing $G^T$ from $G$,for both the adjacency list and adjacency matrix representations of $G$. Analyze the running times of your algorithms.

The transpose of a directed graph $G=(V,E)$ is the graph $G^T=(V,E^T)$, where $E^T=\{(v,u) \in V * V :(u,v) \in E \ \}$ .Thus ,$G^T$ is $G$ with all its edges reversed . ...

akash.dinkar12

4.4k views

akash.dinkar12 asked Apr 7, 2019

0 votes

1 answer

73

Cormen Edition 3 Exercise 22.1 Question 2 (Page No. 592)
Give an adjacency-list representation for a complete binary tree on $7$ vertices. Give an equivalent adjacency-matrix representation. Assume that vertices are numbered from $1\ to\ 7$ as in a binary heap.

Give an adjacency-list representation for a complete binary tree on $7$ vertices. Give an equivalent adjacency-matrix representation. Assume that vertices are numbered fr...

akash.dinkar12

1.2k views

akash.dinkar12 asked Apr 7, 2019

0 votes

1 answer

74

Cormen Edition 3 Exercise 22.1 Question 1 (Page No. 592)
Given an adjacency-list representation of a directed graph, how long does it take to compute the out-degree of every vertex ? How long does it take to compute the in-degrees ?

Given an adjacency-list representation of a directed graph, how long does it take to compute the out-degree of every vertex ? How long does it take to compute the in-degr...

akash.dinkar12

361 views

akash.dinkar12 asked Apr 7, 2019

0 votes

0 answers

75

GATE | GATE-CS-2003
Let G be an arbitrary graph with n nodes and k components. If a vertex is removed from G, the number of components in the resultant graph must necessarily lie between (A) k and n (B) k – 1 and k + 1 (C) k – 1 and n – 1 (D) k + 1 and n – k The answer is C . how is it k-1?? I mean if we have only one component .?Please explain

Let G be an arbitrary graph with n nodes and k components. If a vertex is removed from G, the number of components in the resultant graph must necessarily lie between(A) ...

Doraemon

700 views

Doraemon asked Mar 31, 2019

0 votes

0 answers

76

CLRS CHAPTER 25
FOR THE EXTENDED-SHORTEST-PATH if we want to find the distance between 1->4 and the 1->5 +5->4 gives the shortest path and if 1->5 gets its shortest path as 1->2->5 and 5>4 gets its shortest path as 5->3->4 then how will we get it?? as one of the operands is always from the initial array.

FOR THE EXTENDED-SHORTEST-PATH if we want to find the distance between 1->4 and the 1->5 +5->4 gives the shortest path and if 1->5 gets its shortest path as 1->2->5 and ...

Doraemon

260 views

Doraemon asked Mar 30, 2019

1 votes

1 answer

77

CLRS Chapter-22 Figure-22.6
What are the strongly connected components in the above figure ?

What are the strongly connected components in the above figure ?

Doraemon

773 views

Doraemon asked Mar 30, 2019

0 votes

2 answers

78

Made Easy Workbook
Suppose that you are running Dijkstra’s algorithm on the edge-weighted diagram below, starting from vertex A. The Table gives ‘Distance’ and ‘Parent’ entry of each vertex after vertex E has been deleted from the priority queue and relaxed. Vertex Distance Parent A 0 Null B 2 A C 13 F D 23 A E 11 F F 7 B G 36 F H 19 E What could be the possible value of expression x+y?

Suppose that you are running Dijkstra’s algorithm on the edge-weighted diagram below, starting from vertex A. The Table gives ‘Distance’ and ‘Parent’ entry of ...

noob_coder

2.2k views

noob_coder asked Mar 10, 2019

1 votes

2 answers

79

BFS traversal path
What will be the path from A-H if BFS is used in the following graph?

What will be the path from A-H if BFS is used in the following graph?

saptarshiDey

857 views

saptarshiDey asked Feb 1, 2019

0 votes

2 answers

80

made easy
can anyone explain how dijkstras will behave as BFS whwn a graph is unweighted?

can anyone explain how dijkstras will behave as BFS whwn a graph is unweighted?

screddy1313

709 views

screddy1313 asked Jan 26, 2019

0 votes

1 answer

81

made easy test series question on MST

Shankar Kakde

528 views

Shankar Kakde asked Jan 17, 2019

0 votes

1 answer

82

toplogical sort
none

none

gate_forum

461 views

gate_forum asked Jan 13, 2019

0 votes

1 answer

83

MadeEasy Test Series 2019: Algorithms - Graph Algorithms
Which is the best data structure to implement topological sort on directed graph? Heap Stack queue Array

Which is the best data structure to implement topological sort on directed graph?HeapStackqueueArray

Nandkishor3939

1.5k views

Nandkishor3939 asked Jan 5, 2019

0 votes

0 answers

84

UPPCL AE 2018:56
The Adjacency matrix of a directed graph $\text{G}$ ... $(h, c, a, e, f, d, i, g, b)$ $(c, a, d, e, f, g, h, i, b)$

The Adjacency matrix of a directed graph $\text{G}$ is given below.$\begin{array} {} & a & b & c & d & e & f & g & h & i \\ a & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ b & ...

admin

218 views

admin asked Jan 5, 2019

1 votes

2 answers

85

MadeEasy Test Series: Algorithms - Graph Algorithms
Which of the following statement is true? For a directed graph, the absence of back edges in a DFS tree can have cycle. If all edge in a graph have distinct weight then the shortest path between two vertices is unique. The depth of any DFS ( ... tree rooted at a vertex is atleast as depth of any BFS tree rooted at the same vertex. Both (a) and (c)

Which of the following statement is true?For a directed graph, the absence of back edges in a DFS tree can have cycle.If all edge in a graph have distinct weight then the...

Abhishek Kumar 38

2.6k views

Abhishek Kumar 38 asked Jan 4, 2019

0 votes

1 answer

86

UGC NET CSE | December 2018 | Part 2 | Question: 27
Match $\text{List I}$ with $\text{List II}$ ... $\text{(a)-(iii), (b)-(i), (c)-(iv), (d)-(ii)}$

Match $\text{List I}$ with $\text{List II}$ and choose the correct answer from the code given below.$\begin{array} {clcl} & \textbf{List I} & & \textbf{List II} \\ & \...

Arjun

1.8k views

Arjun asked Jan 2, 2019

0 votes

0 answers

87

Zeal Test Series 2019: Algorithms - Graph Algorithms
If the DFS finishing time f[u] < f[v] for two vertices u and v in a directed graph G, and u and v are in the same DFS tree in the DFS forest, then u is an ancestor of v in the depth first tree ? True /False can anyone explain it ?

If the DFS finishing time f[u] < f[v] for two vertices u and v in a directed graph G, and u and v are in the same DFS tree in the DFS forest, then u is an ancestor of v i...

Prince Sindhiya

860 views

Prince Sindhiya asked Jan 2, 2019

1 votes

0 answers

88

BFS and DFS - types of edges
Can someone please explain what are the types of edges possible in BFS and DFS for DIRECTED as well as UNDIRECTED graphs? Individual meaning of BACK, FRONT and CROSS edges is clear, but can’t decide which are present and which are not for Traversals. an example would be of great help or any specific reference on this.

Can someone please explain what are the types of edges possible in BFS and DFS for DIRECTED as well as UNDIRECTED graphs?Individual meaning of BACK, FRONT and CROSS edges...

Markzuck

1.4k views

Markzuck asked Dec 30, 2018

4 votes

1 answer

89

GATE Overflow | Mock GATE | Test 1 | Question: 47
Which of the following statements is/are correct with respect to Djikstra Algorithm? (P) It always works perfectly for graphs with negative weight edges. (Q) It does not work perfectly for graphs with negative weight cycles. (R) It may or may not work for graphs ... , S, T and U are correct Only Q, R, T are correct Only Q, R, S, T and U are correct

Which of the following statements is/are correct with respect to Djikstra Algorithm?(P) It always works perfectly for graphs with negative weight edges.(Q) It does not wo...

Ruturaj Mohanty

1.6k views

Ruturaj Mohanty asked Dec 27, 2018

0 votes

0 answers

90

MadeEasy Test Series: Algorithms - Graph Algorithms
According To Me Answer Should Be 6… Anyone Please Try Once!!! Given Is 5 With No Explaination !!!! like 11-12-12 then for second square 4 times 13 so c(4,2) any two of then lead to me @ answer @6.

According To Me Answer Should Be 6… Anyone Please Try Once!!! Given Is 5 With No Explaination !!!!like 11-12-12 then for second square 4 times 13 so c(4,2) any two of t...

CHïntän ÞäTël

370 views

CHïntän ÞäTël asked Dec 25, 2018

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