Feel Coding

그래프를 표현하는 방법은 크게 두 가지가 있다. 인접행렬과 인접리스트이다.

인접행렬은 많은 양의 메모리를 쓰는 대신에 정점 v1과 v2 사이에 간선이 있는지 없는지를 매우 빠르게 알아낼 수 있고 직관적이다.

인접 리스트는 적은 양의 메모리를 쓰고 정점 v1에 연결된 모든 정점들을 빨리 알아낼 수 있는 대신에 v1과 v2 사이에 이음선이 있는지 없는지는 빨리 알아내기 어렵다.

fully-connected 그래프가 아닌 이상 인접리스트로 구현하는 것이 좋다. 그런데 포인터로 구현하면 구조체를 구현해야 하고 사용법도 까다롭기 때문에 이미 구현된 라이브러리를 사용하는 방법을 소개하려고 한다.

벡터를 이용하면 쉽게 인접리스트를 구현할 수 있다.

만약 이런 그래프를 인접리스트로 표현하고 싶다면

vector<int> w[6]; //인덱스 0은 사용 안 함
w[1].push_back(2); //1에서 2로 향하는 이음선
w[1].push_back(4); //1에서 4로 향하는 이음선
w[2].push_back(3); //2에서 3로 향하는 이음선
w[3].push_back(4); //3에서 4로 향하는 이음선
w[4].push_back(2); //4에서 2로 향하는 이음선
w[4].push_back(5); //4에서 5로 향하는 이음선

이렇게 하면 된다.

만약 정점 1과 이음선으로 연결된 모든 정점을 출력하고 싶다면

for (int v : w[1]) {
	cout << v << endl;
}

이렇게 for-each문으로 w[1]에 저장되어 있는 모든 정점들을 순회하며 출력하면 된다.

(for-each문은 자바에만 있는 줄 알았었는데 C++에도 C++11부터 생겼다고 한다.)

1에 연결된 정점 2, 4를 출력하는 것을 볼 수 있다.

이렇게 벡터를 이용하면 포인터 없이, 직관적인 인접리스트를 구현할 수 있다.

이렇게 저장되어 있다고 이해하면 되는데

사실은 이렇게 저장되어 있다.

아무튼 다들 느꼈다시피 벡터로 구현해도 포인터를 이용한 인접리스트보다 편리하고 그만큼 직관적이다.

아래는 전체코드이다.

#include <iostream>
#include <vector>
using namespace std;

int main() {
	vector<int> w[6]; //인덱스 0은 사용 안 함
	w[1].push_back(2); //1에서 2로 향하는 이음선
	w[1].push_back(4); //1에서 4로 향하는 이음선
	w[2].push_back(3); //2에서 3로 향하는 이음선
	w[3].push_back(4); //3에서 4로 향하는 이음선
	w[4].push_back(5); //4에서 5로 향하는 이음선
	for (int v : w[1]) {
		cout << v << endl;
	}
	return 0;
}

출력결과는 아까 봤다시피 1에 인접한 정점 2, 4를 출력한다.

이를 이용한 DFS, BFS 등은 알고리즘 카테고리에 포스팅하겠습니다.