Um_nik의 “Thing is what I don’t know” 게시물에 대한 댓글에서 많은 red coder가 SCC 알고리즘을 잘 모른다는 것을 알았습니다. 나만 그런게 아니었어…
또한 usaco.guide에서 SCC 알고리즘은 Gold 또는 Platinum이 아닌 Advanced에 있습니다.
예전부터 SCC알고리즘을 배우고 싶었는데 볼때마다 이해가 안되서 옮긴지 1년이 넘은거 같습니다.
또한 두 알고리즘의 가장 간결한 구현을 제시하고 개인적인 비교를 할 것입니다. 요약본이라 설명이 이상할 수 있습니다…
DFS 트리/포리스트란 무엇입니까?
연결된 그래프에서 dfs 순회를 그릴 때 나타나는 방향성 스패닝 트리를 dfs(깊이 우선 검색) 트리라고 합니다. 물론 여러 개가 있을 수 있습니다.
그래프가 연결되지 않은 경우 연결된 각 구성 요소에 대해 DFS 트리를 만들어 DFS 포리스트로 만들 수 있습니다.
그래프가 방향성인지 무방향성인지에 따라 dfs 트리의 구조가 약간 다릅니다.
유향 그래프의 경우 dfs 트리의 모서리는 네 가지 유형으로 분류할 수 있습니다.
- 트리 에지: DFS 트리에 자연스럽게 포함된 에지
- Forward Edge: 조상->후손 방향으로 가는 DFS 트리에 포함되지 않은 에지
- 백 에지: dfs 트리에 포함되지 않고 자손->조상 방향에 있는 에지.
- 가로 가장자리: 조상-후손 관계가 없는 가장자리
무향 그래프에는 전방 모서리와 절단 모서리가 없습니다. 반전된 모서리로만 처리됩니다. 직접 그려보시면 그 이유를 아실겁니다.
단순화를 위해 다음을 정의합니다.
- 검색 시작 시간: $s:V↦\mathbb N$
- 검색 종료 시간: $f:V↦\mathbb N$
SCC란?
유향 그래프는 어떤 노드로든 다른 노드로든 갈 수 있으면 강하게 연결된 것입니다.
모든 유향 그래프는 SCC(strongly connected component)로 나눌 수 있습니다. SCC는 모든 정점에서 다른 정점으로 이동할 수 있는 최대 정점 집합입니다. 구성 요소 다이어그램은 각 SCC를 새 꼭지점으로 만들고 여기에 포함된 모든 꼭지점의 가장자리를 새 꼭지점의 가장자리로 가정하여 구성할 수 있습니다. 이 시점에서 이 구성 요소 그래프는 방향성 비순환 그래프(DAG)의 형태를 취합니다. 이는 SCC의 정의에 따라 재귀를 통해 쉽게 증명할 수 있습니다.
코사라주의 알고리즘
알고리즘의 과정을 아무렇게나 열거하고 나니 왜 맞는지 생각이 나지 않았다.
그러므로 각 과정을 나름의 방식으로 하고자 하는 의도를 적어보도록 하겠습니다.
이 알고리즘은 먼저 dfs 연산을 사용하여 그래프 $G$에서 각 정점의 검색 종료 시간 $f(v)$를 찾습니다. 그런 다음 $G^T$의 $f(v)$에서 내림차순으로 정점을 선택하여 dfs를 수행합니다.
마지막으로 dfs-forest의 모든 dfs-tree는 그래프 $G$의 SCC입니다. $G^T$의 SCC이기도 합니다.
그냥 따라가면 이해하기 힘듭니다. 성분 그래프가 고유하기 때문에 먼저 생각하고 알고리즘이 올바른 성분 그래프를 찾는지 모니터링하는 느낌으로 생각합니다.
두 개의 SCC를 고려하십시오. $C_1\to C_2$가 첫 번째 SCC에 관계없이 첫 번째 dfs를 시작한 경우 $\max_{v\in C_1}f(v)>\max_{v\in c_2}f(v)$가 적용됩니다. $\min$ 또는 $s(v)$를 사용할 수 없다고 생각할 수도 있지만 작동하지 않습니다. 정말 이상한 일이야…
어쨌든 $f(v)$에서 내림차순으로 회전하면 한 SCC의 모든 것이 두 번째 dfs에 입력되고 가장자리가 반전되어 다른 SCC로 누출되지 않는다는 것은 말할 필요도 없습니다.
자세한 증거 지름길참고하는 것이 좋습니다
Tarjan의 알고리즘
한계점
단층선
숨은 참조는 무엇입니까?
BCC(Biconnected Components)에는 두 가지 유형이 있습니다.
중단점이 없는 구성요소 또는 중단선이 없는 구성요소로 정의할 수 있습니다. 전자가 대중적이고 차단이라는 정의인 것 같습니다.
선인장 그래픽
선인장 그래프에는 두 가지 정의가 있습니다.
- 선인장: 다음 세 가지 정의는 모두 동일합니다.
- 정의 1: 모든 에지는 기껏해야 하나의 단순 주기에 포함됩니다.
- 정의 2: 모든 주기에는 최대 하나의 공통 노드가 있습니다.
- 정의 3: 각 블록은 단순한 주기 또는 에지입니다.
- Vertex Cactus: 각 정점은 최대 하나의 단순 주기에 포함됩니다.
크라운 선인장은 더 강한 조건입니다. 정단 선인장은 항상 일반 선인장에 포함됩니다.
코드 차트
모르겠습니다. 아직 알고 싶지 않습니다. 아인타의 기여.
블록 컷 트리
좋은 개념은 아닌 것 같습니다.
무향 그래프가 BCC로 그룹화되면 BCC는 독립적이거나 중단점을 공유합니다.
따라서 각 BCC와 각 중단점을 꼭지점으로 간주하여 연결하면 블록 컷 트리라는 트리가 형성된다.