Path visiting all nodes

The idea here is to do a depth-first search from all ‘N’ nodes and try all possible paths that visit all the nodes in the given graph. Out of all possible paths that start from any node ‘i’ and end at any node ‘j’, where ‘i’ and ‘j’ are from 0 to ‘N’ - 1 inclusive, we will take the path that has the shortest length, i.e., the path with the minimum number of edges and visits all the ‘N’ nodes in the given graph.

Algorithm:

• Declare a 2 - Dimensional array of integers, say ‘adjList’,  to store the adjacency list of the given graph.
• Build the adjacency list using the ‘edges’ array given in the problem.
• Declare an integer, say ‘minLength’, to store the length of the shortest path that visits all the ‘N’ nodes in the given graph and initialize it with 2 * ‘N’
• Declare an ‘N’ bit integer, say ‘visited’, where the i-th bit denotes whether the i-th node is visited or not, and initialize it with 0.
• Declare a 2 - Dimensional array of booleans, say ‘inProcess’, of size N * 2 ^ N, to avoid cycles during the depth-first search and initialize it with false.
• Run a loop for ‘i’ from 0 to ‘N’ - 1
  • Declare an integer, say ‘currVisited’, and initialize it with ‘visited’.
  • Mark the i-th bit of ‘currVisited’ as 1.
  • Call the ‘depthFirstSearch’ function with ‘i’, ‘currVisited’, ‘inProcess’ and ‘adjList’ as arguments, and store its returned value in ‘currLength’
  • Update ‘minLength’ as the minimum of ‘minLength’ and ‘currLength’.
• Return the maximum of ‘minLength’ - 1 and 0.

Description of ‘depthFirstSearch’ function

This function is used to traverse the given graph and find the length of the shortest path that visits all the ‘N’ nodes.

This function will take four parameters :

• node: An integer denoting the node in the given graph.
• visited: An ‘N’ bit integer denoting the visited nodes.
• inProcess: A 2 - Dimensional array of booleans to avoid cycles.
• adjList: A 2 - Dimensional array of integers denoting the adjacency list of the given graph.

int depthFirstSearch(node, visited, inProcess, adjList)

• If all the bits of ‘visited’ is 1, then return 0.
• Declare an integer, say ‘minLength’, to store the length of the shortest path that visits all the ‘N’ nodes in the given graph and initialize it with 2 * ‘N’
• If  ‘inProcess[node][visited]’ is false:
  • Mark ‘inProcess[node][visited]’ as true.
  • Run a loop for ‘i’ from 0 to the size of adjList[node] - 1
    • Declare an integer, say ‘currVisited’, and initialize it with ‘visited’.
    • Mark the ‘node’ bit of ‘currVisited’ as 1.
    • Call the ‘depthFirstSearch’ function with ‘adjList[node][i]’, ‘currVisited’, ‘inProcess’ and ‘adjList’ as arguments, and store its returned value in ‘currLength’.
    • Update ‘minLength’ as the minimum of ‘minLength’ and ‘currLength’ + 1.
  • Mark ‘inProcess[node][visited]’ as false.
• Return ‘minLength’

O(N ^ N + M), where ‘N’ is the number of nodes and ‘M’ is the number of edges in the given graph.

Here, building the adjacency list will take O(M) time since we have ‘M’ edges to insert in the adjacency list.

In the worst case, we can have 2 * N - 1 nodes in the shortest path, this case occurs when the given graph is a star graph, and for every node, we have ‘N’ choices. Therefore there will be approximately N ^ N different possible paths.

Hence, the overall time complexity will be O(M) + O(N ^ N), which is O(N ^ N +  M).

O(M + N + (N * 2 ^ N)), where ‘N’ is the number of nodes and ‘M’ is the number of edges in the given graph.

We are using an adjacency list that takes O(M) space to insert ‘M’ edges into the list. Moreover, we need O(N) extra space in the form of recursive calls for depth-first search when the given graph is a path graph. Also, O(N * (2 ^  N)) space is taken by the ‘inProcess’ array.
Hence, the overall space complexity will be O(M) + O(N) + O(N * (2 ^  N)), which is O(M + N + N * (2 ^  N)).