맨위로가기

코사라주 알고리즘

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
목차

1. 개요

코사라주 알고리즘은 유향 그래프에서 강하게 연결된 요소를 찾는 알고리즘이다. 이 알고리즘은 그래프의 정점을 열거하고, 정점별 데이터를 저장하며, 순방향 및 역방향 이웃 정점을 열거하는 연산을 기반으로 한다. 코사라주 알고리즘은 깊이 우선 탐색(DFS) 또는 너비 우선 탐색(BFS)을 사용하여 구현할 수 있으며, 세 단계를 거쳐 작동한다. 첫 번째 단계에서는 DFS를 수행하여 각 정점의 후위 순서를 기록하고, 두 번째 단계에서는 원본 그래프의 간선 방향을 뒤집은 역방향 그래프를 생성하며, 마지막 단계에서는 역방향 그래프에서 DFS를 수행하여 강한 연결 요소를 할당한다. 시간 복잡도는 그래프가 인접 리스트로 주어질 경우 Θ(V+E)이며, 인접 행렬로 주어질 경우 Ο(V2)이다.

더 읽어볼만한 페이지

  • 그래프 알고리즘 - 페이지랭크
    페이지랭크는 래리 페이지와 세르게이 브린이 개발한 알고리즘으로, 하이퍼링크로 연결된 문서 집합에서 웹 페이지의 상대적 중요도를 측정하며, 링크를 투표로 간주하여 페이지 순위를 재귀적으로 결정하고, 구글 검색 엔진의 초기 핵심 알고리즘으로 활용되었으며, 다양한 분야에서 활용된다.
  • 그래프 알고리즘 - 너비 우선 탐색
    너비 우선 탐색은 그래프 탐색 알고리즘으로, 큐 자료구조를 사용하여 시작 노드에서 인접한 노드들을 우선적으로 탐색하며, 가중치가 없는 그래프에서 최단 경로를 찾는 데 유용하고 다양한 분야에 활용된다.
코사라주 알고리즘

2. 알고리즘

코사라주 알고리즘은 다음의 네 가지 그래프 연산을 기반으로 한다.


  • 그래프의 정점들을 열거하는 연산
  • 정점마다 데이터를 저장하는 연산 (그래프의 자료 구조 안에 저장하거나, 정점들을 인덱스로 하는 배열에 저장)
  • 정점에서 나가는 방향의 이웃(순방향 이웃) 정점들을 열거하는 연산 (순방향 탐색)
  • 정점에서 들어오는 방향의 이웃(역방향 이웃) 정점들을 열거하는 연산 (역방향 탐색)


마지막 연산은 원본 그래프를 역방향 그래프로 표현하여 순방향 순회 시 비용 없이 가능하다. 이 알고리즘에 필요한 유일한 자료 구조는 각 정점을 한 번씩 포함하는 정점들의 순서가 매겨진 목록 ''L''이다.

알고리즘의 핵심은 첫 번째 (순방향) 순회 때 정점들이 후위 순서로 목록 ''L''에 추가된다는 것이다. 즉, 정점 ''v''가 처음 방문되었는지, 아니면 방문된 다른 정점 ''u''의 바깥 이웃이었는지에 관계없이, ''v''는 ''u''보다 먼저 ''L''에 추가된다. 따라서 ''u''에서 ''v''로의 순방향 경로가 있다면, ''u''는 최종 목록 ''L''에서 ''v''보다 앞에 나타난다. (''u''와 ''v''가 같은 강한 연결 요소에 포함되지 않는다면, ''L''에서의 상대적 순서는 임의적이다.)

간결함을 위해 깊이 우선 탐색을 채용한 알고리즘이 주로 기술되지만, 후위 순서의 특성이 보존되는 경우 너비 우선 탐색에도 적용 가능하다.

== 1단계: 깊이 우선 탐색 (DFS) 및 후위 순서 기록 ==

코사라주 알고리즘의 첫 번째 단계는 깊이 우선 탐색(DFS)을 수행하고, 각 정점의 탐색 완료 순서(후위 순서)를 기록하는 것이다. 이 과정에서 정점들은 탐색 순서와 상관없이 후위 순서로 목록 ''L''에 추가된다. 깊이 우선 탐색은 각 정점을 한 번씩 방문하며, 방문한 정점은 '방문함'으로 표시된다. 어떤 정점 ''u''를 방문했을 때, ''u''의 모든 바깥쪽 이웃 ''v''에 대해 재귀적으로 Visit(''v'')를 호출하여 탐색을 계속한다. 더 이상 방문할 이웃이 없으면, 해당 정점 ''u''를 목록 ''L''의 맨 앞에 추가한다.

이 알고리즘은 깊이 우선 탐색 외에도 너비 우선 탐색(BFS)을 사용할 수 있지만, 후위 순서의 특성이 유지되어야 한다. 핵심은 정점이 검색 트리에 상대적인 후위 순서로 목록에 추가되어야 한다는 점이다.

== 2단계: 역방향 그래프 생성 ==

코사라주 알고리즘의 두 번째 단계는 원본 그래프의 간선 방향을 뒤집은 역방향 그래프를 생성하는 것이다. 이 역방향 그래프는 이후 단계에서 강하게 연결된 요소를 찾는 데 사용된다.

역방향 그래프를 생성하는 연산은 그래프의 정점에서 들어오는 방향의 이웃(역방향 이웃) 정점들을 열거하는 연산(역방향 탐색)을 기반으로 한다. 이 연산은 순방향 탐색을 할 때 추가적인 비용 없이 수행할 수 있다. 즉, 원본 그래프에서 정점 A에서 정점 B로 가는 간선이 있다면, 역방향 그래프에서는 정점 B에서 정점 A로 가는 간선이 존재하게 된다.

이 알고리즘에서 유일하게 필요한 자료 구조는 각 정점을 한 번씩 포함하는 정점들의 정렬된 목록 ''L''이다.

== 3단계: 역방향 그래프에서 DFS 수행 ==

코사라주 알고리즘의 3단계는 ''L'' 목록의 각 원소 ''u''에 대해 역방향 그래프에서 깊이 우선 탐색(DFS)을 수행하여 강한 연결 요소를 할당하는 단계이다. 이 과정은 재귀적으로 수행되는 Assign(''u'',''u'') 함수를 통해 이루어진다.

Assign(''u'',''root'') 함수는 다음과 같이 작동한다.

  • 만약 ''u''가 아직 어떤 강한 연결 요소에도 할당되지 않았다면, ''u''를 ''root''를 루트로 하는 강한 연결 요소에 포함시킨다.
  • ''u''의 역방향 이웃 ''v''에 대해 Assign(''v'',''root'')를 재귀적으로 호출한다.
  • ''u''가 이미 다른 강한 연결 요소에 할당되었다면 아무것도 하지 않는다.


이 과정을 통해 각 정점은 자신이 속한 강한 연결 요소의 루트 정점으로 할당된다.

3단계에서는 L[0]에서 시작하여, 이를 가리키는 모든 정점을 L[0]과 동일한 요소로 할당한다. 이러한 정점은 L[0]을 시작으로 하는 블록에만 존재할 수 있으며, 더 높은 블록은 L[0]의 블록에 연결된 링크를 가질 수 없다. L[0]을 가리키는 모든 정점의 집합을 In(L[0])이라고 한다. 그 후, 이러한 정점을 가리키는 모든 정점, In(In(L[0]))도 추가되며 더 이상 정점을 추가할 수 없을 때까지 계속된다.

L[0]을 포함하는 요소에 추가된 모든 정점에서 L[0]으로 가는 경로가 있다. 그리고 모든 정점은 L[0]에서 시작하는 블록(경로의 각 단계에서 외부 간선을 따라 L[0]에서 도달할 수 있는 모든 정점을 포함)에 있으므로 추가된 모든 정점에 대한 경로가 있다. 따라서 이들은 모두 하나의 강력하게 연결된 요소를 형성한다. 또한, 정점이 이 강력하게 연결된 요소에 속하려면 L[0]에서 도달할 수 있어야 하고 L[0]에 도달할 수 있어야 하므로 정점이 남아 있지 않다. L[0]에 도달할 수 있는 모든 정점(있는 경우)은 첫 번째 블록에만 있고, 첫 번째 블록의 모든 정점은 L[0]에서 도달할 수 있다. 따라서 알고리즘은 L[0]의 연결 요소에 있는 모든 정점을 선택한다.

3단계 루프에서 정점 v = L[i]에 도달하고 v가 어떤 요소에도 할당되지 않은 경우, 왼쪽에 있는 모든 정점이 해당 연결 요소를 만들었음을 확신할 수 있다. v는 해당 요소에 속하지 않는다. v는 왼쪽에 있는 어떤 정점도 가리키지 않는다. 또한 더 높은 블록에서 v의 블록으로의 간선이 없으므로 증명은 동일하게 유지된다.

알고리즘은 정점 u의 강한 연결 요소를 후방 및 전방 순회를 통해 u에서 도달할 수 있는 정점 집합으로 식별하는 것으로 이해할 수 있다. 전방 순회를 통해 u에서 도달할 수 있는 정점 집합을 F(u), 후방 순회를 통해 u에서 도달할 수 있는 정점 집합을 B(u), 알고리즘의 2단계 후에 목록 L에 u 앞에 엄격하게 나타나는 정점 집합을 P(u)라고 쓰면 루트로 지정된 정점 u를 포함하는 강한 연결 요소는 다음과 같다.

: B(u) \cap F(u) = B(u) \setminus (B(u) \setminus F(u)) = B(u) \setminus P(u).

집합 교차는 계산 비용이 많이 들지만 이중 집합 차이와 논리적으로 동일하며, 이므로 새로 발견된 의 요소가 이미 요소에 할당되었는지 여부를 테스트하는 것으로 충분하다.

== 깊이 우선 탐색 (DFS) vs. 너비 우선 탐색 (BFS) ==

코사라주 알고리즘은 깊이 우선 탐색(DFS) 또는 너비 우선 탐색(BFS)을 사용하여 그래프의 강한 연결 요소를 찾는다. 알고리즘의 핵심은 정점들이 탐색 중인 검색 트리에 상대적인 후위 순서로 목록 L에 추가된다는 것이다. 이는 깊이 우선 탐색뿐만 아니라 너비 우선 탐색을 사용해도 동일하게 작동한다.

알고리즘은 정점 ''u''의 강한 연결 요소를 후방 및 전방 순회를 통해 ''u''에서 도달할 수 있는 정점 집합으로 식별한다. 전방 순회를 통해 ''u''에서 도달할 수 있는 정점 집합을 ''F''(''u''), 후방 순회를 통해 ''u''에서 도달할 수 있는 정점 집합을 ''B''(''u''), 알고리즘의 2단계 후에 목록 ''L''에 ''u'' 앞에 엄격하게 나타나는 정점 집합을 ''P''(''u'')라고 하면, 루트로 지정된 정점 ''u''를 포함하는 강한 연결 요소는 다음과 같이 표현된다.

: B(u) \cap F(u) = B(u) \setminus (B(u) \setminus F(u)) = B(u) \setminus P(u).

집합 교차는 계산 비용이 많이 들지만, 이중 집합 차이와 논리적으로 동일하며, 이므로 새로 발견된 의 요소가 이미 요소에 할당되었는지 여부를 테스트하는 것으로 충분하다.

2. 1. 1단계: 깊이 우선 탐색 (DFS) 및 후위 순서 기록

코사라주 알고리즘의 첫 번째 단계는 깊이 우선 탐색(DFS)을 수행하고, 각 정점의 탐색 완료 순서(후위 순서)를 기록하는 것이다. 이 과정에서 정점들은 탐색 순서와 상관없이 후위 순서로 목록 ''L''에 추가된다. 깊이 우선 탐색은 각 정점을 한 번씩 방문하며, 방문한 정점은 '방문함'으로 표시된다. 어떤 정점 ''u''를 방문했을 때, ''u''의 모든 바깥쪽 이웃 ''v''에 대해 재귀적으로 Visit(''v'')를 호출하여 탐색을 계속한다. 더 이상 방문할 이웃이 없으면, 해당 정점 ''u''를 목록 ''L''의 맨 앞에 추가한다.

이 알고리즘은 깊이 우선 탐색 외에도 너비 우선 탐색(BFS)을 사용할 수 있지만, 후위 순서의 특성이 유지되어야 한다. 핵심은 정점이 검색 트리에 상대적인 후위 순서로 목록에 추가되어야 한다는 점이다.

2. 2. 2단계: 역방향 그래프 생성

코사라주 알고리즘의 두 번째 단계는 원본 그래프의 간선 방향을 뒤집은 역방향 그래프를 생성하는 것이다. 이 역방향 그래프는 이후 단계에서 강하게 연결된 요소를 찾는 데 사용된다.

역방향 그래프를 생성하는 연산은 그래프의 정점에서 들어오는 방향의 이웃(역방향 이웃) 정점들을 열거하는 연산(역방향 탐색)을 기반으로 한다. 이 연산은 순방향 탐색을 할 때 추가적인 비용 없이 수행할 수 있다. 즉, 원본 그래프에서 정점 A에서 정점 B로 가는 간선이 있다면, 역방향 그래프에서는 정점 B에서 정점 A로 가는 간선이 존재하게 된다.

이 알고리즘에서 유일하게 필요한 자료 구조는 각 정점을 한 번씩 포함하는 정점들의 정렬된 목록 ''L''이다.

2. 3. 3단계: 역방향 그래프에서 DFS 수행

코사라주 알고리즘의 3단계는 ''L'' 목록의 각 원소 ''u''에 대해 역방향 그래프에서 깊이 우선 탐색(DFS)을 수행하여 강한 연결 요소를 할당하는 단계이다. 이 과정은 재귀적으로 수행되는 Assign(''u'',''u'') 함수를 통해 이루어진다.

Assign(''u'',''root'') 함수는 다음과 같이 작동한다.

  • 만약 ''u''가 아직 어떤 강한 연결 요소에도 할당되지 않았다면, ''u''를 ''root''를 루트로 하는 강한 연결 요소에 포함시킨다.
  • ''u''의 역방향 이웃 ''v''에 대해 Assign(''v'',''root'')를 재귀적으로 호출한다.
  • ''u''가 이미 다른 강한 연결 요소에 할당되었다면 아무것도 하지 않는다.


이 과정을 통해 각 정점은 자신이 속한 강한 연결 요소의 루트 정점으로 할당된다.

3단계에서는 L[0]에서 시작하여, 이를 가리키는 모든 정점을 L[0]과 동일한 요소로 할당한다. 이러한 정점은 L[0]을 시작으로 하는 블록에만 존재할 수 있으며, 더 높은 블록은 L[0]의 블록에 연결된 링크를 가질 수 없다. L[0]을 가리키는 모든 정점의 집합을 In(L[0])이라고 한다. 그 후, 이러한 정점을 가리키는 모든 정점, In(In(L[0]))도 추가되며 더 이상 정점을 추가할 수 없을 때까지 계속된다.

L[0]을 포함하는 요소에 추가된 모든 정점에서 L[0]으로 가는 경로가 있다. 그리고 모든 정점은 L[0]에서 시작하는 블록(경로의 각 단계에서 외부 간선을 따라 L[0]에서 도달할 수 있는 모든 정점을 포함)에 있으므로 추가된 모든 정점에 대한 경로가 있다. 따라서 이들은 모두 하나의 강력하게 연결된 요소를 형성한다. 또한, 정점이 이 강력하게 연결된 요소에 속하려면 L[0]에서 도달할 수 있어야 하고 L[0]에 도달할 수 있어야 하므로 정점이 남아 있지 않다. L[0]에 도달할 수 있는 모든 정점(있는 경우)은 첫 번째 블록에만 있고, 첫 번째 블록의 모든 정점은 L[0]에서 도달할 수 있다. 따라서 알고리즘은 L[0]의 연결 요소에 있는 모든 정점을 선택한다.

3단계 루프에서 정점 v = L[i]에 도달하고 v가 어떤 요소에도 할당되지 않은 경우, 왼쪽에 있는 모든 정점이 해당 연결 요소를 만들었음을 확신할 수 있다. v는 해당 요소에 속하지 않는다. v는 왼쪽에 있는 어떤 정점도 가리키지 않는다. 또한 더 높은 블록에서 v의 블록으로의 간선이 없으므로 증명은 동일하게 유지된다.

알고리즘은 정점 u의 강한 연결 요소를 후방 및 전방 순회를 통해 u에서 도달할 수 있는 정점 집합으로 식별하는 것으로 이해할 수 있다. 전방 순회를 통해 u에서 도달할 수 있는 정점 집합을 F(u), 후방 순회를 통해 u에서 도달할 수 있는 정점 집합을 B(u), 알고리즘의 2단계 후에 목록 L에 u 앞에 엄격하게 나타나는 정점 집합을 P(u)라고 쓰면 루트로 지정된 정점 u를 포함하는 강한 연결 요소는 다음과 같다.

: B(u) \cap F(u) = B(u) \setminus (B(u) \setminus F(u)) = B(u) \setminus P(u).

집합 교차는 계산 비용이 많이 들지만 이중 집합 차이와 논리적으로 동일하며 이므로 새로 발견된 의 요소가 이미 요소에 할당되었는지 여부를 테스트하는 것으로 충분하다.

2. 4. 알고리즘의 핵심 원리

코사라주 알고리즘은 다음의 네 가지 그래프 연산을 기반으로 한다.

  • 그래프의 정점들을 열거하는 연산
  • 정점마다 데이터를 저장하는 연산 (그래프의 자료 구조 안에 저장하거나, 정점들을 인덱스로 하는 배열에 저장)
  • 정점에서 나가는 방향의 이웃(순방향 이웃) 정점들을 열거하는 연산 (순방향 탐색)
  • 정점에서 들어오는 방향의 이웃(역방향 이웃) 정점들을 열거하는 연산 (역방향 탐색)


마지막 연산은 원본 그래프를 역방향 그래프로 표현하여 순방향 순회 시 비용 없이 가능하다. 이 알고리즘에 필요한 유일한 자료 구조는 각 정점을 한 번씩 포함하는 정점들의 순서가 매겨진 목록 ''L''이다.

알고리즘의 핵심은 첫 번째 (순방향) 순회 때 정점들이 후위 순서로 목록 ''L''에 추가된다는 것이다. 즉, 정점 ''v''가 처음 방문되었는지, 아니면 방문된 다른 정점 ''u''의 바깥 이웃이었는지에 관계없이, ''v''는 ''u''보다 먼저 ''L''에 추가된다. 따라서 ''u''에서 ''v''로의 순방향 경로가 있다면, ''u''는 최종 목록 ''L''에서 ''v''보다 앞에 나타난다. (''u''와 ''v''가 같은 강한 연결 요소에 포함되지 않는다면, ''L''에서의 상대적 순서는 임의적이다.)

간결함을 위해 깊이 우선 탐색을 채용한 알고리즘이 주로 기술되지만, 후위 순서의 특성이 보존되는 경우 너비 우선 탐색에도 적용 가능하다.

2. 5. 깊이 우선 탐색 (DFS) vs. 너비 우선 탐색 (BFS)

코사라주 알고리즘은 깊이 우선 탐색(DFS) 또는 너비 우선 탐색(BFS)을 사용하여 그래프의 강한 연결 요소를 찾는다. 알고리즘의 핵심은 정점들이 탐색 중인 검색 트리에 상대적인 후위 순서로 목록 L에 추가된다는 것이다. 이는 깊이 우선 탐색뿐만 아니라 너비 우선 탐색을 사용해도 동일하게 작동한다.

알고리즘은 정점 ''u''의 강한 연결 요소를 후방 및 전방 순회를 통해 ''u''에서 도달할 수 있는 정점 집합으로 식별한다. 전방 순회를 통해 ''u''에서 도달할 수 있는 정점 집합을 ''F''(''u''), 후방 순회를 통해 ''u''에서 도달할 수 있는 정점 집합을 ''B''(''u''), 알고리즘의 2단계 후에 목록 ''L''에 ''u'' 앞에 엄격하게 나타나는 정점 집합을 ''P''(''u'')라고 하면, 루트로 지정된 정점 ''u''를 포함하는 강한 연결 요소는 다음과 같이 표현된다.

: B(u) \cap F(u) = B(u) \setminus (B(u) \setminus F(u)) = B(u) \setminus P(u).

집합 교차는 계산 비용이 많이 들지만, 이중 집합 차이와 논리적으로 동일하며, 이므로 새로 발견된 의 요소가 이미 요소에 할당되었는지 여부를 테스트하는 것으로 충분하다.

3. 시간 복잡도

그래프가 인접 리스트의 형태로 주어질 때, 코사라주 알고리즘은 두 번의 그래프 순회를 수행하므로 Θ(V+E) (선형) 시간에 수행된다. 이는 모든 정점과 간선을 시험해야 하는 하한선과 일치하므로 점근적으로 최적이다. 하지만, 오직 한 번의 순회만 시행하는 타잔의 강하게 연결된 요소 알고리즘이나 경로 기반 강한 연결 요소 알고리즘에 비해 실제로는 비효율적이다.

그래프가 인접 행렬로 주어질 때는 ''Ο(V2)'' 시간에 작동된다.


본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com