Dark Mode

Recent questions tagged depth-first-search

2 votes

1 answer

61

Hamiltonian
A graph is said to be hamiltonian if it contains a cycle containing all vertices. Any DFS tree on the graph must have depth v-1 true or false

A_i_$_h asked in Algorithms Sep 18, 2017

1.0k views

3 votes

2 answers

62

Graph_Traversal

Gate Ranker18 asked in DS Aug 30, 2017

by Gate Ranker18

646 views

0 votes

1 answer

63

CLRS 22.3.1
Make a 3-by-3 chart with row and column labels WHITE, GRAY, and BLACK. In each cell ( , ) ij , indicate whether, at any point during a depth-first search of a directed graph, there can be an edge from a vertex of color i to a vertex of color j . For each possible edge, indicate what types it can be.

sarika asked in Algorithms Aug 21, 2017

by sarika

1.7k views

0 votes

1 answer

64

DFS back edge
If a directed graph G is cyclic but can be made acyclic by removing 1 edge then a DFS will encounter exactly 1 Backedge. True or false ?

Xylene asked in Programming in C Aug 20, 2017

by Xylene

2.5k views

1 vote

1 answer

65

Kuldeep Pal asked in Algorithms Jul 16, 2017

364 views

0 votes

1 answer

66

ME Testseries
how many of the above statements are true?

Shubhanshu asked in Algorithms Mar 13, 2017

320 views

0 votes

1 answer

67

Vertex degrees
Let G be a simple undirected graph such that G contains only vertex 'u' of maximum degree and let D be a DFS tree of G such that D contains only vertex 'v' of maximum degree. Which of the following is True? [ A ] 'u' is same ... loops, hence having a degree of 2n. But the dfs tree should have just one vertex with a single self loop in this case, right?

Krunal2016 asked in Algorithms Feb 3, 2017

279 views

1 vote

2 answers

68

madeasy
Consider the vertices V1 and V2 that are simultaneously on the function call stack at some point during the execution of depthfirst search from vertex s in a digraph. Which of the following must be true? I. There exist directed path from s to V1 and directed path from ... from V1 to V2 then there exist a directed path from V2 to V1 . The number of above statements is/are true ________ .

shefali1 asked in Algorithms Feb 1, 2017

465 views

1 vote

1 answer

69

Test by Bikram | Mock GATE | Test 2 | Question: 29
Given a graph $G$ with vertex set $V$ and edge set $E$, which of the following statements is/are correct about graph $G$? If $G$ is directed and acyclic, the asymptotic algorithmic complexity of topological sort on $G$ is $O$\left ... ancestors to descendants), and cross edges (all other remaining links). I only III only I and II only I, II and III

Bikram asked in GATE Jan 24, 2017

by Bikram

855 views

3 votes

2 answers

70

Test by Bikram | Mock GATE | Test 2 | Question: 27
Let $T$ be a depth-first search tree of a connected undirected graph $G$. For each vertex $v$ of $T$, Let pre$\left ( v \right )$ be the number of nodes visited up to and including $v$ during a preorder traversal of $T$ ... is the lowest common ancestor of $u$ and $v$ in $T$, then $w = u$. II only III only I and II II and III

Bikram asked in GATE Jan 24, 2017

by Bikram

806 views

5 votes

2 answers

71

Tree DFS
int func(Node root) { if(root == NULL) return 0; else if(root->left == NULL && root->right == NULL) return 2; else return(3 + func(root->left) + func(root->right)); } Above code is executed on the following rooted tree. What will be the output?

dd asked in Programming in C Jan 13, 2017

by dd

982 views

3 votes

3 answers

72

Testbook Test Series: Programming & DS - Graphs

focus _GATE asked in Programming in C Jan 11, 2017

761 views

0 votes

1 answer

73

Programming & DS [BFS Cross Edges]
Please tell what is difference between Back edge and cross edge?

rahul sharma 5 asked in Programming in C Dec 19, 2016

by rahul sharma 5

868 views

0 votes

1 answer

74

representation of connected component

iita asked in Algorithms Dec 17, 2016

by iita

396 views

12 votes

4 answers

75

GATE CSE 1989 | Question: 4-vii
In the graph shown above, the depth-first spanning tree edges are marked with a $’ T’$. Identify the forward, backward, and cross edges.

makhdoom ghaya asked in Algorithms Nov 30, 2016

by makhdoom ghaya

2.7k views

2 votes

1 answer

76

DFS based question
How many times 8 is pushed into stack ? a detail answer will be welcomed.

vishwa ratna asked in Programming in C Nov 10, 2016

by vishwa ratna

2.5k views

0 votes

1 answer

77

graph algorithm
Can we use DFS to detect the negetive weight cycle in a directed graph?

vaishali jhalani asked in Algorithms Nov 4, 2016

by vaishali jhalani

469 views

6 votes

1 answer

78

#Algorithm # DFS
Let G be a graph with n vertices and m edges. a. True or false: All its DFS forests (for traversals starting at different vertices) will have the same number of trees? b. True or false: All its DFS forests will have the same number of tree edges and the same number of back edges?

Geet asked in Algorithms Oct 26, 2016

by Geet

2.7k views

1 vote

4 answers

79

ME-ALGORITHM(BASIC LEVEL)-Q26
Consider the vertices a' and b' that are simultaneously on the function call stack at some point during the execution of DFS from vertices s' in diagraph. Which of the following must be true? S1: There exist directed path from s to a' and directed path from s to ... the above statements is/are true? a. S1 only b. S1 and S2 only c. S1 and S3 only d. S1, S2 and S3

KISHALAY DAS asked in Algorithms Oct 16, 2016

by KISHALAY DAS

1.8k views

1 vote

2 answers

80

#algo
If a directed graph G is cyclic but can be made acyclic by removing one edge,then a depth-first search in G will encounter exactly one back edge??

papesh asked in Algorithms Oct 8, 2016

by papesh

540 views

2 votes

3 answers

81

Data Strucutre Test

Rahul Jain25 asked in Programming in C Oct 6, 2016

by Rahul Jain25

454 views

6 votes

2 answers

82

UGC NET CSE | December 2015 | Part 2 | Question: 36
In the following graph, discovery time stamps and finishing time stamps of Depth First Search (DFS) are shown as $x/y$, where $x$ is discovery time stamp and $y$ is finishing time stamp. It shows which of the following depth first forest? {a,b,e} {c,d,f,g,h} {a,b,e} {c,d,h} {f,g} {a,b,e} {f,g} {c,d} {h} {a,b,c,d} {e,f,g} {h}

go_editor asked in Algorithms Aug 8, 2016

7.6k views

3 votes

1 answer

83

#dfs
An undirected graph said to be hamiltonian if it has cycle containing all the vertices. Any DFS tree on a hamiltonian graph must have depth V-1 ? true of false

Sunny123 asked in Algorithms Aug 7, 2016

2.0k views

1 vote

0 answers

84

MadeEasy Test Series 2015: Algorithms - Graph Algorithms
Here i have option III is doubt.how option III always correct.one counter example is if i choose a tree where s is root node and v1& v2 are its child node then above question property i.e the vertices V1 and V2 that are simultaneously ... from vertex s in a digraph is satisfies.but there is no any path from v1 to v2 or from v2 to v1.

dileswar sahu asked in Algorithms Jul 19, 2016

by dileswar sahu

817 views

3 votes

3 answers

85

UGC NET CSE | June 2013 | Part 3 | Question: 68
Which one of the following is not an informed search technique? Hill climbing search Best first search A* search Depth first search

go_editor asked in Algorithms Jul 19, 2016

5.1k views

2 votes

1 answer

86

Ace Test Series: Algorithms - Graph Algorithms

CKgurav asked in Algorithms Feb 1, 2016

833 views

1 vote

2 answers

87

DFS

Mojo-Jojo asked in DS Jan 8, 2016

1.2k views

3 votes

2 answers

88

Dfs
Consider the vertices $V1$ and $V2$ that are simultaneously on the function call stack at some point during the execution of depth -first search from vertex $S$ in a digraph.Which of the following must be true? I. There exist directed path from $s$ to $V_1$ and directed path ... from $V_1$ to $V_2$ then there exist a directed path from $V_2$ to $V_1$ . Which of the above statement is/are true?

sourabh asked in Algorithms Jan 4, 2016

879 views

0 votes

2 answers

89

Problem on DFS
Answer given: C Please explain

shikharV asked in Algorithms Nov 15, 2015

830 views

1 vote

1 answer

90

Edge type in Undirected Graphs on Depth First Tree
Assume WHITE vertices that are yet to be discovered, BLACK vertices are finished vertices and GRAY vertices are frontier betweeen WHITE and BLACK in Depth First Search. Now, What are the various edge types like TREE-EDGE and BACK-EDGE possible between ... edge type between WHITE and GRAY type vertices. [ CLRS (3rd Edition) : 22-3:1; Page # 610 ]

Salman asked in Algorithms Oct 21, 2015

by Salman

570 views

Page:

Recent questions tagged depth-first-search