그래프

정점과 간선의 집합을 그래프라고 한다.

트리는 사이클이 허용되지 않는 그래프이다.

 

정점(vertex)와 간선(edge)의 연결관계에 있어서 방향성이 없는 그래프를 Undirected Graph, 방향성이 있는 그래프를 Directed Graph라고 한다. 또한 간선에 가중치가 있는 그래프를 가중치 그래프라고 부른다.

 

그래프를 구현하는 방법은 두가지가 있다. 하나는 인접행렬을 통해서 구현하는 방법, 하나는 인접리스트를 통해 구현하는 방법이 있다.

 

인접 행렬로 그래프를 구현할 경우에는 정점 i와 j가 연결되어있는지 확인하려면 단순히 graph[i][j]를 확인해주면 된다. 즉 O(1)의 시간동안 연결관계를 파악할 수 있다. 하지만 간선(edge)의 갯수와 관계없이 V^2의 공간 복잡도를 갖는다는 단점이 있다. 

 

인접 리스트로 그래프를 구현하는 경우에는 정점간의 연결을 확인하기 위해서는 O(E+V)의 시간 복잡도가 필요해서, 간선이 적은 경우에 사용하는게 좋다.

 

신장 트리는 정점이 주어졌을때 모든 정점이 연결돼있지만 cycle이 형성되지 않는 경우를 뜻하고, 최소 비용 신장 트리는 가중치의 합이 최소인 신장트리를 뜻한다.

 

최소 비용 신장 트리를 구하는 방법에는 대표적으로 프림알고리즘과 크루스칼 알고리즘이 있다.

 

프림 알고리즘은 한개의 vertex에서 시작해서 가장 작은 비용의 간선을 택해서 그 간선과 연결된 정점을 추가해주는 방식을 반복하는 방법이다.

 

크루스칼 알고리즘은 정점에 상관없이 비용을 기준으로 간선을 오름차순으로 정렬해서 추가해도 사이클을 가지지 않는 작은 비용의 간선의 정점들을 추가해주는 방식을 반복하는 방법이다.