|
|
| Line 1: |
Line 1: |
| [[파일:강한 결합 요소.png|섬네일|강한 결합 요소 예시]]
| | #넘겨주기 [[강한 연결 요소]] |
| [[파일:SCC 예시.png|섬네일|SCC인 그래프]]
| |
| 강한 결합 요소(Strongly Connected Component, SCC)는 방향 그래프에서 모든 정점이 서로 도달 가능한 최대 부분 그래프를 의미한다. 즉, 강한 결합 요소 내부에서는 임의의 두 정점 u, v에 대해 u에서 v로 가는 경로와 v에서 u로 가는 경로가 모두 존재해야 한다.
| |
| | |
| * 즉 쉽게 말해, 직접 가든 다른 곳을 거치든 서로 갈 수 있는 정점의 집합이라고 보면 된다.
| |
| ** 만약, A, B, C, D가 서로 갈 수 있는 길이 있는데, E는 A, B, C, D로 모두 갈 수 있는 반면, E에서 D로 가는 길만 없다면, E는 강한 결합 요소가 아니게 된다.
| |
| * 사이클이 있다면 그 사이클의 구성요소는 무조건 강한 결합 요소이다.
| |
| | |
| ==개요==
| |
| 방향 그래프(Directed Graph)에서 강한 결합 요소는 다음과 같은 성질을 만족하는 최대 부분 그래프이다.
| |
| *'''SCC''' 내부의 모든 정점 쌍 (u, v)에 대해 '''u → v''', '''v → u'''인 경로가 존재한다.
| |
| *'''SCC'''를 정점으로 축소하면 '''DAG(방향 비순환 그래프, Directed Acyclic Graph)'''를 형성한다.
| |
| 예를 들어, 다음 방향 그래프를 고려하자.
| |
| 1 → 2 → 3
| |
| ↑ ↓ ↓
| |
| 4 ← 5 → 6 ↔ 7
| |
| 이 그래프의 강한 결합 요소는 다음과 같다.
| |
| *{1, 2, 4, 5} - 서로 왕복 가능한 경로가 존재
| |
| *{6, 7} - 서로 직접 왕복 가능
| |
| *나머지는 모두 강한 결합 요소가 아니다. '''만약''' 7이 3으로 가는 경로가 존재했다면 {3, 6, 7}이은 강한 결합요소였을 것이다.
| |
| ==강한 결합 요소 찾기 알고리즘==
| |
| 강한 결합 요소를 찾는 대표적인 알고리즘으로는 '''코사라주 알고리즘(Kosaraju's Algorithm)'''과 '''타잔 알고리즘(Tarjan's Algorithm)'''이 있다. 각 구현 코드는 각 문서를 참고하자.
| |
| ===[[코사라주 알고리즘|코사라주 알고리즘(Kosaraju's Algorithm)]]===
| |
| 코사라주 알고리즘은 '''DFS(깊이 우선 탐색)'''을 두 번 수행하여 SCC를 찾는다.
| |
| #방향 그래프에서 '''DFS'''를 수행하여 탐색 완료 순서(탐색 종료 시간이 큰 순서)를 기록한다. | |
| #그래프의 방향을 '''반전(reverse)'''하여 모든 간선을 뒤집는다.
| |
| #반전된 그래프에서 '''DFS'''를 수행하되, '''탐색 종료 순서의 역순'''으로 시작하여 SCC를 찾는다.
| |
| ===[[타잔 알고리즘|타잔 알고리즘(Tarjan's Algorithm)]]===
| |
| 타잔 알고리즘은 **한 번의 DFS 탐색으로 SCC를 찾는 알고리즘**으로, 각 정점의 '''DFS 방문 순서(low-link 값)'''를 활용한다.
| |
| #'''DFS'''를 수행하며 각 노드의 방문 순서를 기록한다.
| |
| #'''DFS''' 탐색 중 가장 작은 도달 가능한 노드(low-link 값)를 갱신한다.
| |
| #'''DFS'''가 백트래킹할 때, 현재 노드의 low-link 값이 자신의 방문 순서와 같다면 SCC의 루트임을 확인하고 해당 SCC를 추출한다.
| |
| ==강한 결합 요소와 DAG==
| |
| SCC를 하나의 노드로 축소하면 방향 비순환 그래프(DAG)가 형성된다. 이는 그래프에서 사이클을 제거하고 위상 정렬을 수행할 때 유용하다.
| |
| | |
| 예를 들어, 아래 방향 그래프에서 SCC를 찾고 축소하면:
| |
| 1 → 2 → 3
| |
| ↑ ↓ ↓ ↖
| |
| 4 ← 5 → 6 ↔ 7
| |
| 강한 결합 요소: | |
| *{1, 2, 4, 5}
| |
| *{3, 6, 7}
| |
| SCC를 하나의 노드로 압축하면 DAG가 된다.
| |
| {1, 2, 4, 5} → {3, 6, 7}
| |
| | |
| == 구현 소스코드 ==
| |
| 아래는 SCC를 구하고 DAG까지 산출해주는 소스코드이다. 코르사주를 기반으로 하고 있지만 코르사주 알고리즘을 철저히 따르진 않고 좀 더 계량된 버전이다. 순수한 코르사주 알고리즘을 보고 싶다면 해당 문서를 참고하면 된다.<syntaxhighlight lang="python3">
| |
| from collections import defaultdict
| |
| | |
| # Step 1: Reverse Graph Function
| |
| def reverse_graph(graph):
| |
| """Reverse the directed graph"""
| |
| rev_graph = defaultdict(list)
| |
| for u in graph:
| |
| for v in graph[u]:
| |
| rev_graph[v].append(u)
| |
| return rev_graph
| |
| | |
| # Step 2: DFS for Reckless Ranking
| |
| def dfs_rank(graph, node, visited, stack):
| |
| """DFS to determine finishing times (Reckless Ranking)"""
| |
| visited.add(node)
| |
| for neighbor in graph[node]:
| |
| if neighbor not in visited:
| |
| dfs_rank(graph, neighbor, visited, stack)
| |
| stack.append(node) # Store nodes in finishing order
| |
| | |
| # Step 3: DFS for SCC Computation
| |
| def dfs_scc(graph, node, visited, component):
| |
| """DFS to extract strongly connected components"""
| |
| visited.add(node)
| |
| component.append(node)
| |
| for neighbor in graph[node]:
| |
| if neighbor not in visited:
| |
| dfs_scc(graph, neighbor, visited, component)
| |
| | |
| # SCC Driver using iRank order
| |
| def scc_driver(graph, iRank):
| |
| """Compute SCCs by running DFS on G in iRank order"""
| |
| visited = set()
| |
| sccs = []
| |
| | |
| while iRank:
| |
| node = iRank.pop() # Process nodes in decreasing finishing order
| |
| if node not in visited:
| |
| component = []
| |
| dfs_scc(graph, node, visited, component)
| |
| sccs.append(component)
| |
| | |
| return sccs
| |
| | |
| # Kosaraju-Sharir SCC Algorithm
| |
| def find_sccs(graph):
| |
| """Compute SCCs using Kosaraju-Sharir Algorithm with iRank"""
| |
| rev_graph = reverse_graph(graph)
| |
|
| |
| # Step 2: Reckless Ranking (DFS on G_rev to get finishing times)
| |
| visited = set()
| |
| stack = []
| |
| for node in graph:
| |
| if node not in visited:
| |
| dfs_rank(rev_graph, node, visited, stack)
| |
| | |
| # Step 3: SCC Computation using SCC Driver (DFS on G in iRank order)
| |
| sccs = scc_driver(graph, stack)
| |
| return sccs
| |
| | |
| # Step 4: Compute Reduced Graph G^c
| |
| def build_reduced_graph(graph, sccs):
| |
| """Build the reduced graph G^c where each SCC is treated as a single node"""
| |
| scc_map = {node: i for i, scc in enumerate(sccs) for node in scc}
| |
| reduced_graph = defaultdict(set)
| |
| | |
| for u in graph:
| |
| for v in graph[u]:
| |
| if scc_map[u] != scc_map[v]: # Only keep inter-SCC edges
| |
| reduced_graph[scc_map[u]].add(scc_map[v])
| |
|
| |
| return reduced_graph, scc_map
| |
| | |
| # Corrected Graph Definition (G9)
| |
| graph_G9 = {
| |
| "a": ["d"],
| |
| "b": ["a", "c"],
| |
| "c": ["b"],
| |
| "d": ["g", "h"],
| |
| "e": ["a", "b", "h", "i"],
| |
| "f": ["c", "e"],
| |
| "g": ["h"],
| |
| "h": ["a"],
| |
| "i": ["f", "h"]
| |
| }
| |
| | |
| # Execute SCC Algorithm with iRank
| |
| sccs = find_sccs(graph_G9)
| |
| reduced_graph, scc_map = build_reduced_graph(graph_G9, sccs)
| |
| | |
| # Print SCC Results
| |
| print("\n📌 Strongly Connected Components (SCCs):")
| |
| for i, scc in enumerate(sccs, 1):
| |
| print(f" SCC {i}: {scc}")
| |
| | |
| # Print Reduced Graph
| |
| print("\n📌 Corrected Reduced Graph (G^c):")
| |
| for scc_id, neighbors in reduced_graph.items():
| |
| print(f" SCC {sccs[scc_id]} → { [sccs[n] for n in neighbors] }")
| |
| </syntaxhighlight>실행 결과
| |
| 📌 Strongly Connected Components (SCCs):
| |
| SCC 1: ['a', 'd', 'g', 'h']
| |
| SCC 2: ['b', 'c']
| |
| SCC 3: ['f', 'e', 'i']
| |
|
| |
| 📌 Corrected Reduced Graph (G^c):
| |
| SCC ['b', 'c'] → <nowiki>[['a', 'd', 'g', 'h']]</nowiki>
| |
| SCC ['f', 'e', 'i'] → [['a', 'd', 'g', 'h'], ['b', 'c']]
| |
| | |
| ==강한 결합 요소의 활용==
| |
| #'''그래프 압축''' - 강한 결합 요소를 노드로 변환하여 DAG로 단순화 가능.
| |
| #'''위상 정렬''' - SCC를 DAG로 변환 후 정렬하여 순서를 분석.
| |
| #'''2-SAT 문제 해결''' - 논리식에서 강한 결합 요소를 이용해 만족 가능성을 판별.
| |
| #'''인터넷 네트워크 분석''' - 통신망에서 강한 결합된 컴포넌트를 찾는 데 활용.
| |
| ==같이 보기==
| |
| *[[깊이 우선 탐색]]
| |
| *[[위상 정렬]]
| |
| *[[방향 비순환 그래프|DAG (방향 비순환 그래프)]]
| |
| *[[코사라주 알고리즘]]
| |
| *[[타잔 알고리즘]]
| |
