다음 링크의 코드를 읽었습니다. http://www.cosc.canterbury.ac.nz/tad.takaoka/alg/graphalg/sc.txt "저 링크"라는 단어에 계속 부딪 쳤고 그 의미가 전혀 없습니다. 나는 이것이 다소 멍청한 질문이지만 누군가 나에게 설명 할 수 있는지 알고 있나? 감사합니다. .Tarjan의 SCC 알고리즘에서 lowlink는 무엇을 의미합니까?
는 링크 된 문서에서 언급 한 바와 같이 :
는알고리즘은 정점이 처음 방문 할 때 방문 번호와 같은 값을 할당 은 초기에 낮은 링크 수를 유지합니다.
다른 말로하면, 저 링크 값은 처음에 노드가 초기 DFS 중에 갖는 수와 같습니다. 첫 번째 노드가 방문한 경우 값은 0입니다. 두 번째 노드 인 경우 1이됩니다. 세 번째 노드는 값 2, 네 번째 값 3 등을 갖습니다.
거기에서 낮은 링크 값 주어진 노드가 어떤 SCC에 들어가는 지 추적 할 수 있도록 업데이트됩니다. 처음에는 각 노드가 자체 SCC에 있다고 생각하지만, 두 개의 다른 노드가 동일한 SCC에 있다고 판단하면 모든 노드의 하위 링크 값을 모두 동일하게 유지합니다.
희망이 도움이됩니다.
http://en.wikipedia.org/wiki/ 타잔의 강한 연결의 구성 요소 알고리즘 –