그래프

그래프를 표현하는 방법은 인접 행렬과 인접 리스트가 있습니다.
오늘 Post에서는 인접 리스트를 알아볼 예정입니다.

다음과 같은 그래프가 있다고 생각해보자.

정점은 모두 5개, 간선은 7개가 된다.
인접 리스트는 정점에서 갈 수 있는 다른 모든 정점들을 2차원 배열로 저장해 주는 형태를 말한다.
위 그래프를 인접 리스트로 만들면 다음과 같다.

인접 리스트를 만드는 방법은 Vector를 사용한 방법, 링크드 리스트를 사용한 방법이 있다.

Vector를 사용하여 인접리스트를 만드는 코드는 다음과 같다.

vector<vector<int>> graph(n);
for (const auto& e : edges) {
	graph[e.first].emplace_back(e.second);
}

위의 코드는 방향이 있는 그래프에서 사용하는 방법이고,
방향이 없는 그래프는 first와 second에게 모두 서로를 저장해 주어야 한다.

vector를 사용할 때, 장점은 구현이 매우 쉽고, 정점의 정보가 하나의 배열에 담기기 때문에 배열에서 할 수 있는 정렬, 삭제 등을 자유롭게 할 수 있다는 점이 있다.
반대로 단점은 push를 해야 하기 때문에 오버헤드가 발생하게 되고, 동적 할당을 계속 하는 방법 때문에 메모리 낭비가 심하다는 단점이 있다.

다음으로 링크드 리스트를 사용하는 코드를 보자.

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;
}

각 노드들이 다음 노드를 가리키고 있도록 저장해준 방법이다.

링크드 리스트의 장점은 메모리 낭비가 심하지 않다는 점이 있고,
단점은 알아보기 힘들고, index로 접근이 불가능한 만큼 배열보다 순회가 느리다는 단점이 있다.

그래프를 사용 가능한 데이터로 가공하는 방법을 알아보았다.
이제 이 인접 리스트를 가지고 DFS와 BFS 등의 문제를 해결할 수 있다!