articulation points Algorithm

The articulation points algorithm, also known as cut vertices algorithm, is an essential graph theory algorithm that identifies the nodes (vertices) in a connected graph, whose removal would increase the number of connected components. In simpler terms, an articulation point is a vertex that, when removed along with its associated edges, disconnects the graph or makes it less connected. This algorithm has significant applications in network reliability, social network analysis, and finding vulnerabilities in structures, among others. The articulation points algorithm can be implemented using Depth-First Search (DFS). It involves traversing the graph and assigning unique depths to each visited node. During this traversal, the algorithm calculates the low-link values for each node, which represent the smallest depth value of any node reachable from the current node, either directly or indirectly through its children. Once the DFS is complete, nodes with certain conditions of depth and low-link values are marked as articulation points. For the root node, if it has at least two independent children, it is an articulation point. For non-root nodes, if the low-link value of any child is greater than or equal to the depth of the parent, then the parent is an articulation point. The algorithm has a time complexity of O(V+E), where V is the number of vertices and E is the number of edges in the graph.
# Finding Articulation Points in Undirected Graph
def computeAP(l):  # noqa: E741
    n = len(l)
    outEdgeCount = 0
    low = [0] * n
    visited = [False] * n
    isArt = [False] * n

    def dfs(root, at, parent, outEdgeCount):
        if parent == root:
            outEdgeCount += 1
        visited[at] = True
        low[at] = at

        for to in l[at]:
            if to == parent:
                pass
            elif not visited[to]:
                outEdgeCount = dfs(root, to, at, outEdgeCount)
                low[at] = min(low[at], low[to])

                # AP found via bridge
                if at < low[to]:
                    isArt[at] = True
                # AP found via cycle
                if at == low[to]:
                    isArt[at] = True
            else:
                low[at] = min(low[at], to)
        return outEdgeCount

    for i in range(n):
        if not visited[i]:
            outEdgeCount = 0
            outEdgeCount = dfs(i, i, -1, outEdgeCount)
            isArt[i] = outEdgeCount > 1

    for x in range(len(isArt)):
        if isArt[x] is True:
            print(x)


# Adjacency list of graph
data = {
    0: [1, 2],
    1: [0, 2],
    2: [0, 1, 3, 5],
    3: [2, 4],
    4: [3],
    5: [2, 6, 8],
    6: [5, 7],
    7: [6, 8],
    8: [5, 7],
}
computeAP(data)

LANGUAGE:

DARK MODE: