그래프에서 각 노드의 사이클까지 거리를 빠르게 구하는 놀라운 방법

1. 문제 정확히 하나의 사이클을 포함하는 무방향 연결 그래프(connected undirected graph)가 주어진다. 각 노드 번호가 0부터 n-1까지 n개의 노드를 가진다. 노드 a와 b 사이 거리가 a에서 b로 가기 위해 필요한 최소 간선의 수 노드 i = 0,1,2,..,n-1에서 이 그래프에 존재하는 사이클에 있는 임의의 노드까지의 최소 거리를 구한다면? 당연히 사이클에 포함된 노드는 사이클 까지의 거리가 0이다.   위 그래프는 1,2,3,4가 사이클을 이룬다. 1,2,3,4는 각각 사이클까지 거리가 0이고, 0번 노드는 사이클 까지 거리가 1 5번 노드는 사이클 까지 거리가 1, 6번 노드는 사이클 까지 거리가 2이다.  2. 풀이 사이클에 포함된 노드는  위상정렬에 포함되지 않는다는 ..

• format_list_bulleted 알고리즘/위상정렬
• · 2024. 11. 13.
• textsms

위상정렬 재활치료하기 - 그래프에 사이클이 존재하여 정렬이 불가능한경우

1. 위상정렬 가볍게 복습 그래프의 노드를 정렬하는 위상정렬 정복하기 (tistory.com) 그래프의 노드를 정렬하는 위상정렬 정복하기 1. 개요 위상 정렬(topology sort)은 정렬 알고리즘의 일종 위상 정렬은 순서가 정해져 있는 일련의 작업을 차례대로 수행해야할 때 사용할 수 있는 알고리즘 이론적으로, 위상 정렬은 방향 그래프의 deepdata.tistory.com 1) 그래프를 만들면서, 각 노드의 진입차수(indegree)를 세준다. 2) 진입차수가 0인 노드를 큐에 모두 넣는다. 3) 큐가 빌때까지 다음을 반복 3-1) 큐에서 노드를 하나 빼고, 결과 리스트에 넣어준다. 3-2) 3-1)에서 뺀 노드에서 출발하는 모든 간선을 제거 3-3) 3-2) 후에 노드의 진입차수가 0이 된 노드는..

• format_list_bulleted 알고리즘/위상정렬
• · 2023. 3. 17.
• textsms

그래프의 노드를 정렬하는 위상정렬 정복하기

1. 개요 위상 정렬(topology sort)은 정렬 알고리즘의 일종 위상 정렬은 순서가 정해져 있는 일련의 작업을 차례대로 수행해야할 때 사용할 수 있는 알고리즘 이론적으로, 위상 정렬은 방향 그래프의 모든 노드를 '방향성에 거스르지 않도록 순서대로 나열하는 것'이다. 실제 예를 들어 위상 정렬을 수행하는 전형적인 예시는, '선수과목을 고려한 학습 순서 결정'이 있다. 예를 들어 컴퓨터공학과 커리큘럼에는 '자료구조'과목을 수강한 뒤에, '알고리즘'강의를 수강하는 것을 권장한다. 이 경우에 자료구조와 알고리즘을 각각 노드로 표현하고, 자료구조에서 알고리즘으로 이어질 수 있도록 방향성을 갖는 간선을 그릴 수 있다. 그래프 상에서 선후 관계가 있다면, 위상 정렬을 수행하여 모든 선후 관계를 지키는 전체 순..

• format_list_bulleted 알고리즘/위상정렬
• · 2022. 10. 27.
• textsms