GATE CSE 2026 Set 2 | Graphs Question 1 | Data Structures

GATE CSE 2026 Set 2

MCQ (Single Correct Answer)

-0

Let $G$ be a weighted directed acyclic graph with $m$ edges and $n$ vertices. Given $G$ and a source vertex $s$ in $G$, which one of the following options gives the worst case time complexity of the fastest algorithm to find the lengths of shortest paths from $s$ to all vertices that are reachable from $s$ in $G$ ?

$\theta(m+n)$

$\theta(m+n \log (n))$

$\theta(n m)$

$\theta\left(n^3\right)$

GATE CSE 2026 Set 1

MCQ (More than One Correct Answer)

-0

Consider the following pseudocode for depth-first search (DFS) algorithm which takes a directed graph $G(V, E)$ as input, where $d[v]$ and $f[v]$ are the discovery time and finishing time, respectively, of the vertex $v \in V$.

DFS(G):
unmark all v ∈ V
t ← 0
for each v ∈ V
    if v is unmarked
        t ← Explore(G, v, t)
    end if
end for

Explore(G, v, t):
    mark v
    t ← t + 1
    d[v] ← t
    for each (v, w) ∈ E
        if w is unmarked
            t ← Explore(G, w, t)
        end if
    end for
    t ← t + 1
    f[v] ← t
    return t

Suppose that the input directed graph $G(V, E)$ is a directed acyclic graph (DAG). For an edge $(u, v) \in E$, which of the following options will NEVER be correct?

$d[u] < d[v] < f[v] < f[u]$

$d[v] < d[u] < f[u] < f[v]$

$d[v] < f[v] < d[u] < f[u]$

$d[u] < d[v] < f[u] < f[v]$

GATE CSE 2026 Set 1

MCQ (More than One Correct Answer)

-0

An undirected, unweighted, simple graph $G(V, E)$ is said to be 2 -colorable if there exists a function $c: V \rightarrow\{0,1\}$ such that for every $(u, v) \in E, c(u) \neq c(v)$.

Which of the following statements about 2-colorable graphs is/are true?

If $G$ is 2-colorable, then $G$ may contain cycles of odd length

If $G$ is 2 -colorable, then $G$ may contain cycles of even length

An optimal algorithm for testing whether $G$ is 2-colorable runs in time $\theta(|V|+|E|)$, if $G$ is represented as an adjacency list

An optimal algorithm for testing whether $G$ is 2-colorable runs in time $\theta(|E| \log |V|)$, if $G$ is represented as an adjacency list

GATE CSE 2025 Set 2

Numerical

-0

Consider the following algorithm someAlgo that takes an undirected graph $G$ as input. someAlgo ( $G$ )

1. Let $v$ be any vertex in $G$. Run BFS on $G$ starting at $v$. Let $u$ be a vertex in $G$ at maximum distance from $v$ as given by the BFS.

2. Run BFS on $G$ again with $u$ as the starting vertex. Let $z$ be the vertex at maximum distance from $u$ as given by the BFS.

3. Output the distance between $u$ and $z$ in $G$.