Minimum Number of Vertices to Reach All Nodes

Introduction

In this blog post, we will discuss the problem of finding the minimum number of vertices required to reach all nodes in a directed graph. We will explore an algorithmic approach to solve this problem efficiently.

Problem Statement

Given a directed graph with n nodes labelled from 0 to n-1, and an array of edges where edges[i] = [u, v] represents a directed edge from node u to node v. Our task is to find the minimum number of vertices from which we can reach all other nodes in the graph.

Data Structure Used

We will represent the directed graph using an adjacency list. Each node will be represented by an integer, and the graph will be stored as a vector of lists.

Algorithmic Approach

To find the minimum number of vertices required to reach all nodes, we can follow the following approach:

1. Create an empty vector res to store the smallest set of vertices.
  1. Create a vector visited of size n and initialize it with zeros. This vector will be used to mark the visited vertices.
  2. Iterate through the edges vector. For each edge [u, v], mark the vertex v as visited by setting visited[v] to 1.
  3. Iterate through the vertices from 0 to n-1. If a vertex i is not visited (i.e., visited[i] is 0), add it to the res vector.
  4. Return the res vector as the smallest set of vertices required to reach all nodes.

This approach identifies the vertices with no incoming edges (vertices with visited[i] equal to 0) as the smallest set of vertices needed to reach all other nodes.

vector<int> findSmallestSetOfVertices(int n, vector<vector<int>>& edges) {

    vector<int> res, visited(n);         
    for (vector<int>& e: edges)
        visited[e[1]] = 1;
    for (int i = 0; i < n; ++i)
        if (visited[i] == 0)
            res.push_back(i);

    return res;   
}

Complexity Analysis

This approach has a time complexity of O(n + m), where n is the number of vertices and m is the number of edges. We iterate through the edges vector once to mark the visited vertices and iterate through the vertices once to identify the vertices with no incoming edges.

The space complexity is O(n) to store the visited vector and the result vector.

It is worth noting that this approach assumes that the vertices are labeled from 0 to n-1 and that there are no duplicate edges in the input.

This approach provides an efficient solution to find the smallest set of vertices required to reach all nodes in the given directed graph.

Conclusion

In this blog post, we discussed the problem of finding the minimum number of vertices required to reach all nodes in a directed graph. We presented an algorithmic approach that involves calculating the indegree of each node and identifying the nodes with an indegree of zero. We analyzed the time and space complexity of the approach, highlighting its efficiency. This solution allows us to efficiently determine the minimum number of vertices needed to reach all nodes in the given graph.

Stackable