Algorithm/H. Trees & Graphs (33) 썸네일형 리스트형 121. Independent Set & Clique 그래프에 포함된 정점 $0$개 이상을 포함한 집합이 다음 조건을 만족할 경우 그 집합을 그래프의 독립 집합(Independent Set)이라고 한다. 그래프에 존재하는 임의의 간선이 정점 $u$와 정점 $v$를 연결할 때, $u$와 $v$ 중 최소한 한 정점은 집합에 속하지 않는다. 간단히 말하면 독립 집합에 속한 정점들 사이를 직접 연결하는 간선이 없다는 것이다. 이것은 트리에도 똑같이 적용할 수 있고, 트리에 존재하는 독립 집합을 트리의 독립 집합이라고 한다. 또한 독립 집합들 중 가장 많은 정점을 포함하는 집합을 최대 독립 집합(Maximal Independent Set)이라고 한다. 하나의 그래프/트리에 두 개 이상의 최대 독립 집합이 존재할 수도 있다. 독립 집합을 정의할 때의 특이사항은 그래프.. 120. Dial's Algorithm 다이얼 알고리즘(Dial's Algorithm)은 간선들의 가중치가 크지 않은 그래프에서 최단 경로를 구할 때 사용할 수 있는 알고리즘으로, $0$-$1$ BFS의 발전된 버전이라고 생각할 수도 있다. 각각의 간선의 가중치가 $0$ 이상 $c$ 이하의 정수일 때 다이얼 알고리즘은 $(c+1)$개의 큐를 사용하여 최단 경로를 구한다. 큐 대신 스택, 벡터 등을 사용할 수도 있다. $c = 1$일 경우 $0$-$1$ BFS와 매우 유사한 형태가 되며, $2$개의 큐를 하나의 덱으로 바꾸면 $0$-$1$ BFS와 같아진다. 다이얼 알고리즘의 작동 방식은 다음과 같다. 1. 시작 정점은 $k$, 정점 $k$로부터 정점 $i$까지의 최단 경로를 $d_i$라고 한다. 2. 정점 $x$에서 정점 $y$로 가는 가중치.. 119. 0-1 BFS $0$-$1$ BFS는 모든 간선의 가중치가 $0$ 또는 $1$인 그래프에서 사용할 수 있는 최단 경로 알고리즘으로, 한 정점에서 다른 정점들까지의 최단 경로를 구한다. 작동 방식은 다음과 같다. 1. 시작 정점은 $k$, 정점 $k$로부터 정점 $i$까지의 최단 거리를 $d_i$라고 한다. 2. 정점 $x$에서 정점 $y$로 가는 가중치 $z$인 간선이 존재할 때 $w(x, y) = z$라고 한다. 3. $d_k$는 $0$, 나머지 $d_i$는 모두 $\infty$로 초기화한다. 4. 빈 덱에 정점 $k$를 추가한다. 5. 덱의 맨 앞에서 정점 하나를 뺀다. 이 정점을 $u$라고 하자. 6. $u$가 아직 선택되지 않았으면, $u$를 선택하고 $u$와 인접한 정점을 확인한다. $u$와 인접한 각각의 정.. 118. Shortest Path Faster Algorithm Shortest Path Faster Algorithm(SPFA)은 벨만-포드 알고리즘을 약간 변형한 것으로 간선을 확인할 때 $d_v$의 값이 변하지 않았을 경우 그 정점과 인접한 정점을 다음 차례에 바로 확인할 필요가 없다는 성질을 이용한다. 작동 방식은 다음과 같다. 1. 시작 정점은 $k$, 정점 $k$로부터 정점 $i$까지의 최단 거리를 $d_i$라고 한다. 2. 정점 $x$에서 정점 $y$로 가는 가중치 $z$인 간선이 존재할 때 $w(x, y) = z$라고 한다. 3. $d_k$는 $0$, 나머지 $d_i$는 모두 $\infty$로 초기화한다. 4. 빈 큐에 정점 $k$를 추가한다. 5. 큐에서 정점 하나를 뺀다. 이 정점을 $u$라고 하자. 6. $u$에서 나가는 간선이 존재하는 각각의 정.. 117. Floyd-Warshall 플로이드-와샬 알고리즘(Floyd-Warshall Algorithm)은 모든 정점에서 모든 정점으로의 최단 거리를 구하는 알고리즘으로, 그래프의 정점의 수가 $n$일 때 시간복잡도는 $\Theta(n^3)$이다. 플로이드-와샬 알고리즘은 정점들 사이의 최단 거리를 구할 때 중간에 거칠 수 있는 정점의 수를 늘려 나가면서 최단 거리를 갱신하는 방식으로 작동한다. 벨만-포드 알고리즘이 간선을 확인하는 것과는 약간 다르다. 구체적인 작동 방식은 다음과 같다. 1. 정점 $i$로부터 정점 $j$까지의 최단 거리를 $d_{i, j}$라고 한다. 2. 각각의 $d_{i, j}$에 대해 $i = j$인 경우 $d_{i, j} = 0$, $i \ne j$인 경우 $d_{i, j} = \infty$로 초기화한다. 3. .. 116. Bellman-Ford 벨만-포드 알고리즘(Bellman-Ford Algorithm)은 한 정점에서 모든 정점까지의 최단 경로를 구하는 알고리즘이다. 이 알고리즘은 그래프의 정점의 수가 $n$, 간선의 수가 $m$일 때 시간복잡도가 $\Theta(nm)$으로 다익스트라 알고리즘에 비해 느리지만, 가중치가 음수인 간선이 존재할 경우에도 최단 경로를 찾을 수 있다. 가중치가 음수인 간선이 존재하는 그래프를 다루기 때문에, 무향 그래프는 사실상 등장하지 않으며 무향 그래프에서의 최단 경로를 다루게 된다. 벨만-포드 알고리즘은 다음과 같은 방식으로 작동한다. 1. 시작 정점은 $k$, 정점 $k$로부터 정점 $i$까지의 최단 거리를 $d_i$라고 한다. 2. 정점 $x$에서 정점 $y$로 가는 가중치 $z$인 간선이 존재할 때 $w(.. 115. Dijkstra 다익스트라 알고리즘(Dijkstra's Algorithm)은 그래프에서 정점과 정점 사이의 최단 경로를 찾을 때 가장 많이 사용되는 알고리즘으로, 유향 그래프와 무향 그래프에서 모두 사용할 수 있으나 가중치가 음수인 간선이 없는 그래프에서만 정상적인 작동을 보장할 수 있다. 다익스트라 알고리즘은 기본적으로 시작 정점이 하나로 고정되어 있으며 작동 원리는 다음과 같다. 1. 시작 정점은 $k$, 정점 $k$로부터 정점 $i$까지의 최단 거리를 $d_i$라고 한다. 2. 정점 $x$에서 정점 $y$로 가는 가중치 $z$인 간선이 존재할 때 $w(x, y) = z$라고 한다. 3. $d_k$는 $0$, 나머지 $d_i$는 모두 $\infty$로 초기화한다. 4. 아직 선택하지 않은 정점들 중 $d_i$값이 가.. 114. Shortest Path 최단 경로(Shortest Path)는 그래프에서 정점과 정점 사이의 경로 중 길이가 가장 짧은 것을 의미하며 그래프 이론에서 기본적인 내용으로 많이 다루어지는 주제이다. 일반적으로 최단 경로를 찾는 대상은 그래프의 정점으로, 트리에서의 최단 경로는 복잡한 요소가 없기 때문에 최단 경로라는 주제로 따로 분리하지 않는다. 아래의 내용이 끝이다. 가중치가 음수인 간선이 하나라도 있다면 그 간선을 무한히 왕복하는 것이 가능하므로 모든 최단 경로의 길이가 $-\infty$가 되며, 가중치가 음수인 간선이 없다면 두 정점 사이의 단순 경로가 두 정점 사이의 최단 경로와 같다. 그래프는 두 정점 사이에 여러 경로가 존재할 수 있으므로 최단 경로를 구하는 것이 더 흥미로운 주제가 된다. 그래프에서 최단 경로를 구하는.. 이전 1 2 3 4 5 다음
