GATE 2026 Algorithms PYQs | GRAPH TECHNIQUES (JavaScript)

Title: GATE 2026 Algorithms PYQs | GRAPH TECHNIQUES (JavaScript)

Why This Matters

Graph techniques are essential for solving complex problems in various fields, including computer science, mathematics, and data science. The Graduate Aptitude Test in Engineering (GATE) is a prestigious exam that tests your understanding of algorithms, and graph techniques are an important part of it. In this lesson, we will learn about graph techniques using JavaScript, focusing on practical depth for real-world scenarios.

Prerequisites

To understand this lesson, you should be familiar with the following topics:

1. Basic JavaScript syntax (variables, functions, loops, and control structures)
2. Data Structures (Arrays, Objects)
3. Understanding of basic graph concepts such as vertices, edges, adjacency lists, and adjacency matrices
4. Familiarity with Big O notation to understand time complexity of algorithms
5. Basic understanding of tree data structures and traversal techniques (pre-requisite for BFS and DFS)
6. Knowledge of sorting algorithms (pre-requisite for Kruskal's algorithm)

Core Concept

Graph Representation in JavaScript

In JavaScript, we can represent a graph using adjacency lists or adjacency matrices. Adjacency lists are more memory-efficient for large graphs, while adjacency matrices are easier to implement for smaller graphs.

Adjacency List

An adjacency list is an array of arrays where each subarray represents the neighbors of a vertex. Here's an example:

const graph = [
[], // Vertex 0
[1], // Vertex 1 has one neighbor, Vertex 0
[0, 2], // Vertex 2 has two neighbors, Vertices 0 and 1
];

Adjacency Matrix

An adjacency matrix is a square matrix where the element (i, j) indicates whether there's an edge from vertex i to vertex j. If there's an edge, the value is 1; otherwise, it's 0. Here's an example for our small graph:

const graphMatrix = [
[0, 0, 1], // Vertex 0 has no edges with itself and has one edge to Vertex 2
[1, 0, 0], // Vertex 1 has one edge with itself and no edges with other vertices
[1, 0, 0] // Vertex 2 has one edge with itself and no edges with other vertices (already represented in the adjacency list)
];

Common Graph Algorithms

Breadth-First Search (BFS)

BFS is an algorithm for traversing or searching tree, graph, or network structures. It starts at the root (or some arbitrary node) and explores all of the neighbor nodes at the present depth prior to moving on to nodes at the next depth level. BFS has a time complexity of O(V + E), where V is the number of vertices and E is the number of edges in the graph.

BFS can be implemented using a queue data structure.

Depth-First Search (DFS)

DFS is another algorithm for traversing or searching graph, tree, or network structures. It explores as far as possible along each branch before backtracking. DFS also has a time complexity of O(V + E).

DFS can be implemented using a stack data structure or recursively.

Minimum Spanning Tree (MST)

An MST is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight. Kruskal's and Prim's algorithms are commonly used for finding the MST in a graph. Both algorithms have a time complexity of O(E log E) or O(E log V), depending on the implementation.

Kruskal's Algorithm

Kruskal's algorithm sorts the edges and then builds the MST by adding edges that connect different components, maintaining a disjoint set data structure to represent the connected components of the graph.

Prim's Algorithm

Prim's algorithm starts with an arbitrary vertex and grows the MST by repeatedly adding the smallest edge that connects the MST to a new vertex. It uses a priority queue to store vertices with their minimum distances from the starting vertex.

Worked Example

Let's consider a simple example of a graph:

const graph = [
[], // Vertex 0
[2], // Vertex 1 has one neighbor, Vertex 2
[0, 3], // Vertex 2 has two neighbors, Vertices 0 and 3
[1, 3] // Vertex 3 has two neighbors, Vertices 1 and 3
];

We can implement BFS and DFS for this graph using JavaScript:

function bfs(graph, start) {
const visited = new Set();
const queue = [start];

while (queue.length > 0) {
const current = queue.shift();

if (!visited.has(current)) {
console.log(current);
visited.add(current);

for (const neighbor of graph[current]) {
if (!visited.has(neighbor)) {
queue.push(neighbor);
}
}
}
}
}

function dfs(graph, current, visited = new Set()) {
visited.add(current);
console.log(current);

for (const neighbor of graph[current]) {
if (!visited.has(neighbor)) {
dfs(graph, neighbor, visited);
}
}
}

bfs(graph, 0); // Output: 0 1 2 3
console.log();
dfs(graph, 0); // Output: 0 2 1 3

Common Mistakes

1. Not initializing the visited set in BFS and DFS implementations.
2. Forgetting to check if a vertex has been visited before adding it to the queue or stack during BFS and DFS traversals.
3. Misunderstanding the difference between BFS and DFS, and using the wrong algorithm for a given problem.
4. Not considering edge weights in MST algorithms like Kruskal's or Prim's algorithms.
5. Failing to properly implement the disjoint set data structure in Kruskal's algorithm.
6. Mismanaging memory during the implementation of BFS and DFS, leading to time complexity degradation.
7. Not sorting the edges before implementing Kruskal's or Prim's algorithms for finding the MST.
8. Implementing BFS and DFS incorrectly by not correctly updating the visited status of vertices during traversal.

Practice Questions

1. Implement DFS recursively for the given graph:

const graph = [
[], // Vertex 0
[2], // Vertex 1 has one neighbor, Vertex 2
[0, 3], // Vertex 2 has two neighbors, Vertices 0 and 3
[1, 3] // Vertex 3 has two neighbors, Vertices 1 and 3
];

1. Implement BFS using a queue for the same graph as in the practice question above.

1. Implement Prim's algorithm to find the minimum spanning tree (MST) of the following edge-weighted graph:

const edges = [
[0, 1, 10], // Edge between Vertex 0 and Vertex 1 with weight 10
[0, 2, 5], // Edge between Vertex 0 and Vertex 2 with weight 5
[1, 2, 3], // Edge between Vertex 1 and Vertex 2 with weight 3
[1, 3, 1], // Edge between Vertex 1 and Vertex 3 with weight 1
[2, 3, 4] // Edge between Vertex 2 and Vertex 3 with weight 4
];

1. Implement Kruskal's algorithm to find the minimum spanning tree (MST) of the same edge-weighted graph as in practice question 3.

FAQ

What is the time complexity of BFS and DFS?

• Both BFS and DFS have an average-case and worst-case time complexity of O(V + E), where V is the number of vertices and E is the number of edges in the graph.

How do I implement Prim's algorithm for finding the minimum spanning tree (MST) of a graph?

• To implement Prim's algorithm, maintain a priority queue to store the vertices with their minimum distances from the starting vertex. Start by adding the starting vertex and its distance (0) to the priority queue. Then, repeatedly extract the smallest-distance vertex from the priority queue, add it to the MST, and update the distances of its neighbors that are not yet in the MST.

How do I implement Kruskal's algorithm for finding the minimum spanning tree (MST) of a graph?

• To implement Kruskal's algorithm, sort the edges in non-decreasing order of their weights. Then, maintain a disjoint set data structure to represent the connected components of the graph. Start by adding the smallest edge that connects two different components to the MST and update the connected components accordingly. Repeat this process until all vertices are part of the MST.

What is the difference between BFS and DFS?

• BFS explores all neighbor nodes at a given depth before moving on to the next level, while DFS explores as far as possible along each branch before backtracking. This leads to different traversal patterns and use cases for each algorithm.

What is the time complexity of Kruskal's and Prim's algorithms?

• Both Kruskal's and Prim's algorithms have a time complexity of O(E log E) or O(E log V), depending on the implementation. The main difference between them lies in their traversal patterns (depth-first for DFS-based Prim's, breadth-first for edge-sorting based Kruskal's).

How do I sort edges efficiently for Kruskal's and Prim's algorithms?

• You can use a sort algorithm like quicksort or mergesort to sort the edges efficiently in O(E log E) time. If you have a small number of edges (O(V^2)), it might be faster to use a simple linear sorting algorithm like bubble sort or insertion sort.