Given a graph and the list of neighbours for each node in an array graph[] of size N, where graph[i] contains a list of neighbor nodes that are connected to ith node, the task is to visit all the nodes of the given graph in a minimum amount of time.
Note: Movement from any node to its neighbour takes one unit of time
Example:
Input: [[1, 2, 3], [2, 0], [0, 1], [0, 4], [3]]
Output: 4
Explanation:
One possible way to visit all node in minimum number of time is shown by the below graph
Input: [[1, 2, 3], [2, 0], [0, 1], [0]]
Output: 3
An approach using BFS + BitMasking:
Usually it is best to use BFS to find the minimum time problem in graph. However, in this case, we cannot use traditional BFS since traditional BFS can only visit the elements once. In this case, repetition is allowed, which means we can traverse any node multiple times, leading to an infinite loop. To handle infinite loop we can use Bitmasking to store the states while moving over graph.
Follow the step below to implement the above idea:
- Create an adjacency list from the given graph
- Initialize a variable finalMask = (1 << number_of_nodes) – 1, this represent the state when all node has been visited.
- Initialize a variable timeCount = 0 to keep track of the minimum time to visit all nodes.
- Initialize a queue for BFS which will store the current node id and mask of visited nodes.
- Initialize a 2D array visited[][] for keeping track of nodes with all possible masks that are visited in the path.
- Push every node as a starting node for all possible paths with their mask for counting the number of the minimum time to visit all the node
- While the queue is not empty:
- Iterate over each level
- Fetch and pop the current node
- Check if the current node mask is equal to finalMask:
- If the condition is true, return timeCount as the result.
- Explore all the children of the current node:
- Make a new mask for the child by toggling the ith bit of the current Mask.
- If the new mask for the child has not been visited yet, push the child and new Mask in the queue and mark visited for the child with new mask.
- Increment the time Count after each level
- Iterate over each level
Below is the implementation of the above approach:
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// Function to calculate the minimum timeint minimizeTime(vector<vector<int> >& graph){ long long n = graph.size(); // Create adjacency list from the given graph vector<vector<long long> > adj(n); for (int i = 0; i < n; i++) { for (auto j : graph[i]) { adj[i].push_back(j); } } // Final mask when all the node will be visited long long finalMask = (long long)(1 << n) - 1; // Initialize a queue for BFS which will store current // node id and mask of visited nodes. queue<pair<long long, long long> > q; // Initialize a visited array for keeping track // of all mask that are visited in the path vector<vector<bool> > visited( n, vector<bool>(finalMask + 1)); // Push starting node for // all possible path with their mask for (int i = 0; i < n; i++) { q.push({ i, (long long)(1 << i) }); } // For counting the minimum time // to visit all the nodes long long timeCount = 0; // Do while q.size > 0 while (q.size() > 0) { int size = q.size(); // Iterate over each level for (int i = 0; i < size; i++) { // Fetch and pop the current node auto curr = q.front(); q.pop(); // Check if the current node mask // is equal to finalMask if (curr.second == finalMask) return timeCount; // Explore all the child of current node for (auto child : adj[curr.first]) { // Make a new Mask for child long long newVisitedBit = curr.second | (1 << child); // If new Mask for child has // not been visited yet, // push child and new Mask in // the queue and mark visited // for child with newVisitedBit if (visited[child][newVisitedBit] == false) { q.push({ child, newVisitedBit }); visited[child][newVisitedBit] = true; } } } // Increment the time Count after each level timeCount++; } // If all node can't be visited return -1;}// Driver codeint main(){ vector<vector<int> > graph = { { 1, 2, 3 }, { 2, 0 }, { 0, 1 }, { 0, 4 }, { 3 } }; // Function call int minTime = minimizeTime(graph); cout << minTime << endl; return 0;} |
Java
// Java code to implement the approachimport java.util.*;// Pair classclass Pair { int first, second; Pair(int first, int second) { this.first = first; this.second = second; } public int getKey() { return this.first; } public int getValue() { return this.second; }}class GFG { // Function to calculate the minimum time public static int minimizeTime(ArrayList<ArrayList<Integer> > graph) { int n = graph.size(); // Create adjacency list from the given graph ArrayList<ArrayList<Integer> > adj = new ArrayList<ArrayList<Integer> >(n); for (int i = 0; i < n; i++) { adj.add(new ArrayList<Integer>()); for (int j : graph.get(i)) { adj.get(i).add(j); } } // Final mask when all the node will be visited int finalMask = (1 << n) - 1; // Initialize a queue for BFS which will store // current node id and mask of visited nodes. Queue<Pair> q = new LinkedList<Pair>(); // Initialize a visited array for keeping track // of all mask that are visited in the path boolean[][] visited = new boolean[n][finalMask + 1]; // Push starting node for // all possible path with their mask for (int i = 0; i < n; i++) { q.add(new Pair(i, (1 << i))); } // For counting the minimum time // to visit all the nodes int timeCount = 0; // Do while q.size > 0 while (q.size() > 0) { int size = q.size(); // Iterate over each level for (int i = 0; i < size; i++) { // Fetch and pop the current node Pair curr = q.poll(); // Check if the current node mask // is equal to finalMask if (curr.getValue() == finalMask) return timeCount; // Explore all the child of current node for (int child : adj.get(curr.getKey())) { // Make a new Mask for child int newVisitedBit = curr.getValue() | (1 << child); // If new Mask for child has // not been visited yet, // push child and new Mask in // the queue and mark visited // for child with newVisitedBit if (visited[child][newVisitedBit] == false) { q.add( new Pair(child, newVisitedBit)); visited[child][newVisitedBit] = true; } } } // Increment the time Count after each level timeCount++; } // If all node can't be visited return -1; } // Driver code public static void main(String[] args) { ArrayList<ArrayList<Integer> > graph = new ArrayList<ArrayList<Integer> >(); graph.add( new ArrayList<Integer>(Arrays.asList(1, 2, 3))); graph.add( new ArrayList<Integer>(Arrays.asList(2, 0))); graph.add( new ArrayList<Integer>(Arrays.asList(0, 1))); graph.add( new ArrayList<Integer>(Arrays.asList(0, 4))); graph.add(new ArrayList<Integer>(Arrays.asList(3))); // Function call int minTime = minimizeTime(graph); System.out.println(minTime); }}// This code is contributed by Tapesh(tapeshdua420) |
Python3
# Python code to implement the approach# Function to calculate the minimum timedef minimizeTime(graph): n = len(graph) # Create adjacency list from the given graph adj = [[] for i in range(n)] for i in range(n): for j in graph[i]: adj[i].append(j) # Final mask when all the node will be visited finalMask = (1<<n) - 1 # Initialize a queue for BFS which will store current # node id and mask of visited nodes. q = [] # Initialize a visited array for keeping track # of all mask that are visited in the path visited = [[0 for i in range(finalMask+1)] for j in range(n)] # Push starting node for # all possible path with their mask for i in range(n): q.append([i,1<<i]) # For counting the minimum time # to visit all the nodes timeCount = 0 # Do while q.size > 0 while(len(q) > 0): size = len(q) # Iterate over each level for i in range(size): # Fetch and pop the current node curr = q.pop(0) # Check if the current node mask # is equal to finalMask if(curr[1] == finalMask): return timeCount # Explore all the child of current node for child in adj[curr[0]]: # Make a new Mask for child newVisitedBit = curr[1]|(1<<child) # If new Mask for child has # not been visited yet, # push child and new Mask in # the queue and mark visited # for child with newVisitedBit if(visited[child][newVisitedBit] == False): q.append([child,newVisitedBit]) visited[child][newVisitedBit] = True # Increment the time Count after each level timeCount = timeCount + 1 # If all node can't be visited return -1 # Driver codegraph = [[1,2,3],[2,0],[0,1],[0,4],[3]]# Function callaminTime = minimizeTime(graph)print(minTime)# This code is contributed by Pushpesh Raj. |
C#
// C# code to implement the approachusing System;using System.Collections.Generic;class Program { // Driver code static void Main(string[] args) { List<List<int> > graph = new List<List<int> >(); graph.Add(new List<int>(new int[] { 1, 2, 3 })); graph.Add(new List<int>(new int[] { 2, 0 })); graph.Add(new List<int>(new int[] { 0, 1 })); graph.Add(new List<int>(new int[] { 0, 4 })); graph.Add(new List<int>(new int[] { 3 })); // Function call int minTime = minimizeTime(graph); Console.WriteLine(minTime); } // Function to calculate the minimum time public static int minimizeTime(List<List<int> > graph) { int n = graph.Count; // Create adjacency list from the given graph List<List<int> > adj = new List<List<int> >(n); for (int i = 0; i < n; i++) { adj.Add(new List<int>()); foreach(int j in graph[i]) { adj[i].Add(j); } } // Final mask when all the node will be visited int finalMask = (1 << n) - 1; // Initialize a queue for BFS which will store // current node id and mask of visited nodes. Queue<Pair> q = new Queue<Pair>(); // Initialize a visited array for keeping track // of all mask that are visited in the path bool[, ] visited = new bool[n, finalMask + 1]; // Push starting node for // all possible path with their mask for (int i = 0; i < n; i++) { q.Enqueue(new Pair(i, (1 << i))); } // For counting the minimum time // to visit all the nodes int timeCount = 0; // Do while q.size > 0 while (q.Count > 0) { int size = q.Count; // Iterate over each level for (int i = 0; i < size; i++) { // Fetch and pop the current node Pair curr = q.Dequeue(); // Check if the current node mask // is equal to finalMask if (curr.getValue() == finalMask) return timeCount; // Explore all the child of current node foreach(int child in adj[curr.getKey()]) { // Make a new Mask for child int newVisitedBit = curr.getValue() | (1 << child); // If new Mask for child has // not been visited yet, // push child and new Mask in // the queue and mark visited // for child with newVisitedBit if (visited[child, newVisitedBit] == false) { q.Enqueue( new Pair(child, newVisitedBit)); visited[child, newVisitedBit] = true; } } } // Increment the time Count after each level timeCount++; } // If all node can't be visited return -1; }}// Pair classclass Pair { public int first, second; public Pair(int first, int second) { this.first = first; this.second = second; } public int getKey() { return this.first; } public int getValue() { return this.second; }}// This code is contributed by Tapesh(tapeshdua420) |
Javascript
// JavaScript code to implement the approach// Function to calculate the minimum timefunction minimizeTime(graph){ var n = graph.length; // Create adjacency list from the given graph var adj = []; for(var i=0;i<n;i++){ adj.push([]); for(var j=0;j<graph[i].length;j++){ adj[i].push(graph[i][j]); } } // Final mask when all the node will be visited var finalMask = (1<<n) - 1; // Initialize a queue for BFS which will store current // node id and mask of visited nodes. var q = []; // Initialize a visited array for keeping track // of all mask that are visited in the path var visited = []; for(var i=0;i<n;i++){ visited.push([]); for(var j=0;j<=finalMask;j++){ visited[i].push(0); } } // Push starting node for // all possible path with their mask for(var i=0;i<n;i++){ q.push([i,1<<i]); } // For counting the minimum time // to visit all the nodes var timeCount = 0; // Do while q.size > 0 while(q.length > 0){ var size = q.length; // Iterate over each level for(var i=0;i<size;i++){ // Fetch and pop the current node var curr = q.shift(); // Check if the current node mask // is equal to finalMask if(curr[1] == finalMask){ return timeCount; } // Explore all the child of current node for(var j=0;j<adj[curr[0]].length;j++){ var child = adj[curr[0]][j]; // Make a new Mask for child var newVisitedBit = curr[1]|(1<<child); // If new Mask for child has // not been visited yet, // push child and new Mask in // the queue and mark visited // for child with newVisitedBit if(visited[child][newVisitedBit] == false){ q.push([child,newVisitedBit]); visited[child][newVisitedBit] = true; } } } // Increment the time Count after each level timeCount = timeCount + 1; } // If all node can't be visited return -1;}// Driver codevar graph = [[1,2,3],[2,0],[0,1],[0,4],[3]];// Function callvar minTime = minimizeTime(graph);console.log(minTime);// This code is contributed by Tapesh(tapeshdua420). |
Output
4
Time Complexity: O(V + E) where V is the number of vertices and E is the number of edges.
Auxiliary Space: O(V + E)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
