Dark Mode

Recent questions tagged graph-algorithms

1 vote

1 answer

31

IIT Kanpur written
If a graph has k-independent components, it it n-k+1 colorable

Shreya Roy asked in Algorithms Feb 28, 2017

303 views

3 votes

1 answer

32

IIT Kanpur written test
Number of distinct BFS, DFS trees in a complete graph ?

Shreya Roy asked in Algorithms Feb 28, 2017

1.6k views

45 votes

5 answers

33

GATE CSE 2017 Set 1 | Question: 26
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 ... always unique. Which of the above statements is/are necessarily true? I only II only both I and II neither I nor II

Arjun asked in Algorithms Feb 14, 2017

by Arjun

12.3k views

29 votes

5 answers

34

GATE CSE 2017 Set 2 | Question: 15
The Breadth First Search (BFS) algorithm has been implemented using the queue data structure. Which one of the following is a possible order of visiting the nodes in the graph below? $\text{MNOPQR}$ $\text{NQMPOR}$ $\text{QMNROP}$ $\text{POQNMR}$

Madhav asked in Algorithms Feb 14, 2017

by Madhav

7.9k views

0 votes

0 answers

35

How to Calculate No of Simple graph with labelled vertices?
No of Simple Undirected Graph with unablled vertices - 2nC2 No of Simple Undirected Graph with labelled vertices - ? No of Simple Undirected Connected Graph with unablled vertices - ? No of Simple Undirected Connected Graph with labelled vertices - ?

yg92 asked in Programming in C Feb 5, 2017

by yg92

446 views

1 vote

2 answers

36

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

2 votes

0 answers

37

Minimum Spanning Tree
Show the different minimum spanning Trees Possible in each of the following Algorithms Prims Algorithm Kruskal

Dulqar asked in Algorithms Jan 26, 2017

by Dulqar

451 views

5 votes

3 answers

38

Difference between Kruskal's and Prim's algorithm ?
It may be the case that "Kruskal's Algorithm may not maintain connectivity while Prim's algorithm always does that" ? Any example which favours this ?

Kapil asked in Algorithms Jan 24, 2017

by Kapil

3.4k views

1 vote

1 answer

39

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

848 views

3 votes

2 answers

40

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

801 views

1 vote

2 answers

41

Minimum Spanning Tree ( TestBook Test Series 2)

biranchi asked in DS Jan 23, 2017

651 views

2 votes

1 answer

42

MadeEasy CBT 2017: Algorithms - Graph Algorithms

Dulqar asked in Algorithms Jan 22, 2017

by Dulqar

594 views

3 votes

5 answers

43

MadeEasy CBT 2017: Algorithms - Graph Algorithms
No of topological sortings

Vasu_gate2017 asked in Algorithms Jan 22, 2017

by Vasu_gate2017

2.1k views

1 vote

1 answer

44

MadeEasy Subject Test: Algorithms - Graph Algorithms
Which of the following statements is true? Adding a constant to every edge weight in a directed graph can change the set of edges that belongs to minimum cost spanning tree. Assume unique weights. Complete graph with 4 vertices, each edges ... ). None of these how is 3rd wrong? If there is no negative cycles dijkstra can work just fine right?

Pankaj Joshi asked in Algorithms Jan 20, 2017

by Pankaj Joshi

3.2k views

1 vote

1 answer

45

Dijkstra
Which of the following procedure results same output as Dijkstra’s algorithm on unweighted graph with ‘n’ vertices ? a) BFS b) DFS c) Kruskal d) Prims

srestha asked in Algorithms Jan 16, 2017

826 views

1 vote

1 answer

46

Test by Bikram | Mock GATE | Test 1 | Question: 42
Find the missing statement in the if loop of $Floyd$ algorithm. Procedure Floyd: (var A: array[1...n,1...n] of real; C: array [1...n,1...n] of real); Var i, j, k: integer; begin M for i:=l to n do for j:=l to n do A[i,j]: =C[i,j] for i:=l to n do A[i,j ]:=0 ; ... $A[i,j]: = A[i, j] + A[k,j]$ $A[i,j]: = A[j,k]+ A[j,i]$ $A[i,j]: =A[i,k] + A[i,j]$

Bikram asked in GATE Jan 16, 2017

by Bikram

540 views

1 vote

1 answer

47

thor asked in Algorithms Jan 15, 2017

by thor

310 views

1 vote

1 answer

48

Algorithms, Graph theory
How to find number of BFS and DFS traversals for any complete graph? I am trying to find a formula for it.

Krupa Rajani asked in Algorithms Jan 11, 2017

by Krupa Rajani

1.6k views

0 votes

1 answer

49

vaishali jhalani asked in Algorithms Jan 7, 2017

by vaishali jhalani

2.7k views

1 vote

2 answers

50

Travelling Salesman Problem
A)250 B)300 C)550 D)375

Shradha asked in Algorithms Jan 5, 2017

4.9k views

0 votes

0 answers

51

Targate
Here it is mentioned as a queue and not a priority queue ,what would be the answer ?

Harsh181996 asked in Algorithms Jan 5, 2017

360 views

0 votes

3 answers

52

number of record movement

iita asked in Algorithms Dec 31, 2016

by iita

335 views

1 vote

1 answer

53

verify the statment
I.The depth of a breadth-first search tree on an undirected graph G=(V,E) from an arbitrary vertex v∈V is the diameter of the graph G. (The diameter d of a graph is the smallest d such that every pair of vertices s and t have δ(s, t) ≤ d.) please veirfy this statement with explanantion and example

Akriti sood asked in Algorithms Dec 27, 2016

796 views

1 vote

1 answer

54

longest path
how can we find longest path between any pair of vertices in a garph??

Akriti sood asked in DS Dec 26, 2016

1.2k views

4 votes

1 answer

55

TIFR CSE 2017 | Part B | Question: 2
Consider the following statements: Checking if a given $undirected$ graph has a cycle is in $\mathsf{P}$ Checking if a given $undirected$ graph has a cycle is in $\mathsf{NP}$ Checking if a given $directed$ graph has a cycle is in $\mathsf{P}$ Checking ... from the following options. Only i and ii Only ii and iv Only ii, iii, and iv Only i, ii and iv All of them

go_editor asked in Algorithms Dec 23, 2016

1.2k views

0 votes

1 answer

56

representation of connected component

iita asked in Algorithms Dec 17, 2016

by iita

396 views

1 vote

1 answer

57

vaishali jhalani asked in Algorithms Dec 16, 2016

by vaishali jhalani

1.4k views

2 votes

3 answers

58

BFS vs DFS
What are some applications where only DFS can be used and BFS can`t and vice versa?

rahul sharma 5 asked in Algorithms Dec 15, 2016

by rahul sharma 5

684 views

1 vote

1 answer

59

[Algorithms] BFS Back edges
True / False? 1. For a directed graph, the absence of back edges with respect to a BFS tree implies that the graph is acyclic. 2. The depth of any DFS tree rooted at a vertex is at least as much as the depth of any BFS tree rooted at the same vertex.

rahul sharma 5 asked in Algorithms Dec 15, 2016

by rahul sharma 5

2.3k views

1 vote

1 answer

60

MadeEasy Test Series: Algorithms - Graph Algorithms

rahul sharma 5 asked in Algorithms Dec 13, 2016

by rahul sharma 5

1.0k views

Page:

« prev
1
2
3
4
5
6
7
next »

Recent questions tagged graph-algorithms