그래프(Graph)
정점(노드)과 정점을 연결하는 간선(edge)의 집합으로 구성된 자료구조
지난 포스팅에서 다루었던 트리도 그래프의 일종입니다.
-
정점(Vertex): 그래프의 구성 요소 중 하나로, 노드(Node)라고도 불리고, 데이터를 저장할 수 있다.
-
간선(Edge): 그래프의 두 정점을 연결하는 선으로, 노드들 간의 관계를 나타냅니다. 간선에는 방향성이 있는 방향 그래프와 방향성이 없는 무방향 그래프가 있습니다.
그래프의 종류
- 무방향 그래프(Undirected Graph)
- 방향 그래프(Directed Graph)
- 가중치 그래프(Weighted Graph)
...
무방향 그래프(Undirected Graph)
간선에 방향이 없는 그래프이다.
방향 그래프(Directed Graph)
간선에 방향이 있는 그래프이다. 따라서 간선은 한 정점에서 다른 정점으로만 방향성을 가진다.
가중치 그래프(Weighted Graph)
간선에 가중치(또는 비용)가 있는 그래프입니다. 각 간선은 양의 가중치 또는 음의 가중치를 가질 수 있다.
그래프 표현 방법
- 인접 행렬(Adjacency Matrix)
- 인접 리스트(Adjacency List)
인접 행렬(Adjacency Matrix)
2차원 배열을 사용하여 그래프의 연결 관계를 나타낸다.
만약 노드에서 노드로 이동이 가능하다면 1로, 아니라면 0으로 표기한다.
우선 무방향 그래프는 대각선을 기준으로 대칭인 특성을 가진다.
A
/ \
B - C
A B C
A [0, 1, 1]
B [1, 0, 1]
C [1, 1, 0]방향 그래프는 대칭성이 없다.
A → B
↗︎ ↙︎ ↓
C → D
A B C D
A [0, 1, 1, 0]
B [0, 0, 0, 1]
C [0, 0, 0, 1]
D [0, 0, 0, 0]인접 리스트(Adjacency List)
각 정점마다 해당 정점과 인접한 정점들을 연결 리스트 형태로 저장한다.
A
/ \
B - C
A: [B, C]
B: [A, C]
C: [A, B]
A → B
↙︎ ↓
C → D
A: [B]
B: [C, D]
C: [D]
D: []인접행렬과 인접리스트의 장단점
인접 행렬 장점
- 두 정점 사이의 연결 여부를 상수 시간(O(1)) 내에 확인할 수 있다.
- 간선의 수가 정점의 수에 비해 많은 경우에 효율적이다.
인접 행렬 단점
- 무조건 2차원 배열을 사용해야하므로 메모리 낭비가 발생한다.
인접 리스트 장점
- 간선의 수가 정점의 수에 비해 적은 경우에 효율적이다.
- 연결된 정점들만을 저장하기 때문에 메모리를 절약할 수 있다.
인접 리스트 장점
- 특정 두 노드가 연결되었는지 확인하기 위해 연결 리스트를 순회해야하므로 시간이 인접 행렬에 비해 오래 걸린다.
iOS Developer