[알고리즘 특강] 6. Graph
1. 그래프의 정의와 필요성
1.1 그래프란?
- 정의: 노드(정점)와 노드들을 연결하는 간선으로 구성된 자료구조
- 특징:
- 노드 간의 관계를 표현하는데 사용
- 방향성에 따라 방향 그래프와 무방향 그래프로 구분
- 가중치가 있는 경우 가중치 그래프로 구분
2. 그래프 구현
2.1 구현 방식
그래프를 구현하는 방법은 크게 두 가지가 있습니다:
- 인접 행렬: 2차원 배열을 사용하여 구현
- 인접 리스트: 연결 리스트나 벡터를 사용하여 구현
2.2 인접 리스트 구현 - vector
- 구현 방식: 각 정점마다 인접한 정점들을 vector에 저장
- 장점:
- 구현이 매우 쉽음
- 간선으로 이어진 정점 정보가 하나의 배열에 담김
- 배열에서 할 수 있는 모든 작업(정렬, 삭제 등)을 자유롭게 수행 가능
- 단점:
- vector에 정점을 push하는데 오버헤드 발생
- 여러 개의 테스트케이스를 처리할 경우, 메모리에 빈 공간이 많이 생김
- 메모리상에 각각의 배열이 파편화되어 저장되므로 캐시 효율이 떨어짐
#include <vector>
using namespace std;
constexpr int n = 5;
const vector<pair<int, int>> edges = { {0,1}, {0,2}, {0,3}, {1,2}, {1,4}, {3,2}, {4,3} }
vector<vector<int>> graph(n);
for (const auto& e : edges) {
graph[e.first].emplace_back(e.second)
}
2.3 인접 리스트 구현 - 링크드 리스트
- 구현 방식: 정점마다 인접한 정점의 개수는 미리 알지 못하지만, 총 간선의 개수는 알고 있으므로 사용할 메모리만 정확하게 미리 할당
- 장점:
- 메모리를 효율적으로 사용 가능
- 특히 여러 개의 테스트케이스를 처리할 때 차이가 큼
- 단점:
- 가독성이 떨어짐
- 정점 정보를 링크드 리스트에 저장하므로 정렬하거나 삭제하는 데 어려움
- 연결 리스트 순회는 기본적으로 배열보다 느림
#include <vector>
using namespace std;
struct LinkedListNode {
int id;
int next;
};
vector<LinkedListNode> nodes(edges.size());
vector<int> head(n, -1);
for (int i = 0; i<static_cast<int>(edges.size()); i++) {
nodes[i].id = edges[i].second;
nodes[i].next = head[edges[i].first];
head[edges[i].first] = i;
}
2.4 인접 리스트 구현 - 1차원 배열
- 구현 방식: 2차원으로 놓인 여러 개의 정점 리스트를 일렬로 잇는 방법
- 장점:
- 캐시 효율이 가장 뛰어남
- 단점:
- 가독성이 떨어짐
- 크기가 다른 세 개의 독립된 배열을 사용하므로 실수할 여지가 많음
- 실시간으로 간선을 추가/삭제할 수 없음
#include <vector>
#include <numeric>
using namespace std;
vector<int> outdegree(n);
vector<int> prefix(n+1);
vector<int> vertices(edges.size());
for (const auto& e: edges) {
++outdegree[e.first];
}
partial_sum(outdegree.begin(), outdegree.end(), next(prefix.begin()))
for (const auto& e : edges) {
vertices[prefix[e.first] + --outdegree[e.first]] = e.second;
}
3. 다익스트라 (Dijkstra)
3.1 다익스트라란?
- 정의: 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려주는 경로 탐색 알고리즘
- 조건:
- 그래프의 모든 간선이 0 이상의 cost를 가져야 함
- 그래프에서 연결되지 않는 간선의 가중치는 Inf로 표현
3.2 다익스트라의 동작 원리
- 출발노드를 설정
- ‘최단거리 테이블’(dist)과 ‘노드 방문여부 체크 배열’(visited)을 초기화
- 현재까지 방문한 노드와 인접한 노드 중 방문하지 않은 노드를 구별
- 방문하지 않은 노드 중 거리가 가장 짧은 노드를 선택하고 방문 처리
- 해당 노드를 거쳐 다른 노드로 넘어가는 간선 비용(가중치)을 계산해 ‘최단 거리 테이블’을 업데이트
- 목적지 노드에 방문할 때까지 3~4의 과정을 반복
3.3 다익스트라 구현 - Sequential Search
#define MAX_N 6
#define INF (987654321)
int graph[MAX_N][MAX_N] = {
{0,2,5,1,INF,INF},
{2,0,3,2,INF,INF},
{5,3,0,3,1,5},
{1,2,3,0,1,INF},
{INF,INF,1,1,0,2},
{INF,INF,5,INF,2,0},
}
// 방문 안한 노드 중에서 거리가 가장 짧은 노드 반환
int getMinIdx(int nodes[MAX_N], int visited[MAX_N]) {
int min = -1;
for (int i=0; i < MAX_N; i++){
if (visited[i])
continue;
if (min<0 || nodespmin > nodes[i])
minj = i;
}
return min;
}
void dijkstra(int arr[MAX_N][MAX_N], int start, int dist[MAX_N]){
int visited[MAX_N] = { 0, };
// 시작지점에서 다른 노드까지의 거리 초기화
for (int i=0; i<MAX_N; i++) {
dist[i] = arr[start][i];
}
visited[start] = 1;
for (int i=0; i<MAX_N-1;i++) {
int n_new = getMinIdx(dist, visited);
visited[n_new] = 1;
// 최단 거리 갱신
for (int j=0; j<MAX_N; j++) {
if(visited[j])
continue;
// 기존 j 노드까지 최단거리와 현재 방문 안한 노드중에서 거리가 가장 짧은 노드까지의 거리
// (n_new) + n_new에서 j까지 최단거리 선택
if (dist[j] > dist[n_new] + arr[n_new][j])
dist[j] = dist[n_new] + arr[n_new][j];
}
}
}
3.4 다익스트라 구현 - Priority Queue Search
void dijkstra(int arr[MAX_N][MAX_N], int start, int dist[MAX_N]) {
// 다음에 방문 가능한 노드들 저장
// 이 중에서 거리가 가장 짜릅은 노드부터 꺼냄
priority_queue<pair<int,int>> pq; // first: 거리, second: 방문할 노드
for (int i = 0; i<MAX_N; i++){
dist[i] = INF;
}
// 시작 지접 세팅
dist[start] = 0;
pq.push({0, start});
while(!pq.empty()) {
int cur_dist = -pq.top().first; // C++에서 우선순위큐는 숫자가 높은게 우선이라
int cur_node = pq.top().second;;
pq.pop();
// 이미 처리된 노드는 무시
if (cur_dist != dist[cur_node])
continue;
for (int i = 0; i<MAX_N; i++) {
int nxt_dist = cur_dist + arr[cur_node][i];
if (nxt_dist < dist[i]) {
dist[n] = nxt_dist;
pq.push({-nxt_dist, i}); // C++에서 우선순위큐는 숫자가 높은게 우선이라
}
}
}
}
댓글남기기