Graph

노드와 엣지로 구성된 집합이다.

G = (V, E)
V = a set of vertices(=nodes, points)
E ⊆ {(x, y)| x, y ∈ V and x ≠ y}

트리도 그래프의 일부다.

🔰관련 알고리즘

유니온 파인드

그래프의 사이클이 생성되는지 판별하는 알고리즘이다.

위상 정렬

cycle이 없고 방향이 있는 그래프일 때 사용한다.

그래프 노드를 선형으로 정렬하는 알고리즘이다.

결과가 유일하게 나오지 않는다.

수강신청, 게임 빌드 순서와 같이 전후관계가 명확한, 순서(방향)가 정해져 있을 때 유용하다.

다익스트라, 벨만-포드, 플로이드-워셀

최단거리를 구하는 알고리즘이다.

다익스트라는 시작 노드부터 다른 모든 노드로 가는 최단 거리를 구하는 알고리즘이다. 단, 간선의 가중치가 음수면 안 된다(음수간선x).

벨만-포드는 다익스트라와 비슷하지만, 가중치가 음수여도 가능하다(음수간선o). 최단 거리 문제보다는 음수 cycle이 있는지(최단거리가 -무한대로 가는지)를 확인하는 문제가 많다.

플로이드-워셀은 시작 노드가 없다. 모든 노드에 대해서 최단 거리를 구하는 알고리즘이다. 단, 시간 복잡도가 크다.

최소 신장 트리(MST)

그래프로부터 최소의 가중치 합으로 모든 노드를 연결하는 알고리즘이다. 결과로 트리가 나온다.

트리는 사이클이 없어야 하므로 유니온 파인드를 활용한다. 

🔰그래프 표현

엣지 리스트

엣지를 중심으로 그래프를 표현한다.

가중치가 없는 그래프는 출발 노드와 도착 노드만 표현하므로 배열의 행은 2개면 된다. -> graph = [(1, 2), (2, 3), ...]

가중치가 있는 그래프는 출발 노드와 도착 노드, 가중치까지 표현해야하므로 배열의 행은 3개면 된다. graph = [(1, 2, 3), (2, 3, 5), ...] -> 대부분의 문제들

특정 노드와 관련된 엣지를 탐색하기 어렵다(시간 복잡도 증가). 따라서 벨만-포드나 크루스칼 알고리즘에 사용하며, 노드 중심 알고리즘에는 적합하지 않다.

인접 행렬

2차원 배열을 자료구조로 이용하여 그래프를 표현한다.

노드 중심으로 그래프를 표현한다.

가중치가 없는 그래프는 graph[start_node][goal_node] = 1을 저장하는 방식으로 표현한다. -> True도 될 듯

가중치가 있는 그래프는 graph[start_node][goal_node] = k(가중치)를 저장하는 방식으로 표현한다.

두 노드를 연결하는 엣지의 여부와 가중치 값을 배열에 직접 접근함으로써 O(1)로 바로 확인할 수 있다.

그러나 특정 노드와 관련된 엣지를 탐색하려면 n번의 접근이 필요한데, 노드 개수에 비해 엣지 개수가 적을 때는 공간 효율성이 떨어진다(대부분이 비어 있다.). 또한 노드 개수가 많은 경우 2차원 배열을 선언할 수 없는 경우도 있다(힙 스페이스 에러).

인접 행렬은 노드 개수에 따라 사용 여부를 적절하게 판단해야 한다.

인접 리스트

가장 많이 사용한다.

노드 개수만큼의 ArrayList(가변적)로 그래프를 표현한다.

가중치가 없는 그래프는 graph[start_node] = [n1, n2, ...] 방식(ArrayList<Integer>[N])으로 표현한다. -> graph = [[2, 3], [1], [1, 2]]

가중치가 있는 그래프는 graph[start_node] = [(n1, k1), (n2, k2), ...] 방식(ArrayList<Node>[N])으로 표현한다. -> graph = [[(2, 5), (3, 10)], ...]

그래프 구현은 복잡한 편이나, 노드와 연결된 엣지를 탐색하는 시간이 매우 적게 걸린다. 또한 노드 개수가 많아도 공간 효율이 좋아 메모리 초과 에러도 발생하지 않는다.