그래프 알고리즘

인접 행렬은 그래프를 2차원 배열로 표현하는 방법이다. 정점의 개수가 N개일 때, N x N 크기의 행렬을 사용한다. 행렬의 i행 j열 원소는 정점 i에서 정점 j로 가는 간선의 존재 여부 또는 가중치를 저장한다.

무방향 그래프의 경우 인접 행렬은 대칭 행렬이 된다. 가중치 그래프에서는 간선이 존재하는 위치에 가중치 값을, 간선이 없는 위치에는 0 또는 무한대(INF)와 같은 특정 값으로 표시한다. 이 표현 방식은 두 정점 사이의 연결 관계를 상수 시간에 확인할 수 있다는 장점이 있다.

반면, 정점의 개수에 비해 실제 간선의 개수가 매우 적은 희소 그래프의 경우 메모리 사용이 비효율적이다. 또한 특정 정점에 연결된 모든 이웃을 찾기 위해서는 해당 정점의 행 전체를 순회해야 하므로 정점 수에 비례하는 시간이 소요된다.

인접 행렬은 그래프의 연결 관계를 명시적으로 나타내며, 행렬 연산을 통해 그래프의 경로나 연결 성분 등을 분석하는 데 활용될 수 있다. 플로이드-워셜 알고리즘과 같이 모든 정점 쌍 간의 관계를 계산하는 알고리즘에서 주로 사용된다.

인접 리스트는 그래프를 표현하는 방법 중 하나로, 각 정점마다 그 정점에 인접한 정점들의 목록을 저장하는 방식이다. 각 정점을 인덱스로 하는 배열을 만들고, 각 배열의 요소는 해당 정점과 직접 연결된 다른 정점들의 리스트(연결 리스트, 동적 배열 등)를 가리킨다. 이 방식은 그래프의 변의 개수에 비례하는 메모리만 사용하므로, 변이 많지 않은 희소 그래프를 표현할 때 효율적이다.

인접 행렬과 비교했을 때, 특정 두 정점 사이에 변이 존재하는지 확인하는 연산은 인접 리스트에서 더 느릴 수 있다. 해당 정점의 리스트를 순회하며 찾아야 하기 때문이다. 반면, 한 정점에 연결된 모든 이웃 정점들을 순회하는 작업은 인접 리스트에서 매우 효율적이다. 이는 많은 그래프 알고리즘의 기본 동작이므로 실용적이다.

가중치가 있는 그래프를 표현할 때는 리스트에 인접 정점의 번호뿐만 아니라 가중치 정보도 함께 저장한다. 방향 그래프의 경우, 각 정점의 리스트는 그 정점에서 나가는 변만을 저장한다. 무방향 그래프라면 한 변이 두 정점의 리스트에 모두 기록된다.

인접 리스트는 깊이 우선 탐색, 너비 우선 탐색, 다익스트라 알고리즘 등 대부분의 그래프 순회 및 경로 탐색 알고리즘에서 널리 사용되는 표현 방식이다. 구현이 간단하고 실제 데이터에서 자주 나타나는 희소 그래프에 적합하기 때문이다.

간선 리스트는 그래프를 표현하는 방법 중 하나로, 모든 간선을 리스트나 배열에 나열하여 저장하는 방식이다. 인접 행렬이나 인접 리스트에 비해 메모리 사용이 간단하고 직관적이라는 장점이 있다. 각 간선은 보통 출발 정점, 도착 정점, 그리고 필요에 따라 가중치를 함께 저장한다. 이 방식은 간선 중심의 연산, 예를 들어 모든 간선을 순회하거나 정렬하는 알고리즘에 효율적으로 사용된다.

구현은 매우 단순하다. 예를 들어, C++에서는 구조체나 클래스의 배열을, Python에서는 리스트 안의 튜플을 사용하여 간선 정보를 저장할 수 있다. 가중치가 없는 무향 그래프라면 (u, v) 형태로, 가중치가 있는 유향 그래프라면 (u, v, w) 형태로 저장하는 것이 일반적이다. 이는 그래프의 모든 연결 관계를 하나의 집합으로 관리하는 것과 유사하다.

따라서 간선 리스트는 특정 정점의 이웃을 빠르게 찾아야 하는 그래프 순회에는 비효율적일 수 있지만, 간선 자체를 정렬하거나 일괄 처리하는 알고리즘에서는 매우 유용한 표현법이다. 그래프의 밀도가 매우 낮은 희소 그래프이든 높은 밀집 그래프이든 관계없이 간선의 총수만큼의 공간을 사용한다는 점이 특징이다.

깊이 우선 탐색(DFS, Depth-First Search)은 그래프의 모든 정점을 탐색하는 알고리즘이다. 루트 노드(또는 임의의 노드)에서 시작하여 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식을 사용한다. 스택 자료구조를 활용하거나 재귀 호출을 통해 구현할 수 있으며, 구현이 비교적 간단하고 직관적이라는 장점이 있다.

주요 동작 원리는 다음과 같다. 먼저 시작 정점을 방문 처리하고 스택에 넣는다. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 노드를 방문 처리하고 스택에 넣는다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 제거한다. 이 과정을 스택이 빌 때까지 반복한다. 재귀를 이용한 구현에서는 함수 호출 스택이 이 역할을 대신한다.

깊이 우선 탐색은 다양한 문제 해결에 응용된다. 그래프 내 사이클 존재 여부를 판별하거나, 위상 정렬을 수행하며, 백트래킹 기법의 기초가 된다. 또한, 미로 탐색이나 퍼즐 문제 해결, 그리고 강한 연결 요소를 찾는 알고리즘의 핵심 구성 요소로도 사용된다.

너비 우선 탐색(BFS)은 그래프를 체계적으로 탐색하는 알고리즘이다. 시작 정점을 기준으로 가까운 정점부터 차례대로 모든 정점을 방문하는 방식으로 동작한다. 이 알고리즘은 주로 큐 자료구조를 사용하여 방문할 정점의 순서를 관리한다.

알고리즘의 동작 과정은 다음과 같다. 먼저 시작 정점을 큐에 넣고 방문했다고 표시한다. 이후 큐가 빌 때까지, 큐의 앞에서 정점을 하나 꺼내고, 그 정점에 인접하면서 아직 방문하지 않은 모든 정점을 큐에 넣으며 방문 표시를 반복한다. 이 과정은 모든 연결된 정점을 시작점으로부터 거리 순(레벨 순)으로 방문하게 만든다.

너비 우선 탐색은 가중치가 없는 그래프에서 두 정점 사이의 최단 경로를 찾는 데 사용할 수 있다. 또한 위상 정렬이나 강한 연결 요소를 찾는 알고리즘의 기초가 되기도 한다. 인공지능 분야에서는 게임 트리 탐색이나 상태 공간 탐색에 널리 응용된다.

다익스트라 알고리즘은 가중치가 있는 그래프에서 한 정점에서 다른 모든 정점까지의 최단 경로를 찾는 알고리즘이다. 이 알고리즘은 음수가 아닌 가중치를 가진 그래프에서만 정확하게 동작한다. 기본 아이디어는 시작 정점으로부터 가장 가까운 정점을 순차적으로 확정해 나가면서, 각 정점까지의 최단 거리를 점진적으로 업데이트하는 것이다.

알고리즘은 우선순위 큐(또는 최소 힙)를 사용하여 효율적으로 구현된다. 시작 정점의 거리를 0으로, 다른 모든 정점의 거리를 무한대로 초기화한다. 우선순위 큐에는 (거리, 정점) 쌍이 저장된다. 큐가 빌 때까지, 가장 짧은 거리를 가진 정점을 큐에서 꺼내어 '확정'하고, 이 정점에 인접한 모든 정점에 대해 현재 알려진 거리보다 더 짧은 경로가 발견되면 거리 값을 갱신하고 우선순위 큐에 넣는다.

이 알고리즘은 네트워크 라우팅 프로토콜, 지도 및 내비게이션 소프트웨어에서 경로 찾기, 물류 및 운송 계획 수립 등 다양한 분야에 폭넓게 응용된다. 다익스트라 알고리즘은 그리디 알고리즘의 한 예로, 각 단계에서 가장 좋아 보이는 선택(가장 가까운 정점)을 함으로써 전체 최적해를 보장한다.

벨만-포드 알고리즘은 가중치가 있는 방향 그래프에서 한 출발 정점으로부터 다른 모든 정점까지의 최단 경로를 찾는 알고리즘이다. 다익스트라 알고리즘과 달리, 그래프의 변 가중치가 음수인 경우에도 사용할 수 있다는 점이 가장 큰 특징이다. 이 알고리즘은 최단 경로 추정치를 반복적으로 완화하는 방식으로 동작하며, 음수 가중치를 가진 사이클이 존재하는 경우 이를 감지해낼 수 있다.

알고리즘의 기본 동작은 다음과 같다. 먼저, 출발 정점까지의 거리를 0으로, 다른 모든 정점까지의 거리를 무한대로 초기화한다. 이후, 모든 변에 대해 거리 완화 연산을 수행하는 과정을 (정점의 수 - 1)번 반복한다. 거리 완화는 현재 정점 u를 거쳐 정점 v로 가는 경로가 기존에 알려진 v까지의 거리보다 짧다면, 그 거리 값을 더 짧은 값으로 갱신하는 과정이다. 이렇게 (V-1)번의 완화 과정을 거치면, 출발점으로부터 모든 정점까지의 최단 경로가 보장된다.

음수 사이클의 존재 여부를 확인하기 위해서는 (V-1)번의 완화 과정을 마친 후, 한 번 더 모든 변에 대해 완화를 시도한다. 이 추가 단계에서 거리 값이 또다시 갱신되는 정점이 발생한다면, 해당 그래프는 음수 가중치 사이클을 포함하고 있어 최단 경로가 정의되지 않음을 의미한다. 벨만-포드 알고리즘은 네트워크 라우팅 프로토콜, 금융에서의 차익 거래 모델링, 그리고 음수 가중치를 다루는 다양한 최적화 문제에 응용된다.

플로이드-워셜 알고리즘은 모든 정점 쌍 사이의 최단 경로를 구하는 알고리즘이다. 한 번의 실행으로 그래프 내 모든 정점에서 다른 모든 정점으로 가는 최단 거리를 계산한다. 이 알고리즘은 다이나믹 프로그래밍을 기반으로 하며, 음의 가중치를 가진 간선이 존재해도 사용할 수 있다. 하지만 음의 가중치 사이클이 존재하는 경우에는 올바른 결과를 내지 못한다.

알고리즘의 핵심 아이디어는 중간 정점을 거치는 경로를 점진적으로 고려하는 것이다. 3중 반복문을 사용하여, 각 단계에서 특정 정점을 중간 경유지로 허용했을 때 모든 정점 쌍의 최단 거리를 갱신한다. 초기 거리 행렬은 직접 연결된 간선의 가중치로 설정하고, 연결되지 않은 정점 쌍의 거리는 무한대로 설정한다.

이 알고리즘은 구현이 간단하고 직관적이라는 장점이 있지만, 정점의 수가 많아지면 세제곱에 비례하는 시간 복잡도로 인해 계산 비용이 매우 커진다. 따라서 정점의 수가 수백 개를 넘지 않는 중소규모의 그래프에 주로 적용된다. 주요 응용 분야로는 네트워크 라우팅 프로토콜 설계, 도시 간 최단 이동 경로 계산, 복잡한 시스템 내 상호 의존성 분석 등이 있다. 또한 알고리즘의 변형을 통해 그래프의 연결성(경로의 존재 여부)을 확인하거나, 최단 경로뿐만 아니라 그 경로 자체를 복원하는 데에도 사용할 수 있다.

크루스칼 알고리즘은 가중치가 있는 무방향 연결 그래프에서 최소 신장 트리를 찾는 대표적인 그리디 알고리즘이다. 이 알고리즘은 모든 정점을 포함하면서 사이클이 없고, 사용된 모든 간선의 가중치 합이 최소가 되는 트리를 구성한다. 기본 아이디어는 간선을 가중치가 낮은 순서로 하나씩 확인하며, 해당 간선을 추가해도 사이클이 형성되지 않으면 트리에 포함시키는 것이다.

알고리즘의 구체적인 동작 과정은 다음과 같다. 먼저 그래프의 모든 간선을 가중치 기준으로 오름차순 정렬한다. 그 후, 가장 가중치가 작은 간선부터 순회하며, 해당 간선이 현재까지 구성된 부분 트리에서 사이클을 만들지 않는지 확인한다. 사이클 생성 여부는 분리 집합 자료구조를 통해 효율적으로 판단한다. 두 정점이 같은 집합에 속하면 간선을 추가할 경우 사이클이 생기므로 무시하고, 서로 다른 집합에 속하면 간선을 트리에 추가하고 두 집합을 합친다.

크루스칼 알고리즘의 시간 복잡도는 간선 정렬에 필요한 O(E log E) 시간이 지배적이며, 여기서 E는 간선의 수이다. 분리 집합의 연산은 거의 상수 시간에 가까워 정렬 시간이 전체 성능을 결정한다. 이 알고리즘은 간선 중심 방식으로, 그래프가 희소할 때 유리하다.

이 알고리즘은 네트워크 설계, 회로 배선, 클러스터링 등 다양한 최적화 문제에 폭넓게 응용된다. 구현이 직관적이고 효율적이어서 최소 신장 트리를 구하는 기본적인 방법으로 자주 사용된다.

프림 알고리즘은 최소 신장 트리를 구하는 대표적인 탐욕 알고리즘이다. 이 알고리즘은 하나의 시작 정점에서 출발하여, 현재까지 구성된 트리에 인접한 정점들 중 가장 가중치가 작은 간선을 선택해 트리를 점진적으로 확장해 나간다. 이 과정은 모든 정점이 트리에 포함될 때까지 반복된다. 크루스칼 알고리즘이 간선을 중심으로 작업하는 반면, 프림 알고리즘은 정점을 중심으로 트리를 성장시킨다는 차이가 있다.

알고리즘의 구체적인 동작은 다음과 같다. 먼저 임의의 시작 정점을 트리에 포함시킨다. 이후 현재 트리에 포함된 정점들과 연결된 간선들 중, 아직 트리에 포함되지 않은 정점으로 향하며 가중치가 가장 작은 간선을 선택한다. 이 간선과 연결된 새로운 정점을 트리에 추가한다. 이 단계를 모든 정점이 트리에 포함될 때까지 반복하면 최소 신장 트리가 완성된다. 사이클이 생기지 않도록 주의해야 하는 크루스칼과 달리, 프림 알고리즘은 항상 트리에 새로운 정점 하나를 추가하는 방식이므로 사이클이 자연스럽게 방지된다.

효율적인 구현을 위해서는 우선순위 큐 (주로 최소 힙)가 사용된다. 우선순위 큐는 현재 트리에서 갈 수 있는 간선들 중 최소 가중치를 효율적으로 선택하는 데 핵심적이다. 이 알고리즘은 네트워크 설계, 통신망 구축, 도로 건설 등 연결 비용을 최소화해야 하는 다양한 운용 과학 및 공학 문제에 폭넓게 응용된다.

에드몬즈-카프 알고리즘은 네트워크에서 소스에서 싱크로 흘려보낼 수 있는 최대 유량을 찾는 알고리즘이다. 이는 포드-풀커슨 알고리즘의 한 구현 방식으로, 너비 우선 탐색을 사용하여 증가 경로를 찾는 것이 핵심 특징이다. 이 방법을 사용하면 알고리즘의 시간 복잡도가 보장된다.

알고리즘은 소스에서 싱크까지 유량을 보낼 수 있는 경로(증가 경로)가 존재하는 동안 반복한다. 각 단계에서는 너비 우선 탐색을 사용하여 잔여 용량이 남은 간선들로 구성된 잔여 그래프에서 최단 길이의 증가 경로를 찾는다. 찾은 경로를 따라 흘릴 수 있는 최대 유량(병목 용량)을 계산하고, 해당 경로의 모든 간선에 그 유량을 흘려보낸다. 이때, 순방향 간선의 용량은 줄이고, 반대 방향 간선의 용량은 늘리는 방식으로 잔여 그래프를 갱신한다.

이 알고리즘은 증가 경로를 찾을 때 항상 가장 적은 수의 간선을 사용하는 경로를 선택하기 때문에, 포드-풀커슨 알고리즘에 비해 효율성이 보장된다. 구현이 비교적 간단하면서도 성능이 안정적이어서, 소규모에서 중간 규모의 네트워크 유량 문제를 해결하는 데 널리 사용된다.

디닉 알고리즘은 네트워크 유량 문제를 해결하는 효율적인 알고리즘이다. 특히 에드몬즈-카프 알고리즘의 성능을 개선한 것으로, 유량 네트워크에서 소스(source)에서 싱크(sink)로 흘려보낼 수 있는 최대 유량을 계산한다. 이 알고리즘은 레벨 그래프를 구축한 후, 차단 유량을 찾는 과정을 반복하는 방식을 사용한다.

알고리즘의 동작은 크게 두 단계로 나눌 수 있다. 첫 번째 단계는 너비 우선 탐색을 사용하여 소스로부터 각 정점까지의 최단 거리(레벨)를 계산하고, 이를 바탕으로 유량이 흐를 수 있는 레벨 그래프를 생성하는 것이다. 두 번째 단계는 생성된 레벨 그래프에서 깊이 우선 탐색을 수행하여 소스에서 싱크로 가는 차단 유량을 찾고, 이를 네트워크에 흘려보내는 것이다. 이 두 단계를 더 이상 레벨 그래프를 만들 수 없을 때까지 반복한다.

디닉 알고리즘은 레벨 그래프를 한 번 구성한 후, 그 안에서 가능한 모든 차단 유량을 찾아내기 때문에 에드몬즈-카프 알고리즘보다 일반적으로 더 빠르게 동작한다. 이 알고리즘은 대용량의 네트워크 유량 문제나 경기 매칭 문제 등 다양한 최적화 문제에 응용된다.