Strongly Connected Components (SCC)?
Strongly Connected Component(SCC)는 방향성 그래프(Directed Graph)에서, 모든 정점들이 서로 도달 가능한 서브그래프(subgraph)를 말합니다. 즉, 한 정점에서 시작해서 다른 모든 정점에 도달할 수 있고, 그 반대 방향으로도 모든 정점에 도달할 수 있는 경우입니다. 이는 유향 그래프의 연결성을 분석하는 데 중요한 개념입니다.
SCC는 다양한 분야에서 사용됩니다:
- 웹 크롤링: 웹 페이지들이 서로 연결되어 있는 방식 분석.
- 컴파일러: 모듈 간의 종속성 분석.
- 회로 설계: 전자 회로의 연결성을 분석하는 데 사용.
SCC를 찾는 대표적인 알고리즘은 Kosaraju’s Algorithm과 Tarjan’s Algorithm입니다.
JavaScript 예제 코드 (Kosaraju’s Algorithm)
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
// 깊이 우선 탐색 함수
function dfs(graph, v, visited, stack) {
visited[v] = true;
for (let i of graph[v]) {
if (!visited[i]) {
dfs(graph, i, visited, stack);
}
}
stack.push(v);
}
// 역방향 깊이 우선 탐색
function reverseDfs(graph, v, visited, component) {
visited[v] = true;
component.push(v);
for (let i of graph[v]) {
if (!visited[i]) {
reverseDfs(graph, i, visited, component);
}
}
}
// SCC를 찾는 함수 (Kosaraju's Algorithm)
function findSCC(graph) {
let stack = [];
let visited = new Array(graph.length).fill(false);
// 1단계: 정방향 그래프에서 DFS
for (let i = 0; i < graph.length; i++) {
if (!visited[i]) {
dfs(graph, i, visited, stack);
}
}
// 그래프를 역전환
let reverseGraph = Array.from(Array(graph.length), () => []);
for (let v = 0; v < graph.length; v++) {
for (let u of graph[v]) {
reverseGraph[u].push(v);
}
}
// 2단계: 역방향 그래프에서 DFS
visited.fill(false);
let sccList = [];
while (stack.length) {
let v = stack.pop();
if (!visited[v]) {
let component = [];
reverseDfs(reverseGraph, v, visited, component);
sccList.push(component);
}
}
return sccList;
}
// 그래프 정의
const graph = [[1], [2], [0, 3], [4], [5], [3]];
const scc = findSCC(graph);
console.log("Strongly Connected Components:", scc);
Rust 예제 코드 (Kosaraju’s Algorithm)
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
fn dfs(v: usize, graph: &Vec<Vec<usize>>, visited: &mut Vec<bool>, stack: &mut Vec<usize>) {
visited[v] = true;
for &i in &graph[v] {
if !visited[i] {
dfs(i, graph, visited, stack);
}
}
stack.push(v);
}
fn reverse_dfs(v: usize, reverse_graph: &Vec<Vec<usize>>, visited: &mut Vec<bool>, component: &mut Vec<usize>) {
visited[v] = true;
component.push(v);
for &i in &reverse_graph[v] {
if !visited[i] {
reverse_dfs(i, reverse_graph, visited, component);
}
}
}
fn find_scc(graph: Vec<Vec<usize>>) -> Vec<Vec<usize>> {
let mut stack = Vec::new();
let mut visited = vec![false; graph.len()];
// 1단계: 정방향 그래프에서 DFS
for v in 0..graph.len() {
if !visited[v] {
dfs(v, &graph, &mut visited, &mut stack);
}
}
// 그래프를 역전환
let mut reverse_graph = vec![Vec::new(); graph.len()];
for v in 0..graph.len() {
for &u in &graph[v] {
reverse_graph[u].push(v);
}
}
// 2단계: 역방향 그래프에서 DFS
visited.fill(false);
let mut scc_list = Vec::new();
while let Some(v) = stack.pop() {
if !visited[v] {
let mut component = Vec::new();
reverse_dfs(v, &reverse_graph, &mut visited, &mut component);
scc_list.push(component);
}
}
scc_list
}
fn main() {
let graph = vec![
vec![1],
vec![2],
vec![0, 3],
vec![4],
vec![5],
vec![3]
];
let scc = find_scc(graph);
println!("Strongly Connected Components: {:?}", scc);
}
사용 예시:
- 웹 그래프 분석: 여러 웹 페이지들이 상호 연결되어 있는지 분석.
- 프로그램 모듈 분석: 코드의 모듈 간의 의존성을 파악하는 데 사용.
- 네트워크 분석: 네트워크의 강한 연결 성분을 찾고, 끊기지 않는 서브네트워크를 분석.
이 코드는 Kosaraju의 알고리즘을 사용하여 Strongly Connected Components를 찾는 방법을 보여줍니다.
Strongly Connected Components (SCC)?
A Strongly Connected Component (SCC) in a directed graph is a subgraph where every vertex is reachable from every other vertex. In other words, for any vertex in the subgraph, you can travel to any other vertex and back. This concept is crucial when analyzing the connectivity of directed graphs.
SCCs are used in several domains:
- Web Crawling: Analyzing how web pages are linked to each other.
- Compilers: Analyzing module dependencies in programming.
- Circuit Design: Identifying the connectivity of electronic components in a circuit.
The most common algorithms to find SCCs are Kosaraju’s Algorithm and Tarjan’s Algorithm.
JavaScript Example (Kosaraju’s Algorithm)
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
// Depth-First Search function
function dfs(graph, v, visited, stack) {
visited[v] = true;
for (let i of graph[v]) {
if (!visited[i]) {
dfs(graph, i, visited, stack);
}
}
stack.push(v);
}
// Reverse DFS
function reverseDfs(graph, v, visited, component) {
visited[v] = true;
component.push(v);
for (let i of graph[v]) {
if (!visited[i]) {
reverseDfs(graph, i, visited, component);
}
}
}
// Function to find SCCs using Kosaraju's Algorithm
function findSCC(graph) {
let stack = [];
let visited = new Array(graph.length).fill(false);
// Step 1: Perform DFS on the original graph
for (let i = 0; i < graph.length; i++) {
if (!visited[i]) {
dfs(graph, i, visited, stack);
}
}
// Step 2: Reverse the graph
let reverseGraph = Array.from(Array(graph.length), () => []);
for (let v = 0; v < graph.length; v++) {
for (let u of graph[v]) {
reverseGraph[u].push(v);
}
}
// Step 3: Perform DFS on the reversed graph
visited.fill(false);
let sccList = [];
while (stack.length) {
let v = stack.pop();
if (!visited[v]) {
let component = [];
reverseDfs(reverseGraph, v, visited, component);
sccList.push(component);
}
}
return sccList;
}
// Example graph definition
const graph = [[1], [2], [0, 3], [4], [5], [3]];
const scc = findSCC(graph);
console.log("Strongly Connected Components:", scc);
Rust Example (Kosaraju’s Algorithm)
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
fn dfs(v: usize, graph: &Vec<Vec<usize>>, visited: &mut Vec<bool>, stack: &mut Vec<usize>) {
visited[v] = true;
for &i in &graph[v] {
if !visited[i] {
dfs(i, graph, visited, stack);
}
}
stack.push(v);
}
fn reverse_dfs(v: usize, reverse_graph: &Vec<Vec<usize>>, visited: &mut Vec<bool>, component: &mut Vec<usize>) {
visited[v] = true;
component.push(v);
for &i in &reverse_graph[v] {
if !visited[i] {
reverse_dfs(i, reverse_graph, visited, component);
}
}
}
fn find_scc(graph: Vec<Vec<usize>>) -> Vec<Vec<usize>> {
let mut stack = Vec::new();
let mut visited = vec![false; graph.len()];
// Step 1: Perform DFS on the original graph
for v in 0..graph.len() {
if !visited[v] {
dfs(v, &graph, &mut visited, &mut stack);
}
}
// Step 2: Reverse the graph
let mut reverse_graph = vec![Vec::new(); graph.len()];
for v in 0..graph.len() {
for &u in &graph[v] {
reverse_graph[u].push(v);
}
}
// Step 3: Perform DFS on the reversed graph
visited.fill(false);
let mut scc_list = Vec::new();
while let Some(v) = stack.pop() {
if !visited[v] {
let mut component = Vec::new();
reverse_dfs(v, &reverse_graph, &mut visited, &mut component);
scc_list.push(component);
}
}
scc_list
}
fn main() {
let graph = vec![
vec![1],
vec![2],
vec![0, 3],
vec![4],
vec![5],
vec![3]
];
let scc = find_scc(graph);
println!("Strongly Connected Components: {:?}", scc);
}
Usage Examples:
- Web Graph Analysis: Finding how different web pages link to each other.
- Program Module Analysis: Detecting dependency cycles between program modules.
- Network Analysis: Identifying strongly connected regions in a network.
This code demonstrates how to find Strongly Connected Components (SCCs) using Kosaraju’s algorithm.