[Algorithm] 위상 정렬(Topological Sort)

📂 위상 정렬이란? DAG(Directed Acycle Graph : 비순환 방향 그래프)에서 정점들을 선형으로 정렬하는 것을 말한다. DAG는 말 그대로, 사이클이 존재하지 않으면서 방향성을 가진 그래프이다. 이해하기 쉽게 그래프를 통해 알아보자. 다음과 같은 DAG가 있다고 가정해보자. 정점들의 위상에 맞게 정렬하는 것이므로, 간선의 방향성에 맞게(방향성을 조건으로 삼아서) 정점들의 번호를 선형으로 저장하는 것이다. 위 그래프를 예로 본다면, 다음과 같이 정렬될 수 있다. 1 3 5 4 2 6 이 정렬 조건에서 무엇이 만족되어야 하냐면, 모든 간선마다 1에서 4로 향하는 간선이 있다면 정렬 조건에서 1번이 4번보다 먼저 나타나야 한다. 3번에서 6번으로 바로가는 간선은 없지만, 2번으로 가는 간선이 ..

• format_list_bulleted 알고리즘/알고리즘
• · 2023. 4. 14.
• textsms

[Algorithm] BFS : 너비 우선 탐색(Java)

DFS와 함께 가장 널리 사용되는 그래프 탐색 알고리즘인 너비 우선 탐색(Breadth First Search, BFS)에 대해 알아보자. 다익스트라(Dijkstra) 알고리즘이나 최소 스패닝 트리를 찾는 프림(Prim) 알고리즘 등이 BFS를 기반으로 하고 있다. 동작 과정 BFS는 시작점에서 가까운 정점부터 순서대로 방문하는 탐색 알고리즘이기 때문에 DFS에 비해 매우 직관적이다. 위의 그래프를 보자. a를 탐색의 시작점이라 하면, a에서부터 최소 몇 개의 간선을 지나야 도달할 수 있는가를 기준으로 그래프의 정점들을 나눌 수 있다. 간선 $i$개 지나야 도착할 수 있는 정점의 집합을 $H_i$라고 부르자. 그러면 BFS는 $H_0$에 속한 a를 가장 먼저 방문하고, 그 후 $H_1, H_2$ 그리고 ..

• format_list_bulleted 알고리즘/알고리즘
• · 2022. 8. 2.
• textsms