익명 사용자
로그인하지 않음
토론
기여
계정 만들기
로그인
IT 위키
검색
타잔 알고리즘
편집하기 (부분)
IT 위키
이름공간
문서
토론
더 보기
더 보기
문서 행위
읽기
편집
원본 편집
역사
경고:
로그인하지 않았습니다. 편집을 하면 IP 주소가 공개되게 됩니다.
로그인
하거나
계정을 생성하면
편집자가 사용자 이름으로 기록되고, 다른 장점도 있습니다.
스팸 방지 검사입니다. 이것을 입력하지
마세요
!
==동작 방식 및 예제== 타잔 알고리즘은 DFS를 수행하면서 각 노드의 방문 순서(DFS 번호)와 최소 연결 가능 DFS 번호를 기록하며, 스택을 이용해 SCC를 찾는다. 기본적인 동작 과정은 다음과 같다. *DFS를 수행하면서 각 노드에 대해 DFS 번호를 부여한다. *방문한 노드를 스택에 저장하고, 현재 경로에서 가장 작은 DFS 번호를 유지한다. *이미 방문한 노드를 다시 방문할 경우, 최소 DFS 번호를 갱신한다. *DFS 탐색이 끝날 때, 현재 노드가 SCC의 루트라면 스택에서 해당 SCC를 구성하는 노드들을 꺼낸다. '''예제''' 다음 그래프를 예로 들어 타잔 알고리즘이 어떻게 동작하는지 살펴보자. 0 → 1 ↖ 2 ↓ 3 → 4 → 6 ↖ ↓ ↓ ↖ 5 7 → 8 이제 0번 노드에서 DFS를 시작한다고 가정하자. #DFS를 수행하면서 DFS 번호를 부여한다. #*0번 노드 방문 → DFS 번호: 0, 최소 DFS 번호: 0 #*1번 노드 방문 → DFS 번호: 1, 최소 DFS 번호: 1 #*2번 노드 방문 → DFS 번호: 2, 최소 DFS 번호: 2 #*2에서 다시 0번으로 가는데, 0은 이미 방문됨 → 최소 DFS 번호를 갱신 → 2의 최소 DFS 번호 = 0 #*2에서 3번 노드로 이동 → DFS 번호: 3, 최소 DFS 번호: 3 #방문한 노드를 스택에 저장하고 최소 DFS 번호를 유지한다. #*3 → 4 방문 (DFS 번호: 4, 최소 DFS 번호: 4) #*4 → 5 방문 (DFS 번호: 5, 최소 DFS 번호: 5) #*5 → 3으로 되돌아가는데, 3은 스택에 있음 → 최소 DFS 번호 갱신 → 5의 최소 DFS 번호 = 3 #이미 방문한 노드를 다시 방문할 경우 최소 DFS 번호를 갱신한다. #*5에서 DFS 종료 → 최소 DFS 번호 == DFS 번호이므로 SCC 찾음 → {3, 4, 5} #DFS 탐색이 끝날 때 SCC를 찾고 스택에서 제거한다. #*3, 4, 5가 SCC로 묶이며 스택에서 제거됨 #*2 → 0의 영향을 받아 최소 DFS 번호가 0으로 유지됨 #*0, 1, 2가 SCC로 묶이며 스택에서 제거됨 이제 아래 코드를 실행하여 동일한 결과를 확인할 수 있다.
요약:
IT 위키에서의 모든 기여는 크리에이티브 커먼즈 저작자표시-비영리-동일조건변경허락 라이선스로 배포된다는 점을 유의해 주세요(자세한 내용에 대해서는
IT 위키:저작권
문서를 읽어주세요). 만약 여기에 동의하지 않는다면 문서를 저장하지 말아 주세요.
또한, 직접 작성했거나 퍼블릭 도메인과 같은 자유 문서에서 가져왔다는 것을 보증해야 합니다.
저작권이 있는 내용을 허가 없이 저장하지 마세요!
취소
편집 도움말
(새 창에서 열림)
둘러보기
둘러보기
대문
최근 바뀜
광고
위키 도구
위키 도구
특수 문서 목록
문서 도구
문서 도구
사용자 문서 도구
더 보기
여기를 가리키는 문서
가리키는 글의 최근 바뀜
문서 정보
문서 기록