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?

Figure for GATE CSE 2017 | Set 2 | Question 15

Single correct

Answer key coming soon

Source: GATE CSE 2017 Set 2, IIT Roorkee. Official question paper.

GATE CSE 2016 | Set 1 | Question 11

Graph Algorithms·Graph Theory

NAT1 mark

Consider the following directed graph: The number of different topological orderings of the vertices of the graph is ________.

Figure for GATE CSE 2016 | Set 1 | Question 11

Numerical answer

Your answer

Answer key coming soon

Source: GATE CSE 2016 Set 1, IISc Bengaluru. Official question paper.

GATE CSE 2016 | Set 1 | Question 14

Graph Algorithms

MCQ1 mark

Let

G

be a weighted connected undirected graph with distinct positive edge weights. If every edge weight is increased by the same value, then which of the following statements is/are TRUE? P: Minimum spanning tree of

G

does not change Q: Shortest path between any pair of vertices does not change

Single correct

Answer key coming soon

Source: GATE CSE 2016 Set 1, IISc Bengaluru. Official question paper.

GATE CSE 2016 | Set 1 | Question 38

Graph Algorithms

NAT2 marks

Consider the weighted undirected graph with 4 vertices, where the weight of edge

\{i, j\}

is given by the entry

W_{ij}

in the matrix

W

W = \begin{bmatrix} 0 & 2 & 8 & 5 \\ 2 & 0 & 5 & 8 \\ 8 & 5 & 0 & x \\ 5 & 8 & x & 0 \end{bmatrix}

The largest possible integer value of

x

, for which at least one shortest path between some pair of vertices will contain the edge with weight

x

is ________.

Numerical answer

Your answer

Answer key coming soon

Source: GATE CSE 2016 Set 1, IISc Bengaluru. Official question paper.

GATE CSE 2016 | Set 1 | Question 39

Graph Algorithms

NAT2 marks

Let

G

be a complete undirected graph on 4 vertices, having 6 edges with weights being 1, 2, 3, 4, 5, and 6. The maximum possible weight that a minimum weight spanning tree of

G

can have is ________.

Numerical answer

Your answer

Answer key coming soon

Source: GATE CSE 2016 Set 1, IISc Bengaluru. Official question paper.

GATE CSE 2016 | Set 1 | Question 40

Graph Algorithms

MCQ2 marks

G = (V, E)

is an undirected simple graph in which each edge has a distinct weight, and

e

is a particular edge of

G

. Which of the following statements about the minimum spanning trees (MSTs) of

G

is/are TRUE? I. If

e

is the lightest edge of *some* cycle in

G

, then every MST of

G

*includes*

e

II. If

e

is the heaviest edge of *some* cycle in

G

, then every MST of

G

*excludes*

e

Single correct

Answer key coming soon

Source: GATE CSE 2016 Set 1, IISc Bengaluru. Official question paper.

GATE CSE 2016 | Set 2 | Question 11

Trees & BST·Graph Algorithms

NAT1 mark

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 ________.

Numerical answer

Your answer

Answer key coming soon

Source: GATE CSE 2016 Set 2, IISc Bengaluru. Official question paper.

GATE CSE 2016 | Set 2 | Question 41

Graph Algorithms

MCQ2 marks

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 a pointer from an adjacency list entry to its twin. If

|E| = m

and

|V| = n

, and the memory size is not a constraint, what is the time complexity of the most efficient algorithm to set the twin pointer in each entry in each adjacency list?

Single correct

Answer key coming soon

Source: GATE CSE 2016 Set 2, IISc Bengaluru. Official question paper.

GATE CSE 2015 | Set 1 | Question 51

Graph Algorithms

MCQ2 marks

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

x

. A breadth first search (BFS) is performed starting at

s

. Let

T

be the resultant BFS tree. If

(u, v)

is an edge of

G

that is not in

T

, then which one of the following CANNOT be the value of

d(u) - d(v)

Single correct

Source: GATE CSE 2015 Set 1, IIT Kanpur. Official question paper and answer key.

GATE CSE 2015 | Set 1 | Question 63

Graph Algorithms

NAT2 marks

The graph shown below has 8 edges with distinct integer edge weights. The minimum spanning tree (MST) is of weight 36 and contains the edges: {(A, C), (B, C), (B, E), (E, F), (D, F)}. The edge weights of only those edges which are in the MST are given in the figure shown below. The minimum possible sum of weights of all 8 edges of this graph is _____.

Figure for GATE CSE 2015 | Set 1 | Question 63

Numerical answer

Your answer

Source: GATE CSE 2015 Set 1, IIT Kanpur. Official question paper and answer key.

Previous pageUse ← → to move

Questions

52 total

Correct Wrong Answer seen

1 2 3

Sort

Filters

Year

Set

Set

Marks

Marks

Question type

Question type