Critical Connection

If we observe carefully the critical connection is a similar bridge in a graph(edge whose removal increases the number of components in a graph).

The idea is to do Depth first search(DFS) traversal of the given graph. In DFS tree an edge (‘u’, ‘ v’) (‘u’ is parent of ‘v’ in DFS tree) is bridge if there does not exist any other alternative to reach ‘u’ or an ancestor of ‘u’ from subtree rooted with ‘v’.

In order to implement the above thought, we will maintain two arrays :

• low[] : the value low[v] indicates earliest visited vertex reachable from subtree rooted with v.
• Disc[]: the value of disc[u] indicates the discovery time of node ‘u’.
• The condition for an edge (u, v) to be a bridge is, “low[v]  >  disc[u]”.

 The steps are as follows :

We will use  following variables :

• timer,  to keep track of discovery time.
• ‘disc’ array, the value of disc[u] indicates the discovery time of node ‘u’.
• ‘low’  array, the value low[v] indicates earliest visited vertex reachable from subtree rooted with v.
• visited  array, mark whether node ’i’ is visited or not.
• Array of list, to construct graph.

Let  ‘criticalConnection(n, ‘connections’)’ be the function that returns all the critical connections in a network, where ‘n’ is the number of nodes in a given network and ‘connections’ contain all connections.

• Take a variable ‘timer’, Initialize ‘timer’ to 0.
• Take an array ‘disc’ of length ‘n’.
• Take an array ‘visited’ of length.
• Take an array ‘low’ of length.
• Take a variable ‘m’ and initialize it with the size of connections array.
• Run a loop from 0 to ‘m’:
  • Take a variable ‘u’ and store the first element of connections[i].
  • Take a variable ‘v’ and store the second element of connections[i].
  • Push ‘u’ in graph[v].
  • Push ‘v’ in graph[u].
• Take an array ‘ans’ to store the critical connections.
• Run a loop from 0 to ‘n’:
  • Initialize disc[i] with 0.
  • Initialize low[i] with large value.
  • Initialize visited[i] with 0.
• Make a function dfs(start, ‘ans’, parent, ‘disc’, ‘low’, ‘visited’, ‘graph’, ‘timer’) , to find all the critical connection:
  • Run a loop from 0 to ‘n’ - 1
    • If visited[i] is equal to 0
    • Call dfs(start, ‘ans’, parent, ‘disc’, ‘low’, ‘visited’, ‘graph’, ‘timer’) function
  • Return ‘ans’ array.

Description of ‘dfs(‘start(s)’, ‘ans’, parent(p),‘disc’, ‘low’, ‘visited’, ‘graph’, ‘timer’)’ function

This utility function finds all the critical connections in a network.

• Mark ‘visited[s]’ equal to 1.
• Increment the ‘timer’ by 1.
• Store the ‘timer’ in ‘disc[s]’ and ‘low[s]’.
• Run a loop from 0 to size of graph[s] array ( number of nodes adjacent to the node ‘s’)
  • Take a variable ‘adj’ and initialize it with graph[s][i].
  • Check if this adjacent node ‘adj’ is visited or not, if visited:
    • Recursively call dfs(‘adj’, ans, ‘s’).
    • Update ‘low[s]’ equal to min of ( low[adj]’ and ‘low[s]’).
    • If ‘low[adj]’ is greater than ‘disc’ of ‘s’, this is a critical connection store in ‘ans’ array.
      • Take a temporary array ‘temp’.
      • Push min of ‘s’ and ‘adj’ in temp.
      • Push max of ‘s’ and ‘adj’ in temp.
  • Else if ‘adj’ is not the parent of ‘s’ i.e ‘p’:
    • Update ‘low[s]’ as minimum of ‘low[adj]’ and ‘low[s]’.

O(M + N), where ‘N’ is the number of nodes and ‘M’ is the number of connections.

We are using the standard ‘dfs’ function that takes O(N + M). Hence, the overall time complexity is O(N + M).

 O(M + N), where ‘N’ is the number of nodes and ‘M’ is the number of connections.

Mainly, We are using space in creating a graph, which takes O(N + M) space, visited array, which takes O(N) space, ‘low’ array which takes O(N) space, ‘disc’ array which takes O(N) space. Hence, the overall space complexity is  O(N + M) + 3 * O(N) =  O(N + M).