Smallest set of vertices to visit all nodes of the given Graph

0 0 9 minutes read

Given a directed acyclic graph of N nodes, the task is to find the smallest set of vertices from which the complete graph can be visited.

Examples:

Input: Graph in the image below

Output: 0 4
Explanation: From vertex 0, the set of nodes that can be visited is {0 ,1}. Similarly, from vertex 4, {4, 3, 2} can be visited. Hence, the complete graph can be visited from the set {0, 4} which is of the minimum possible size.

Input: Graph in the image below

Output: 3 4

Approach 1: The given problem can be solved using topological sorting to get the ordering of vertices such that for every directed edge from U to V, U comes before V. Below are the steps to follow:

Sort the given array of vertices in topological order using Khan’s Algorithm.
Maintain an array visited which keeps track of the visited vertices.
Iterate the sorted array perform the following operations:
- If the current vertex is not visited, insert it into the required set.
- Visit all the nodes that are reachable from the inserted node using DFS traversal.

Below is the implementation of the above approach:

C++

#include <bits/stdc++.h>
using namespace std;
 
class Solution {
  public:
  // Function to perform DFS
  void dfs(int node, unordered_set<int>& vis,
           map<int, vector<int> >& graph)
  {
 
    // add node to visited set
    vis.insert(node);
 
    for (int adj : graph[node]) {
      if (vis.count(adj) == 0) {
        dfs(adj, vis, graph);
      }
    }
  }
 
  vector<int> solve(vector<vector<int> >& edges)
  {
    map<int, vector<int> > graph;
 
    // dictionary storing
    // indegrees of node
    map<int, int> indeg;
 
    // array to store topological
    // sorting of the array
    vector<int> topo_sort;
    unordered_set<int> vis;
 
    for (auto edge : edges) {
      int u = edge[0], v = edge[1];
      graph[u].push_back(v);
 
      // count indegree of each node
      indeg[v]++;
    }
 
    queue<int> qu;
 
    for (auto u : graph) {
 
      // add to queue, if indegree
      // of node u is 0
      if (indeg[u.first] == 0) {
        qu.push(u.first);
      }
    }
 
    // Run till queue is not empty
    while (!qu.empty()) {
 
      int node = qu.front();
      qu.pop();
 
      // add node to topo_sort
      topo_sort.push_back(node);
 
      // traverse adj nodes
      for (int adj : graph[node]) {
 
        // decrement count of indegree
        // of each adj node by 1
        indeg[adj]--;
 
        // if count becomes 0, then
        // add adj to qu
        if (indeg[adj] == 0) {
          qu.push(adj);
        }
      }
    }
 
    vis.clear();
    vector<int> ans;
 
    // Take each node from topo_sort
    for (int node : topo_sort) {
 
      // check if node is visited
      if (vis.count(node) == 0) {
 
        vis.insert(node);
        ans.push_back(node);
 
        // Mark all the reachable
        // nodes as visited
        dfs(node, vis, graph);
      }
    }
 
    // finally return ans
    return ans;
  }
};
 
// Driver code
int main()
{
  Solution obj;
  vector<vector<int> > edges
    = { { 0, 1 }, { 2, 1 }, { 3, 2 }, { 4, 3 } };
 
  // Function call
  vector<int> ans = obj.solve(edges);
  for (int n : ans) {
    cout << n << " ";
  }
  cout << endl;
 
  return 0;
}

Java

//GFG
// JAVA program of the above approach
import java.util.*;
 
public class Solution {
   
  // Function to perform DFS
    private void dfs(int node, Set<Integer> vis, Map<Integer, List<Integer>> graph) {
        vis.add(node);
        for (int adj : graph.getOrDefault(node, new ArrayList<>())) {
            if (!vis.contains(adj)) {
                dfs(adj, vis, graph);
            }
        }
    }
 
    public List<Integer> solve(int[][] edges) {
        Map<Integer, List<Integer>> graph = new HashMap<>();
        Map<Integer, Integer> indeg = new HashMap<>();
 
        List<Integer> topoSort = new ArrayList<>();
        Set<Integer> vis = new HashSet<>();
 
        for (int[] edge : edges) {
            int u = edge[0];
            int v = edge[1];
            graph.putIfAbsent(u, new ArrayList<>());
            graph.get(u).add(v);
            indeg.put(v, indeg.getOrDefault(v, 0) + 1);
        }
 
        Queue<Integer> qu = new LinkedList<>();
        for (int u : graph.keySet()) {
            if (!indeg.containsKey(u)) {
                qu.offer(u);
            }
        }
 
        while (!qu.isEmpty()) {
            int node = qu.poll();
            topoSort.add(node);
            for (int adj : graph.getOrDefault(node, new ArrayList<>())) {
                indeg.put(adj, indeg.get(adj) - 1);
                if (indeg.get(adj) == 0) {
                    qu.offer(adj);
                }
            }
        }
 
        vis = new HashSet<>();
        List<Integer> ans = new ArrayList<>();
        for (int node : topoSort) {
            if (!vis.contains(node)) {
                vis.add(node);
                ans.add(node);
                dfs(node, vis, graph);
            }
        }
 
        return ans;
    }
 
    public static void main(String[] args) {
        Solution obj = new Solution();
        int[][] edges = {{0, 1}, {2, 1}, {3, 2}, {4, 3}};
        List<Integer> ans = obj.solve(edges);
        System.out.println(ans);
    }
}
// This code is written by Sundaram

Python3

# Python program of the above approach
from collections import defaultdict, deque
 
class Solution:
 
    # Function to perform DFS
    def dfs(self, node, vis, graph):
 
        # add node to visited set
        vis.add(node)
 
        for adj in graph[node]:
            if (adj not in vis):
                self.dfs(adj, vis, graph)
 
    def solve(self, edges):
 
        graph = defaultdict(list)
 
        # dictionary storing
        # indegrees of node
        indeg = defaultdict(int)
 
        # array to store topological
        # sorting of the array
        topo_sort = []
        vis = set()
 
        for (u, v) in edges:
            graph[u].append(v)
 
            # count indegree of each node
            indeg[v] += 1
 
        qu = deque()
 
        for u in graph:
 
            # add to ququ ,if indegree
            # of node u is 0
            if(indeg[u] == 0):
                qu.append(u)
 
        # Run till queue is not empty
        while(qu):
 
            node = qu.popleft()
 
            # add node to topo_sort
            topo_sort.append(node)
 
            # traverse adj nodes
            for adj in graph[node]:
 
                # decrement count of indegree
                # of each adj node by 1
                indeg[adj] -= 1
 
                # if count becomes 0, then
                # add adj to qu
                if (indeg[adj] == 0):
                    qu.append(adj)
 
        vis = set()
        ans = []
 
        # Take each node from topo_sort
        for node in topo_sort:
 
            # check if node is visited
            if (node not in vis):
 
                vis.add(node)
                ans.append(node)
 
                # Mark all the reachable
                # nodes as visited
                self.dfs(node, vis, graph)
 
        # finally return ans
        return (ans)
 
 
obj = Solution()
edges = [[0, 1], [2, 1], [3, 2], [4, 3]]
 
ans = obj.solve(edges)
print(" ".join(str(n) for n in ans))

C#

using System;
using System.Collections.Generic;
using System.Linq;
 
public class Solution {
    // Function to perform DFS
    private void dfs(int node, HashSet<int> vis,
                     Dictionary<int, List<int> > graph)
    {
        vis.Add(node);
        foreach(int adj in graph.GetValueOrDefault(
            node, new List<int>()))
        {
            if (!vis.Contains(adj)) {
                dfs(adj, vis, graph);
            }
        }
    }
 
    public List<int> Solve(int[][] edges)
    {
        Dictionary<int, List<int> > graph
            = new Dictionary<int, List<int> >();
        Dictionary<int, int> indeg
            = new Dictionary<int, int>();
 
        List<int> topoSort = new List<int>();
        HashSet<int> vis = new HashSet<int>();
 
        foreach(int[] edge in edges)
        {
            int u = edge[0];
            int v = edge[1];
            if (!graph.ContainsKey(u)) {
                graph.Add(u, new List<int>());
            }
            graph[u].Add(v);
            indeg[v] = indeg.GetValueOrDefault(v, 0) + 1;
        }
 
        Queue<int> qu = new Queue<int>();
        foreach(int u in graph.Keys)
        {
            if (!indeg.ContainsKey(u)) {
                qu.Enqueue(u);
            }
        }
 
        while (qu.Count() != 0) {
            int node = qu.Dequeue();
            topoSort.Add(node);
            foreach(int adj in graph.GetValueOrDefault(
                node, new List<int>()))
            {
                indeg[adj] = indeg[adj] - 1;
                if (indeg[adj] == 0) {
                    qu.Enqueue(adj);
                }
            }
        }
 
        vis = new HashSet<int>();
        List<int> ans = new List<int>();
        foreach(int node in topoSort)
        {
            if (!vis.Contains(node)) {
                vis.Add(node);
                ans.Add(node);
                dfs(node, vis, graph);
            }
        }
 
        return ans;
    }
 
    public static void Main()
    {
        Solution obj = new Solution();
        int[][] edges
            = { new int[] { 0, 1 }, new int[] { 2, 1 },
                new int[] { 3, 2 }, new int[] { 4, 3 } };
        List<int> ans = obj.Solve(edges);
        Console.WriteLine(string.Join(", ", ans));
    }
}
// This code is contrubuted by user_dtewbxkn77n

Javascript

// Function to perform DFS
function dfs(node, vis, graph) {
    vis.add(node);
    for (const adj of graph[node] || []) {
        if (!vis.has(adj)) {
            dfs(adj, vis, graph);
        }
    }
}
 
class Solution {
    solve(edges) {
        const graph = {};
        const indeg = {};
 
 
        const topoSort = [];
        const vis = new Set();
 
        // Build graph and calculate indegree
        for (const [u, v] of edges) {
            if (!graph[u]) {
                graph[u] = [];
            }
            graph[u].push(v);
            indeg[v] = (indeg[v] || 0) + 1;
        }
 
        // Enqueue all nodes with 0 indegree
        const qu = [];
        for (const u of Object.keys(graph)) {
            if (!indeg[u]) {
                qu.push(u);
            }
        }
 
        // Perform topological sort
        while (qu.length) {
            const node = qu.shift();
            topoSort.push(node);
            for (const adj of graph[node] || []) {
                indeg[adj]--;
                if (indeg[adj] === 0) {
                    qu.push(adj);
                }
            }
        }
 
        // Perform DFS on unvisited nodes in topoSort
        vis.clear();
        const ans = [];
        for (const node of topoSort) {
            if (!vis.has(node)) {
                vis.add(node);
                ans.push(node);
                dfs(node, vis, graph);
            }
        }
 
        return ans;
 
    }
}
 
 
// Driver code
const obj = new Solution();
const edges = [
    [0, 1],
    [2, 1],
    [3, 2],
    [4, 3],
];
// Function call
const ans = obj.solve(edges);
console.log(ans.join(" "));
 
 
// This code is contributed by phasing17

Output

0 4

Time Complexity: O(N)
Auxiliary Space: O(N)

Approach 2: The given problem can also be solved using the observation that vertices with in-degree 0 are the vertices that can not be reached from any other vertex. Hence, the idea is to find the indegree of each vertex and insert the vertices with in-degree 0 into the required set, as all the other vertices can be visited eventually.