Advanced Coding Patterns for Interviews

0% completed

Previous
Next
Introduction to Articulation Points and Bridges Pattern

In any network, certain points or connections are crucial for maintaining its overall connectivity. These points, known as articulation points or cut vertices, are locations that, if removed, cause the network to break into disconnected parts. Basically, articulation points is a single point of failure in any given network. Identifying these points is essential for building resilient systems, whether it be computer networks, transportation grids, or communication systems.

Tarjan’s Algorithm provides an efficient way to find articulation points in a network, ensuring that potential single points of failure are addressed.

Articulation Point in Graph

In an undirected graph, an articulation point (or cut vertex) is a node that, if removed, causes the graph to break into more disconnected parts than it had before. This means that the node plays a crucial role in holding the network together.

To better understand this, let's first define what a connected component is. A connected component is a subset of a graph where every node is reachable from any other node in that subset by following a sequence of edges. In simple terms, it's a cluster where there is a path between every pair of nodes.

A node becomes an articulation point if, after its removal, the number of these connected components increases. In other words, removing that node causes the graph to split into more isolated clusters.

Understanding with an Example

Let's look at a simple example to illustrate this concept.

Consider a graph with six nodes connected as follows:

Image

Initially, all the nodes are part of a single connected component, meaning every node can be reached from any other node.

Scenario 1: Removing Node 6

If we remove node 6 from this graph, it splits into two disconnected parts:

Image

Since the removal of node 1 results in two separate groups, node 1 is an articulation point.

Scenario 2: Removing Node 5

Now, let's remove node 3. After removing node 5, the graph divides into three disconnected parts:

Image

Again, the removal of node 3 increases the number of connected components from one to three, making node 3 another articulation point.

Naive Approach to Find Articulation Points

To identify articulation points in a graph, a simple, straightforward approach is to examine each node one by one, removing it temporarily and checking whether its removal increases the number of connected components in the graph. If the number of connected components increases after removing a node, that node is identified as an articulation point.

Approach

  1. Initial Setup: Start with the entire graph and count the number of connected components.
  2. Node Removal Check:
    • For each node in the graph:
      • Temporarily remove the node and all edges connected to it.
      • Recalculate the number of connected components in the modified graph.
      • If the number of connected components increases, mark the node as an articulation point.
    • Restore the node and repeat the process for the next node.
  3. Result: After checking all nodes, the marked nodes will be the articulation points of the graph.

Pseudo Code

Here's the rewritten pseudocode:

1. Compute the number of connected components in graph G.
2. For each vertex V in G:
   - Temporarily remove vertex V from G to create a modified graph G'.
   - Perform a DFS traversal on G' to determine the number of connected components in G'.
   - If the number of connected components in G' is greater than in G, then V is an articulation point.
   - Restore vertex V back into the graph.

Complexity Analysis

  • Time Complexity: The naive approach involves removing each node once and recalculating the number of connected components. If there are V nodes and E edges in the graph:
    • The time to count connected components using DFS or BFS is O(V + E).
    • This needs to be repeated for every node, leading to an overall time complexity of O(V * (V + E)).
  • Space Complexity: The space complexity mainly depends on the storage of the graph and the visited set used in the DFS or BFS traversal, which is O(V + E).

This naive method can become quite slow for large graphs due to its high time complexity. Therefore, to handle larger inputs efficiently, we need a more optimized algorithm, such as Tarjan's Algorithm, which reduces the time complexity significantly.

Tarjan's Algorithm to Find Articulation Points

Tarjan's Algorithm is an efficient method to find all the articulation points in a graph using Depth-First Search (DFS). The algorithm leverages the discovery time of each node and the lowest point reachable from its subtree to determine whether a node is a critical connection.

Case 1: When the Root Node of a DFS Tree Can Be an Articulation Point

In a DFS traversal, the root node is the starting point of the search within a connected component of a graph. A root node can be an articulation point if it has multiple children in the DFS tree that are not interconnected. This means that if the root node is removed, it will split the graph into multiple disconnected components.

Understanding the Root Node as an Articulation Point:

Let’s consider a graph where we start the DFS traversal from vertex 4. Here, vertex 4 becomes the root of our DFS tree.

  1. Scenario 1:
Image

In the above Figure 1, vertex 4 has three children: vertices 1, 2, and 3. Notice that the only way to travel between these child nodes is through vertex 4. If vertex 4 is removed, the graph splits into multiple disconnected parts (e.g., you can't reach vertices 3 and 1 from vertex 2 anymore). Therefore, vertex 4 is an articulation point because removing it increases the number of connected components in the graph.

  1. Scenario 2:
Image

In the above Figure 2, vertex 4 is again the root of the DFS tree. However, unlike Figure 1, all child nodes of vertex 4 are directly connected to each other. Even if we remove vertex 4, there are still paths available between nodes 2, 3, and 1. Hence, vertex 4 does not act as an articulation point in this scenario.

To summarize, the root node in a DFS traversal is an articulation point if it has more than one child that belongs to different subgraphs. The removal of this node would increase the number of disconnected components.

Step-by-Step Algorithm for Case 1

  1. Initialize DFS Traversal:

    • Start DFS from any node; this becomes the root node.
    • Set the parent of the root node to -1 to signify it has no parent.

  2. Count Children of Root Node:

    • Initialize childCount to 0.

  3. Traverse Through Each Child:

    • For every adjacent node (child node) of the current root:
      • If the child is not visited:
        • Increment childCount by 1.
        • Set the parent of this child to the current root.

  4. Recursive DFS Call:

    • Perform a DFS call on the child to explore further.

  5. Check for Articulation Point:

    • After visiting all children, if the current node is the root (parent[currentNode] == -1) and childCount > 1, mark it as an articulation point.

Pseudocode for Case 1:

void dfsForRootArticulation(int currentNode, vector<int> &parent) {
    int childCount = 0; // Initialize child count of the root node as 0
    
    for each adjacentNode of currentNode {
        if (adjacentNode is not visited) {
            childCount++; // Increase the count of children for the root
            parent[adjacentNode] = currentNode; // Set the parent of adjacentNode
            dfsForRootArticulation(adjacentNode, parent); // Recursive DFS call
            
            // Check if the current node is the root
            // and if it has more than one child
            if (parent[currentNode] == -1 && childCount > 1) {
                // Mark the current node as an articulation point
                markArticulationPoint(currentNode);
            }
        }
    }
}

Case 2: When a Non-Root Node Can Be an Articulation Point

For a non-root node U in a DFS traversal, it can be an articulation point if it has a child V such that the subtree rooted at V does not have a back-edge to any of the ancestors of U. Let's understand this with the concept of back-edges.

What is a Back-Edge?

Image

A back-edge is an edge that connects a node to one of its ancestors in a DFS tree. For example, in the above diagram, vertex 6 is the root and during DFS, vertex 2 points back to vertex 6, this edge (2 → 6) is a back-edge. Similarly, an edge from node 4 to node 5 (4 → 5) is also a back-edge as node 5 is an ancestor of node 4.

Is an Edge to the Immediate Parent Considered a Back-Edge?

Yes, an edge from a child node to its immediate parent is technically a back-edge, but for finding articulation points, such edges are not considered. This is because when a node is removed, its direct connection to its parent does not exist in the modified graph.

Efficiently Finding Back-Edges

To efficiently determine if a node is an articulation point, we use two arrays:

  • discovery_time[]: This array keeps track of the time at which each node is first visited during the DFS traversal. The "time" here represents the order in which nodes are visited.
  • low[]: This array stores the earliest (smallest) discovery time that can be reached from a given node using any combination of its own edges and back-edges.

How to Update the low[] Array

  1. For a Tree Edge (an edge from a parent to a child in the DFS tree):

    • When visiting a child node from its parent during DFS, update the low value of the parent node by taking the minimum of its current low value and the low value of its child. This update ensures that the parent node is aware of any back-edges reachable through its children.
    • Update Rule:
      low[node] = min(low[node], low[child_node])

  2. For a Back-Edge (an edge that points back to an ancestor of the current node):

    • When a back-edge is found (a child points to an ancestor of the current node, excluding its direct parent), update the low value of the current node to be the minimum of its current low value and the discovery_time of the node that the back-edge points to. This captures the earliest reachable ancestor node using the back-edge.
    • Update Rule:
      low[node] = min(low[node], discovery_time[child_node])

Condition to Identify an Articulation Point

A non-root node U is an articulation point if there exists at least one child V such that:

  • Condition: low[V] >= discovery_time[U]

This condition means that there is no back-edge from any node in the subtree rooted at V to any ancestor of U. If this is true, removing U would separate V (and its subtree) from the rest of the graph, making U a critical connection point or articulation point.

Step-by-Step Algorithm for Case 2

  1. Initialize Discovery and Low Arrays:

    • Set all entries in discovery_time and low arrays to -1.

  2. Set Discovery and Low Time for Current Node:

    • For the current node, set discovery_time[current_node] and low[current_node] to the current DFS time.

  3. Increment Time for the Next Node Visit:

    • Increment the DFS time by 1.

  4. Traverse Each Child Node:

    • For every child of the current node:
      • If the child has not been visited:
        • Perform a DFS on the child.
        • Update low[current_node] to the minimum of low[current_node] and low[child].
        • Check if current_node is not the root and low[child] >= discovery_time[current_node].
        • If true, mark current_node as an articulation point.

  5. Handle Back-Edges:

    • If the edge is a back-edge (child is not a parent), update low[current_node] with discovery_time[child].

Pseudocode for Case 2

// Initialize discovery_time and low arrays with -1

void dfsForNonRootArticulation(int currentNode, vector<int>& discovery_time, vector<int>& low, int parent, int time) {
    // Step 2: Set discovery and low time for the current node
    discovery_time[currentNode] = low[currentNode] = time;
    time++; // Step 3: Increment the DFS time

    // Step 4: Traverse each child of the current node
    for each (adjacentNode of currentNode) {
        if (discovery_time[adjacentNode] == -1) { // If the child is not visited
            dfsForNonRootArticulation(adjacentNode, discovery_time, low, currentNode, time);

            // Update low value for the current node
            low[currentNode] = min(low[currentNode], low[adjacentNode]);

            // Check if the current node is an articulation point
            if (parent != -1 && low[adjacentNode] >= discovery_time[currentNode]) {
                markArticulationPoint(currentNode); // Mark as articulation point
            }
        }
        // Step 5: Handle back-edge, ignore edge to parent
        else if (adjacentNode != parent) {
            low[currentNode] = min(low[currentNode], discovery_time[adjacentNode]);
        }
    }
}

Implementation of Trajan's Algorithm to Find Articulation Point

Now, let's combine the logic from both cases to create a complete algorithm to find all articulation points in an undirected graph using Tarjan's Algorithm. The combined algorithm will check both scenarios:

  1. When the root node of the DFS tree is an articulation point.
  2. When any non-root node is an articulation point.

Step-by-Step Algorithm

  1. Initialize the Graph:

    • Create a graph with V vertices.
    • Initialize an adjacency list (adjList) to store the connections between vertices.
    • Provide a method (addEdge(u, v)) to add edges between nodes u and v.

  2. Prepare Data Structures for DFS Traversal:

    • Create four arrays:
      • discovery_time[]: Stores the time at which each vertex is first visited.
      • low[]: Stores the smallest discovery time reachable from a vertex.
      • parent[]: Keeps track of each vertex's parent in the DFS tree.
      • articulation_point[]: A boolean array that marks articulation points in the graph.
    • Initialize all arrays to default values (-1 for discovery_time, low, and parent, false for articulation_point).

  3. Start DFS Traversal for Each Node:

    • Iterate over all nodes in the graph.
    • If a node has not been visited (discovery_time[node] == -1), start a DFS from that node.

  4. DFS Function (Depth-First Search):

    • Initialize Discovery Time and Low Value:
      • Set the discovery_time[currentNode] and low[currentNode] to the current time.
      • Increment the time variable.
    • Traverse All Adjacent Nodes:
      • For each adjacent node:
        • If the Adjacent Node Is Not Visited:
          • Mark it as a child of currentNode and increase the child count.
          • Set the parent of adjacentNode as currentNode.
          • Recursively call DFS for adjacentNode.
          • Update Low Value After Recursive Call:
            • Update low[currentNode] to the minimum of low[currentNode] and low[adjacentNode] to ensure that the current node knows the earliest visited node reachable from its subtree.
          • Check for Articulation Point:
            • Case 1: Root Node Condition:
              • If currentNode is the root (its parent is -1) and it has more than one child, mark it as an articulation point.
            • Case 2: Non-Root Node Condition:
              • If currentNode is not the root (its parent is not -1) and low[adjacentNode] >= discovery_time[currentNode], mark it as an articulation point.
        • If the Adjacent Node Is Already Visited and Not Parent:
          • This edge is a back-edge.
          • Update low[currentNode] to the minimum of low[currentNode] and discovery_time[adjacentNode] to account for the back-edge.

  5. Output the Articulation Points:

    • After completing the DFS for all nodes, iterate through the articulation_point[] array and print all the marked articulation points.

Algorithm Walkthrough for the Example Input:

Given graph has 6 vertices and the following edges:

  • (0, 1)
  • (1, 2)
  • (1, 3)
  • (3, 4)
  • (4, 5)

Initialization:

  • V = 6
  • adjList = {0: [1], 1: [0, 2, 3], 2: [1], 3: [1, 4], 4: [3, 5], 5: [4]}
  • discovery_time[] = [-1, -1, -1, -1, -1, -1]
  • low[] = [-1, -1, -1, -1, -1, -1]
  • parent[] = [-1, -1, -1, -1, -1, -1]
  • articulation_point[] = [false, false, false, false, false, false]
  • time = 0

Step-by-Step DFS Traversal:

  1. Start DFS from Node 0:
    • currentNode = 0
    • discovery_time[0] = low[0] = 1 (time = 1)
    • No parent for root: parent[0] = -1
    • Traverse Adjacent Nodes of 0:
      • Node 1 is Unvisited:
        • children = 1 (increment child count)
Image
  1. DFS from Node 1:
    • currentNode = 1
    • discovery_time[1] = low[1] = 2 (time = 2)
    • Traverse Adjacent Nodes of 1:
      • Node 0 is Parent, Ignore.
      • Node 2 is Unvisited:
        • children = 1 (increment child count)
Image
  1. DFS from Node 2:
    • currentNode = 2
    • discovery_time[2] = low[2] = 3 (time = 3)
    • Traverse Adjacent Nodes of 2:
Image
  1. Continue DFS from Node 1:
    • Node 3 is Unvisited:
      • children = 2 (increment child count)
      • parent[3] = 1 (set parent of 3)
      • Recursively call dfs(3)
Image
  1. DFS from Node 3:
    • currentNode = 3
    • discovery_time[3] = low[3] = 4 (time = 4)
    • Traverse Adjacent Nodes of 3:
      • Node 1 is Parent, Ignore.
      • Node 4 is Unvisited:
Image
  1. DFS from Node 4:
    • currentNode = 4
    • discovery_time[4] = low[4] = 5 (time = 5)
    • Traverse Adjacent Nodes of 4:
      • Node 3 is Parent, Ignore.
      • Node 5 is Unvisited:
Image
  1. DFS from Node 5:
    • currentNode = 5
    • discovery_time[5] = low[5] = 6 (time = 6)
    • Traverse Adjacent Nodes of 5:
      • Node 4 is Parent, Ignore.
Image
  1. Continue DFS from Node 4:
Image

  1. Continue DFS from Node 3:

    • End of DFS for Node 3, return to Node 1.
    • Update low[1] = min(low[1], low[3]) = min(2, 4) = 2
    • Check for Articulation Point:
      • low[3] >= discovery_time[1] (4 >= 2), so node 1 is already marked as an articulation point.

  2. End DFS for Remaining Nodes:

    • Nodes 2, 3, 4, and 5 are already visited, no further DFS calls are needed.

Output Articulation Points

  • Articulation Points Identified:
    • Nodes: 1, 3, 4

Code

Python3
Python3
. . . .

Complexity Analysis

  • Time Complexity:
    The algorithm runs in O(V + E) time, where V is the number of vertices and E is the number of edges. This is because each node and edge is visited only once during the DFS traversal.

  • Space Complexity:
    The space complexity is O(V), mainly due to the storage required for arrays like discovery_time, low, parent, and articulation_point, and the adjacency list representation of the graph.

Applications of Articulation Points in Real-World Problems

Articulation points are crucial in many real-world scenarios where network connectivity is vital:

  1. Network Reliability: In computer networks, identifying articulation points helps prevent failures by ensuring backup paths are available.

  2. Transportation Networks: In road systems, articulation points highlight critical intersections or cities; their disruption can cause major traffic problems.

  3. Social Networks: Identifying key users or groups as articulation points helps understand influence and detect communities or clusters.

  4. Biological Networks: In protein interaction or metabolic networks, articulation points can identify critical proteins or enzymes for drug targeting.

  5. Power and Telecom Grids: In power grids and telecom networks, articulation points indicate critical infrastructure whose failure could cause widespread outages or service disruptions.

Now, let's start solving the problem on the Articulation Point and Bridge pattern.

.....

.....

.....

Like the course? Get enrolled and start learning!
Previous
Next