-
-
Notifications
You must be signed in to change notification settings - Fork 2.6k
/
articulationpoints.go
89 lines (75 loc) · 2.94 KB
/
articulationpoints.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
// Package graph provides algorithms to analyze graph structures.
package graph
import "github.com/TheAlgorithms/Go/math/min"
// apHelper stores auxiliary data used to identify articulation points in a graph.
type apHelper struct {
isAP []bool
visited []bool
childCount []int
discoveryTime []int
earliestDiscovery []int
}
// ArticulationPoint identifies articulation points in a graph. It returns a boolean slice
// where each element indicates whether a vertex is an articulation point.
// Worst Case Time Complexity: O(|V| + |E|)
// Auxiliary Space: O(|V|)
// Reference: https://en.wikipedia.org/wiki/Biconnected_component and https://cptalks.quora.com/Cut-Vertex-Articulation-point
func ArticulationPoint(graph *Graph) []bool {
// Time variable to keep track of the discovery time of a vertex
time := 0
// Initialize apHelper instance with the required data structures
apHelperInstance := &apHelper{
isAP: make([]bool, graph.vertices),
visited: make([]bool, graph.vertices),
childCount: make([]int, graph.vertices),
discoveryTime: make([]int, graph.vertices),
earliestDiscovery: make([]int, graph.vertices),
}
// Start traversal from the root (0)
articulationPointHelper(apHelperInstance, 0, -1, &time, graph)
// Check if the root has only one child, making it non-articulate
if apHelperInstance.childCount[0] == 1 {
apHelperInstance.isAP[0] = false
}
return apHelperInstance.isAP
}
// articulationPointHelper recursively traverses the graph using DFS and marks articulation points.
// It updates `childCount`, `discoveryTime`, and `earliestDiscovery` slices for the given vertex.
func articulationPointHelper(
apHelperInstance *apHelper,
vertex int,
parent int,
time *int,
graph *Graph,
) {
apHelperInstance.visited[vertex] = true
// Set discovery and earliest discovery times for the vertex
apHelperInstance.discoveryTime[vertex] = *time
apHelperInstance.earliestDiscovery[vertex] = *time
*time++
for nextVertex := range graph.edges[vertex] {
if nextVertex == parent {
continue
}
if apHelperInstance.visited[nextVertex] {
// Update the earliest discovery time to the smallest reachable discovery time
apHelperInstance.earliestDiscovery[vertex] = min.Int(
apHelperInstance.earliestDiscovery[vertex],
apHelperInstance.discoveryTime[nextVertex],
)
continue
}
// Increment child count and perform recursive traversal for DFS
apHelperInstance.childCount[vertex]++
articulationPointHelper(apHelperInstance, nextVertex, vertex, time, graph)
// Update the earliest discovery time post DFS
apHelperInstance.earliestDiscovery[vertex] = min.Int(
apHelperInstance.earliestDiscovery[vertex],
apHelperInstance.earliestDiscovery[nextVertex],
)
// Mark vertex as articulation point if condition meets
if apHelperInstance.earliestDiscovery[nextVertex] >= apHelperInstance.discoveryTime[vertex] {
apHelperInstance.isAP[vertex] = true
}
}
}