그래프(Graph)는 가장 널리 사용되는 자료구조 중 하나 이다. 그래프는 데이터 간의 관계를 나타내는데 사용되며, 복잡한 데이터를 직관적으로 이해할 수 있게 해준다.
그래프는 보통 Node(노드)와 Edge(엣지)로 이루어져 있다.
Node(노드)는 데이터의 지점을 나타내며, Edge(엣지)는 노드 간의 관계를 나타낸다.
그래프는 방향성이 있을 수도 있고, 없을 수도 있다. 그래서 방향성이 있는 그래프를 directed graph라 불리며, 방향성이 없는 그래프를 undirected graph 로 불린다. 방향성 그래프에서 자기 자신을 가리키는 그래프도 있다. 그것을 self edge라 불린다.
방향성 그래프에서도 여러가지 종류의 그래프로 나뉜다.
그래프 내부에 Cycle이 회전하는 것이 하나라도 있으면 cyclic graph 라 불리며, 없다면 acyclic graph 라 불린다.
대개 그래프를 표현하는 방법은 3가지가 있다.
2차원 배열에다가 표현하는 방법
위 그림과 같이 표현할 수 있다. 하나의 예를 들어보자.
현재 0
에서 1
로 이동하는 노드는 가능하기 때문에 matrix[0][1] = 1
이다.
하지만 1
에서 0
으로 이동하는 노드는 불가능하기 때문에 matrix[1][0] = 0
이다.
이렇듯 2차원 배열로 이동이 가능한지 불가능 한지 표기하는 방법이다.
배열에 노드들을 나열하고 Linked List로 표현하는 방법
Adjacency List는 그래프를 표현하는 가장 흔한 방법 중 하나이다. 각 노드의
위 그림를 참고하여, 설명해보겠다.
노드 A
에서 갈 수 있는 노드는 B
와 C
이다. 이것을 A
라는 키값에 리스트를 저장하고 있으며, 리스트 내부에 B
와 C
를 저장 해놓는 것이다.
배열에 갈 수 있는 노드끼리 tuple로 묶어 저장하는 방법
Edge sets은 매우 간단한 그래프 표현 방법이다.
표현 방식 | 정점에 인접한 모든 간선 가져오기 | 전체 그래프 순회 | hasEdge(u, v) | 공간 |
---|---|---|---|---|
인접 행렬 | O(V) | O(V2) | O(1) | O(V2) |
간선 집합 | O(E) | O(E) | O(E) | O(E) |
인접 리스트 | O(1) | O(V + E) | O(정점이 가지는 최대 간선 수) | O(E + V) |