Data Structures and Algorithms

DSA Interview Questions

Prim’s Algorithm for Minimum Spanning Tree (MST)

When working with graphs, Breadth-First Search (BFS) is a fundamental algorithm used to explore nodes in a level-by-level manner. In this guide, we’ll walk through how to perform BFS on an undirected graph represented by an adjacency list, starting from vertex 0. The traversal should follow the left-to-right order as defined in the adjacency list.

Problem Statement

Given an undirected graph represented as an adjacency list adj, where adj[i] contains all the vertices directly connected to vertex i, perform a BFS traversal starting from vertex 0. Return a list representing the BFS order of visited vertices.

Example 1

Input:

				
					adj = [[1, 2], [0, 2, 3], [0, 1, 4], [1, 4], [2, 3]]

BFS Traversal Output:

				
					[0, 1, 2, 3, 4]

Explanation:

The BFS traversal begins from vertex 0. It explores the adjacent nodes level by level:

Start at vertex 0 → Traversal: [0]
Visit vertex 1 (neighbor of 0) → Traversal: [0, 1]
Visit vertex 2 (another neighbor of 0) → Traversal: [0, 1, 2]
From vertex 1, visit vertex 3 → Traversal: [0, 1, 2, 3]
From vertex 2, visit vertex 4 → Final Traversal: [0, 1, 2, 3, 4]

Example 2

Input:

				
					adj = [[1, 2], [0, 2], [0, 1, 3, 4], [2], [2]]

BFS Traversal Output:

				
					[0, 1, 2, 3, 4]

Explanation:

The BFS begins at vertex 0 and continues level by level:

Start at vertex 0 → Traversal: [0]
Visit vertex 1 → Traversal: [0, 1]
Visit vertex 2 → Traversal: [0, 1, 2]
From vertex 2, visit vertex 3 → Traversal: [0, 1, 2, 3]
Visit vertex 4 → Final Traversal: [0, 1, 2, 3, 4]

What is Breadth-First Search (BFS)?

Breadth-First Search (BFS) is a core graph traversal algorithm used to explore nodes in a systematic, level-by-level manner. It starts from a given source node and visits all of its adjacent (neighboring) nodes before moving on to their respective neighbors. This process continues until all reachable vertices have been visited.

Unlike Depth-First Search (DFS), which explores as far along a branch as possible before backtracking, BFS always explores the closest (or shallowest) vertices first. This makes it particularly suitable for scenarios where the shortest path or minimum number of steps is needed.

Several well-known algorithms rely on the BFS approach, including:

Dijkstra’s Algorithm for shortest paths,
Kahn’s Algorithm for topological sorting,
Prim’s Algorithm for Minimum Spanning Tree (with slight modifications).

Additionally, BFS is widely used in solving real-world graph problems such as:

Cycle detection in both directed and undirected graphs,
Finding the shortest path in an unweighted graph,
Level-order traversal in trees,
and many more.

BFS from a Given Source

Breadth-First Search (BFS) starts from a specific source node and systematically explores all vertices that are reachable from that source. The approach is similar to the level-order traversal of a tree.

Just like in trees—where traversal begins at the root—BFS in a graph begins at the specified source vertex and proceeds level by level, visiting all neighboring nodes before moving to the next level. To implement this traversal efficiently, a queue data structure is used.

However, unlike trees, graphs can contain cycles. This means the algorithm might encounter the same node multiple times through different paths. To prevent processing a node more than once—and to avoid infinite loops—we maintain a boolean visited array. This array keeps track of which nodes have already been visited during the traversal.

By combining the queue and visited array, BFS ensures every node is explored exactly once, making it both efficient and cycle-safe for graph traversal.

Approach to Perform BFS from a Given Source

To carry out Breadth-First Search (BFS) from a specific source node, follow the steps outlined below:

1. Initialization

Begin by enqueuing the source vertex into a queue.
Mark the source node as visited using a boolean array or set.

2. Exploration

While the queue is not empty, repeat the following steps:
Dequeue the front node from the queue.
Visit the node (e.g., print its value or store it in the result list).
For each adjacent (neighboring) vertex of the dequeued node:
If the neighbor has not been visited:
Enqueue the neighbor.
Mark it as visited to avoid revisiting it.

3. Termination

Continue the exploration process until the queue becomes empty.

This method guarantees a level-order traversal of all vertices connected to the starting node. By ensuring each vertex is visited exactly once and all neighbors are processed in order, BFS provides an efficient and reliable way to traverse graphs in a breadth-first manner.

				
					#include<bits/stdc++.h>
using namespace std;

// BFS from given source s
vector<int> bfs(vector<vector<int>>& adj)  {
    int V = adj.size();
    
    int s = 0; // source node 
    // create an array to store the traversal
    vector<int> res;

    // Create a queue for BFS
    queue<int> q;  
    
    // Initially mark all the vertices as not visited
    vector<bool> visited(V, false);

    // Mark source node as visited and enqueue it
    visited[s] = true;
    q.push(s);

    // Iterate over the queue
    while (!q.empty()) {
      
        // Dequeue a vertex from queue and store it
        int curr = q.front();
        q.pop();
        res.push_back(curr);

        // Get all adjacent vertices of the dequeued 
        // vertex curr If an adjacent has not been 
        // visited, mark it visited and enqueue it
        for (int x : adj[curr]) {
            if (!visited[x]) {
                visited[x] = true;
                q.push(x);
            }
        }
    }

    return res;
}

int main()  {

    vector<vector<int>> adj = {{1,2}, {0,2,3}, {0,4}, {1,4}, {2,3}};
    vector<int> ans = bfs(adj);
    for(auto i:ans) {
        cout<<i<<" ";
    }
    return 0;
}

				
					// Function to find BFS of Graph from given source s
import java.util.*;

class GfG {

    // BFS from given source s
    static ArrayList<Integer> bfs(
        ArrayList<ArrayList<Integer>> adj) {
        int V = adj.size();
        
        int s = 0; // source node
        // create an array to store the traversal
        ArrayList<Integer> res = new ArrayList<>();
        
        // Create a queue for BFS
        Queue<Integer> q = new LinkedList<>();
        
        // Initially mark all the vertices as not visited
        boolean[] visited = new boolean[V];
        
        // Mark source node as visited and enqueue it
        visited[s] = true;
        q.add(s);
        
        // Iterate over the queue
        while (!q.isEmpty()) {
            
            // Dequeue a vertex from queue and store it
            int curr = q.poll();
            res.add(curr);
            
            // Get all adjacent vertices of the dequeued 
            // vertex curr If an adjacent has not been 
            // visited, mark it visited and enqueue it
            for (int x : adj.get(curr)) {
                if (!visited[x]) {
                    visited[x] = true;
                    q.add(x);
                }
            }
        }
        return res;
    }
    
    public static void main(String[] args) {
        
        // create the adjacency list
        // { {2, 3, 1}, {0}, {0, 4}, {0}, {2} }
       
        ArrayList<ArrayList<Integer>> adj = new ArrayList<>();
        adj.add(new ArrayList<>(Arrays.asList(1, 2)));
        adj.add(new ArrayList<>(Arrays.asList(0, 2, 3)));       
        adj.add(new ArrayList<>(Arrays.asList(0, 4)));       
        adj.add(new ArrayList<>(Arrays.asList(1,4)));          
        adj.add(new ArrayList<>(Arrays.asList(2,3)));          
        
        
        ArrayList<Integer> ans = bfs(adj);
        for (int i : ans) {
            System.out.print(i + " ");
        }
    }
}

				
					// Function to find BFS of Graph from given source s
function bfs(adj) {
    let V = adj.length;
    let s = 0; // source node is 0
    // create an array to store the traversal
    let res = [];
    
    // Create a queue for BFS
    let q = [];
    
    // Initially mark all the vertices as not visited
    let visited = new Array(V).fill(false);
    
    // Mark source node as visited and enqueue it
    visited[s] = true;
    q.push(s);
    
    // Iterate over the queue
    while (q.length > 0) {
        
        // Dequeue a vertex from queue and store it
        let curr = q.shift();
        res.push(curr);
        
        // Get all adjacent vertices of the dequeued 
        // vertex curr If an adjacent has not been 
        // visited, mark it visited and enqueue it
        for (let x of adj[curr]) {
            if (!visited[x]) {
                visited[x] = true;
                q.push(x);
            }
        }
    }
    return res;
}
 
// Main execution
let adj = 
    [ [1,2], [0,2,3], [0,4], [1,4], [2,3]];
let src = 0;
let ans = bfs(adj);
for (let i of ans) {
    process.stdout.write(i + " ");
}

				
					# Function to find BFS of Graph from given source s
def bfs(adj):
    
    # get number of vertices
    V = len(adj)
    
    # create an array to store the traversal
    res = []
    s = 0
    # Create a queue for BFS
    from collections import deque
    q = deque()
    
    # Initially mark all the vertices as not visited
    visited = [False] * V
    
    # Mark source node as visited and enqueue it
    visited[s] = True
    q.append(s)
    
    # Iterate over the queue
    while q:
        
        # Dequeue a vertex from queue and store it
        curr = q.popleft()
        res.append(curr)
        
        # Get all adjacent vertices of the dequeued 
        # vertex curr If an adjacent has not been 
        # visited, mark it visited and enqueue it
        for x in adj[curr]:
            if not visited[x]:
                visited[x] = True
                q.append(x)
                
    return res

if __name__ == "__main__":
    
    # create the adjacency list
    # [ [2, 3, 1], [0], [0, 4], [0], [2] ]
    adj = [[1,2], [0,2,3], [0,4], [1,4], [2,3]]
    ans = bfs(adj)
    for i in ans:
        print(i, end=" ")

Output

0 1 2 3 4

BFS in a Disconnected Graph

The standard Breadth-First Search (BFS) implementation starts from a given source node and explores only the vertices that are reachable from that source. However, if the graph is disconnected, this method won’t visit all vertices—some components may remain unexplored.

To handle such cases, we need a modified approach that ensures complete traversal, even when the graph contains disconnected components.

				
					#include<bits/stdc++.h>
using namespace std;

// BFS from given source s
void bfs(vector<vector<int>>& adj, int s, 
        vector<bool>& visited, vector<int> &res) {

    // Create a queue for BFS
    queue<int> q; 

    // Mark source node as visited and enqueue it
    visited[s] = true;
    q.push(s);

    // Iterate over the queue
    while (!q.empty()) {

        // Dequeue a vertex and store it
        int curr = q.front(); 
        q.pop();
        res.push_back(curr);

        // Get all adjacent vertices of the dequeued 
        // vertex curr If an adjacent has not been 
        // visited, mark it visited and enqueue it
        for (int x : adj[curr]) {
            if (!visited[x]) {
                visited[x] = true;
                q.push(x);
            }
        }
    }
}
                      
// Perform BFS for the entire graph which maybe
// disconnected
vector<int> bfsDisconnected(vector<vector<int>>& adj) {
    int V = adj.size();

    // create an array to store the traversal
    vector<int> res;

    // Initially mark all the vertices as not visited
    vector<bool> visited(V, false); 

    // perform BFS for each node
    for (int i = 0; i < adj.size(); ++i) {
        if (!visited[i]) {
            bfs(adj, i, visited, res);
        }
    }

    return res;
}

int main()  {

    vector<vector<int>> adj = { {1, 2}, {0}, {0},
                                {4}, {3, 5}, {4}};
    vector<int> ans = bfsDisconnected(adj);
    for(auto i:ans) {
        cout<<i<<" ";
    }
    return 0;
}

				
					// BFS from given source s
import java.util.*;

class GfG {

    // BFS from given source s
    static ArrayList<Integer> 
        bfsOfGraph(ArrayList<ArrayList<Integer>> adj, 
                int s, boolean[] visited, ArrayList<Integer> res) {

        // Create a queue for BFS
        Queue<Integer> q = new LinkedList<>();

        // Mark source node as visited and enqueue it
        visited[s] = true;
        q.add(s);

        // Iterate over the queue
        while (!q.isEmpty()) {

            // Dequeue a vertex and store it
            int curr = q.poll();
            res.add(curr);

            // Get all adjacent vertices of the dequeued 
            // vertex curr If an adjacent has not been 
            // visited, mark it visited and enqueue it
            for (int x : adj.get(curr)) {
                if (!visited[x]) {
                    visited[x] = true;
                    q.add(x);
                }
            }
        }
        return res;
    }

    // Perform BFS for the entire graph which maybe
    // disconnected
    static ArrayList<Integer> bfsDisconnected(
                ArrayList<ArrayList<Integer>> adj) {
        int V = adj.size();

        // create an array to store the traversal
        ArrayList<Integer> res = new ArrayList<>();

        // Initially mark all the vertices as not visited
        boolean[] visited = new boolean[V];

        // perform BFS for each node
        for (int i = 0; i < V; i++) {
            if (!visited[i]) {
                bfsOfGraph(adj, i, visited, res);
            }
        }
        return res;
    }

    public static void main(String[] args) {
        ArrayList<ArrayList<Integer>> adj = new ArrayList<>();
        adj.add(new ArrayList<>(Arrays.asList(1, 2)));
        adj.add(new ArrayList<>(Arrays.asList(0))); 
        adj.add(new ArrayList<>(Arrays.asList(0)));   
        adj.add(new ArrayList<>(Arrays.asList(4)));
        adj.add(new ArrayList<>(Arrays.asList(3, 5)));
        adj.add(new ArrayList<>(Arrays.asList(4)));  

        int src = 0;
        ArrayList<Integer> ans = bfsDisconnected(adj);
        for (int i : ans) {
            System.out.print(i + " ");
        }
    }
}

				
					// BFS from given source s
function bfsOfGraph(adj, s, visited, res) {
    
    // Create a queue for BFS
    let q = [];
    
    // Mark source node as visited and enqueue it
    visited[s] = true;
    q.push(s);
    
    // Iterate over the queue
    while (q.length > 0) {
        
        // Dequeue a vertex and store it
        let curr = q.shift();
        res.push(curr);
        
        // Get all adjacent vertices of the dequeued 
        // vertex curr If an adjacent has not been 
        // visited, mark it visited and enqueue it
        for (let x of adj[curr]) {
            if (!visited[x]) {
                visited[x] = true;
                q.push(x);
            }
        }
    }
    return res;
}
 
// Perform BFS for the entire graph which maybe
// disconnected
function bfsDisconnected(adj) {
    let V = adj.length;
    
    // create an array to store the traversal
    let res = [];
    
    // Initially mark all the vertices as not visited
    let visited = new Array(V).fill(false);
    
    // perform BFS for each node
    for (let i = 0; i < V; i++) {
        if (!visited[i]) {
            bfsOfGraph(adj, i, visited, res);
        }
    }
    return res;
}
 
// Main execution
let adj =
    [[1, 2], [0], [0],
    [4], [3, 5], [4]];
let ans = bfsDisconnected(adj);
for (let i of ans) {
    process.stdout.write(i + " ");
}

				
					# BFS from given source s
from collections import deque

def bfsOfGraph(adj, s, visited, res):
    
    # Create a queue for BFS
    q = deque()
    
    # Mark source node as visited and enqueue it
    visited[s] = True
    q.append(s)
    
    # Iterate over the queue
    while q:
        
        # Dequeue a vertex and store it
        curr = q.popleft()
        res.append(curr)
        
        # Get all adjacent vertices of the dequeued 
        # vertex curr If an adjacent has not been 
        # visited, mark it visited and enqueue it
        for x in adj[curr]:
            if not visited[x]:
                visited[x] = True
                q.append(x)
    return res

# Perform BFS for the entire graph which maybe
# disconnected
def bfsDisconnected(adj):
    V = len(adj)
    
    # create an array to store the traversal
    res = []
    
    # Initially mark all the vertices as not visited
    visited = [False] * V
    
    # perform BFS for each node
    for i in range(V):
        if not visited[i]:
            bfsOfGraph(adj, i, visited, res)
    return res

if __name__ == "__main__":
    adj = [[1, 2], [0], [0],
        [4], [3, 5], [4]]
    ans = bfsDisconnected(adj)
    for i in ans:
        print(i, end=" ")

Output

0 1 2 3 4

BFS in a Disconnected Graph

To handle such cases, we need a modified approach that ensures complete traversal, even when the graph contains disconnected components.

Network Routing in Computer Networking

The Floyd-Warshall algorithm is widely used in computer networks to determine the shortest paths between all pairs of nodes. This helps in efficient routing of data packets, ensuring optimal communication paths in network infrastructure.

Flight Connectivity in Aviation

In the aviation industry, this algorithm assists in finding the shortest and most cost-effective routes between airports, optimizing flight paths and connections for passengers and cargo.

Geographic Information Systems (GIS)

GIS applications frequently analyze spatial data such as road networks. Floyd-Warshall is used to calculate the shortest paths between various locations, helping in navigation, urban planning, and resource management.

Kleene’s Algorithm and Formal Language Theory

A generalization of Floyd-Warshall, known as Kleene’s algorithm, is employed in automata theory to compute regular expressions for regular languages, facilitating pattern matching and compiler design.

Output

0 1 2 3 4

BFS in a Disconnected Graph

To handle such cases, we need a modified approach that ensures complete traversal, even when the graph contains disconnected components.

				
					#include<bits/stdc++.h>
using namespace std;

// Function to find sum of weights of edges of the Minimum Spanning Tree.
int spanningTree(int V, int E, vector<vector<int>> &edges) {
  
    // Create an adjacency list representation of the graph
    vector<vector<int>> adj[V];
    
    // Fill the adjacency list with edges and their weights
    for (int i = 0; i < E; i++) {
        int u = edges[i][0];
        int v = edges[i][1];
        int wt = edges[i][2];
        adj[u].push_back({v, wt});
        adj[v].push_back({u, wt});
    }
    
    // Create a priority queue to store edges with their weights
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
    
    // Create a visited array to keep track of visited vertices
    vector<bool> visited(V, false);
    
    // Variable to store the result (sum of edge weights)
    int res = 0;
    
    // Start with vertex 0
    pq.push({0, 0});
    
    // Perform Prim's algorithm to find the Minimum Spanning Tree
    while(!pq.empty()){
        auto p = pq.top();
        pq.pop();
        
        int wt = p.first;  // Weight of the edge
        int u = p.second;  // Vertex connected to the edge
        
        if(visited[u] == true){
            continue;  // Skip if the vertex is already visited
        }
        
        res += wt;  // Add the edge weight to the result
        visited[u] = true;  // Mark the vertex as visited
        
        // Explore the adjacent vertices
        for(auto v : adj[u]){
            // v[0] represents the vertex and v[1] represents the edge weight
            if(visited[v[0]] == false){
                pq.push({v[1], v[0]});  // Add the adjacent edge to the priority queue
            }
        }
    }
    
    return res;  // Return the sum of edge weights of the Minimum Spanning Tree
}

int main() {
    vector<vector<int>> graph = {{0, 1, 5},
                      			{1, 2, 3},
                      			{0, 2, 1}};

    cout << spanningTree(3, 3, graph) << endl;

    return 0;
}

Output

0 1 2 3 4 5

Complexity Analysis of the Breadth-First Search (BFS) Algorithm

Time Complexity: O(V + E)

The BFS algorithm explores all vertices and edges in a graph. In the worst-case scenario, it visits every vertex and traverses every edge exactly once.

V = Number of vertices
E = Number of edges
Thus, the time complexity of BFS is O(V + E).

Auxiliary Space Complexity: O(V)

BFS uses a queue to manage the vertices to be explored. In the worst case, the queue can hold all vertices at once, especially in dense or fully connected graphs.
Hence, the auxiliary space required is O(V).

Applications of BFS in Graph Theory

Breadth-First Search is a foundational algorithm in computer science and graph theory, with several practical applications:

🔹 1. Shortest Path in Unweighted Graphs

BFS is commonly used to determine the shortest path between two nodes in an unweighted graph. By tracking each node’s parent during traversal, the path can be reconstructed efficiently.

🔹 2. Cycle Detection

BFS can detect cycles in both directed and undirected graphs. If a node is encountered more than once during traversal (excluding its immediate parent), a cycle exists.

🔹 3. Identifying Connected Components

In disconnected graphs, BFS can be used to identify connected components, where each component is a group of nodes that are mutually reachable.

🔹 4. Topological Sorting (for DAGs)

In a Directed Acyclic Graph (DAG), BFS helps in performing topological sorting by processing nodes in linear order such that each node appears before its dependents.

🔹 5. Level-Order Traversal of Binary Trees

BFS is ideal for level-order traversal in binary trees, where nodes are visited level by level from top to bottom.

🔹 6. Network Routing

BFS plays a key role in network routing algorithms, especially when finding the shortest path between two routers or devices in a network.

				
					// A Java program for Prim's Minimum Spanning Tree (MST)
// algorithm. The program is for adjacency list
// representation of the graph

import java.io.*;
import java.util.*;

// Class to form pair
class Pair implements Comparable<Pair>
{
    int v;
    int wt;
    Pair(int v,int wt)
    {
        this.v=v;
        this.wt=wt;
    }
    public int compareTo(Pair that)
    {
        return this.wt-that.wt;
    }
}

class GFG {

	// Function of spanning tree
	static int spanningTree(int V, int E, int edges[][])
    {
         ArrayList<ArrayList<Pair>> adj=new ArrayList<>();
         for(int i=0;i<V;i++)
         {
             adj.add(new ArrayList<Pair>());
         }
         for(int i=0;i<edges.length;i++)
         {
             int u=edges[i][0];
             int v=edges[i][1];
             int wt=edges[i][2];
             adj.get(u).add(new Pair(v,wt));
             adj.get(v).add(new Pair(u,wt));
         }
         PriorityQueue<Pair> pq = new PriorityQueue<Pair>();
         pq.add(new Pair(0,0));
         int[] vis=new int[V];
         int s=0;
         while(!pq.isEmpty())
         {
             Pair node=pq.poll();
             int v=node.v;
             int wt=node.wt;
             if(vis[v]==1) 
             continue;
             
             s+=wt;
             vis[v]=1;
             for(Pair it:adj.get(v))
             {
                 if(vis[it.v]==0)
                 {
                     pq.add(new Pair(it.v,it.wt));
                 }
             }
         }
         return s;
    }
    
    // Driver code
    public static void main (String[] args) {
        int graph[][] = new int[][] {{0,1,5},
                                    {1,2,3},
                                    {0,2,1}};
 
        // Function call
        System.out.println(spanningTree(3,3,graph));
    }
}

				
					class PriorityQueue {
    constructor() {
        this.heap = [];
    }

    enqueue(value) {
        this.heap.push(value);
        let i = this.heap.length - 1;
        while (i > 0) {
            let j = Math.floor((i - 1) / 2);
            if (this.heap[i][0] >= this.heap[j][0]) {
                break;
            }
            [this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]];
            i = j;
        }
    }

    dequeue() {
        if (this.heap.length === 0) {
            throw new Error("Queue is empty");
        }
        let i = this.heap.length - 1;
        const result = this.heap[0];
        this.heap[0] = this.heap[i];
        this.heap.pop();

        i--;
        let j = 0;
        while (true) {
            const left = j * 2 + 1;
            if (left > i) {
                break;
            }
            const right = left + 1;
            let k = left;
            if (right <= i && this.heap[right][0] < this.heap[left][0]) {
                k = right;
            }
            if (this.heap[j][0] <= this.heap[k][0]) {
                break;
            }
            [this.heap[j], this.heap[k]] = [this.heap[k], this.heap[j]];
            j = k;
        }

        return result;
    }

    get count() {
        return this.heap.length;
    }
}

function spanningTree(V, E, edges) {
    // Create an adjacency list representation of the graph
    const adj = new Array(V).fill(null).map(() => []);

    // Fill the adjacency list with edges and their weights
    for (let i = 0; i < E; i++) {
        const [u, v, wt] = edges[i];
        adj[u].push([v, wt]);
        adj[v].push([u, wt]);
    }

    // Create a priority queue to store edges with their weights
    const pq = new PriorityQueue();

    // Create a visited array to keep track of visited vertices
    const visited = new Array(V).fill(false);

    // Variable to store the result (sum of edge weights)
    let res = 0;

    // Start with vertex 0
    pq.enqueue([0, 0]);

    // Perform Prim's algorithm to find the Minimum Spanning Tree
    while (pq.count > 0) {
        const p = pq.dequeue();

        const wt = p[0];  // Weight of the edge
        const u = p[1];   // Vertex connected to the edge

        if (visited[u]) {
            continue;  // Skip if the vertex is already visited
        }

        res += wt;  // Add the edge weight to the result
        visited[u] = true;  // Mark the vertex as visited

        // Explore the adjacent vertices
        for (const v of adj[u]) {
            // v[0] represents the vertex and v[1] represents the edge weight
            if (!visited[v[0]]) {
                pq.enqueue([v[1], v[0]]);  // Add the adjacent edge to the priority queue
            }
        }
    }

    return res;  // Return the sum of edge weights of the Minimum Spanning Tree
}

// Example usage
const graph = [[0, 1, 5], [1, 2, 3], [0, 2, 1]];

// Function call
console.log(spanningTree(3, 3, graph));

				
					def tree(V, E, edges):
    # Create an adjacency list representation of the graph
    adj = [[] for _ in range(V)]
    # Fill the adjacency list with edges and their weights
    for i in range(E):
        u, v, wt = edges[i]
        adj[u].append((v, wt))
        adj[v].append((u, wt))
    # Create a priority queue to store edges with their weights
    pq = []
    # Create a visited array to keep track of visited vertices
    visited = [False] * V
    # Variable to store the result (sum of edge weights)
    res = 0
    # Start with vertex 0
    heapq.heappush(pq, (0, 0))
    # Perform Prim's algorithm to find the Minimum Spanning Tree
    while pq:
        wt, u = heapq.heappop(pq)
        if visited[u]:
            continue  
            # Skip if the vertex is already visited
        res += wt  
        # Add the edge weight to the result
        visited[u] = True  
        # Mark the vertex as visited
        # Explore the adjacent vertices
        for v, weight in adj[u]:
            if not visited[v]:
                heapq.heappush(pq, (weight, v))  
                # Add the adjacent edge to the priority queue
    return res  
  # Return the sum of edge weights of the Minimum Spanning Tree
if __name__ == "__main__":
    graph = [[0, 1, 5],
             [1, 2, 3],
             [0, 2, 1]]
    # Function call
    print(tree(3, 3, graph))

Output

Time Complexity: O((E + V) * log(V))

Where V is the number of vertices and E is the number of edges in the graph.
Auxiliary Space: O(E + V)
This space is used to store the graph and auxiliary data structures like the priority queue and visited array.

Advantages and Disadvantages of Prim’s Algorithm

Advantages:

Guaranteed to find the MST: Prim’s algorithm reliably computes the Minimum Spanning Tree in any connected, weighted graph.
Efficient with optimized data structures: When used with a binary heap or Fibonacci heap, it achieves a time complexity of O((E + V) * log(V)).
Ease of understanding and implementation: Compared to some other MST algorithms, Prim’s algorithm is relatively straightforward to grasp and code.

Disadvantages:

Performance on dense graphs: On graphs with a high number of edges, the algorithm may be slower since it needs to consider every edge at least once.
Additional memory usage: The reliance on a priority queue can increase memory consumption, which might lead to slower performance on very large-scale graphs.
MST may vary based on the starting node: The initial vertex selection can influence the structure of the resulting MST, which could be undesirable in certain scenarios where consistency is critical.

Note: If you’re studying Data Structures & Algorithms (DSA) for the first time, you can explore our comprehensive Data Structures & Algorithms course. For developers looking to build end-to-end applications, our Web Development program covers both frontend and backend concepts. If you want an integrated path covering algorithms, web development, and system design, check out the Master DSA, Web Dev & System Design curriculum. For those interested in analytics, our Data Science course offers hands-on projects and real-world datasets.

Network Routing in Computer Networking

Flight Connectivity in Aviation

In the aviation industry, this algorithm assists in finding the shortest and most cost-effective routes between airports, optimizing flight paths and connections for passengers and cargo.

Geographic Information Systems (GIS)

Kleene’s Algorithm and Formal Language Theory

What is BFS and how does it work?

BFS is a graph traversal algorithm that systematically explores a graph by visiting all the vertices at a given level before moving to the next. It begins at a starting vertex, enqueues it, and marks it as visited. Then it dequeues a vertex, visits it, and enqueues its unvisited neighbors. This continues until all reachable vertices are processed.
If you’re new to such algorithms, our Data Structures & Algorithms (DSA) Course explains BFS with visuals and coding exercises.

What are the applications of BFS?

BFS is used in numerous applications such as finding the shortest path in unweighted graphs, detecting cycles, topological sorting in DAGs, finding connected components, and solving puzzles like mazes and Sudoku.
To explore real-world uses of BFS in web applications, check out our Web Development Course that blends algorithms with practical projects.

What is the time complexity of BFS?

The time complexity of BFS is O(V + E), where V is the number of vertices and E is the number of edges. It ensures each vertex and edge is visited once.
If you want to dive deeper into such complexities, our Design + DSA Combined Course is designed just for you.

DSA, High & Low Level System Designs

85+ Live Classes & Recordings
24*7 Live Doubt Support
400+ DSA Practice Questions
Comprehensive Notes
HackerRank Tests & Quizzes
Topic-wise Quizzes
Case Studies
Access to Global Peer Community

Buy for 60% OFF
₹25,000.00 ₹9,999.00

Accelerate your Path to a Product based Career

Boost your career or get hired at top product-based companies by joining our expertly crafted courses. Gain practical skills and real-world knowledge to help you succeed.

Reach Out Now

If you have any queries, please fill out this form. We will surely reach out to you.

Contact Email

Reach us at the following email address.

[email protected]

Phone Number

You can reach us by phone as well.

+91-97737 28034

Our Location

Rohini, Sector-3, Delhi-110085

Prim’s Algorithm for Minimum Spanning Tree (MST)

Problem Statement

Example 1

Input:

BFS Traversal Output:

Explanation:

Example 2

Input:

BFS Traversal Output:

Explanation:

What is Breadth-First Search (BFS)?

BFS from a Given Source

Approach to Perform BFS from a Given Source

1. Initialization

2. Exploration

3. Termination

Output

BFS in a Disconnected Graph

Output

BFS in a Disconnected Graph

Network Routing in Computer Networking

Flight Connectivity in Aviation

Geographic Information Systems (GIS)

Kleene’s Algorithm and Formal Language Theory

Output

BFS in a Disconnected Graph

Output

Complexity Analysis of the Breadth-First Search (BFS) Algorithm

Time Complexity: O(V + E)

Auxiliary Space Complexity: O(V)

Applications of BFS in Graph Theory

🔹 1. Shortest Path in Unweighted Graphs

🔹 2. Cycle Detection

🔹 3. Identifying Connected Components

🔹 4. Topological Sorting (for DAGs)

🔹 5. Level-Order Traversal of Binary Trees

🔹 6. Network Routing

Output

Time Complexity: O((E + V) * log(V))

Advantages and Disadvantages of Prim’s Algorithm

Advantages:

Disadvantages:

Network Routing in Computer Networking

Flight Connectivity in Aviation

Geographic Information Systems (GIS)

Kleene’s Algorithm and Formal Language Theory

What is BFS and how does it work?

What are the applications of BFS?

What is the time complexity of BFS?

DSA, High & Low Level System Designs

Buy for 60% OFF ₹25,000.00 ₹9,999.00

Accelerate your Path to a Product based Career

Essentials of Machine Learning and Artificial Intelligence

Buy for 65% OFF ₹20,000.00 ₹6,999.00

Fast-Track to Full Spectrum Software Engineering

Buy for 57% OFF ₹35,000.00 ₹14,999.00

DSA, High & Low Level System Designs

Buy for 60% OFF ₹25,000.00 ₹9,999.00

Low & High Level System Design

Buy for 65% OFF ₹20,000.00 ₹6,999.00

Mastering Mern Stack (WEB DEVELOPMENT)

Buy for 60% OFF ₹15,000.00 ₹5,999.00

10 Day Google Interview Preparation Bootcamp

Reach Out Now

Contact Email

Phone Number

Our Location

Quick Links

Quick Links

Social Media

Master Your Interviews with Our Free Roadmap!

Hi Instagram Fam! Get a FREE Cheat Sheet on System Design.

Hi LinkedIn Fam! Get a FREE Cheat Sheet on System Design

Loved Our YouTube Videos? Get a FREE Cheat Sheet on System Design.

Buy for 60% OFF
₹25,000.00 ₹9,999.00

Buy for 65% OFF
₹20,000.00 ₹6,999.00

Buy for 57% OFF
₹35,000.00 ₹14,999.00

Buy for 60% OFF
₹25,000.00 ₹9,999.00

Buy for 65% OFF
₹20,000.00 ₹6,999.00

Buy for 60% OFF
₹15,000.00 ₹5,999.00

Hi Instagram Fam!
Get a FREE Cheat Sheet on System Design.

Hi LinkedIn Fam!
Get a FREE Cheat Sheet on System Design