1. 그래프 (Graph)
연결되어 있는 원소 간의 관계를 표현한 자료구조.
- 리스트, 스택, 큐 등의 자료구조는 선형구조인데 비해, 그래프는 비선형의 자료구조.
- 트리는 그래프의 일종.
- 정점(Vertex): 연결할 객체 / 간선(Edge): 객체를 연결하는 선의 집합으로 구성.
- G = (V,E) ** V: 정점의 집합, E: 간선들의 집합.
2. 그래프의 종류
1. 무방향 그래프 (Undirected Graph)
- 두 정점을 연결하는 간선에 방향이 없는 그래프.
- V(G1) = {A,B,C,D}, E(G1) = {(A,B),(B,C),(B,D),(C,D)}
- 무방향 그래프에서 정점 Vi와 Vj를 연결하는 간선을 (Vi, Vj)로 표현 -> 이 때, (Vi, Vj)와 (Vj,Vi)는 같은 간선
2. 방향 그래프 (Directed Graph)
- 간선에 방향이 있는 그래프.
- V(G1) = {A, B, C, D}, E(G1) = {<A,B>,<A,D>,<B,C>,<C,D>}
- 방향 그래프에서 정점 Vi와 Vj를 연결하는 간선을 <Vi, Vj>로 표현 -> Vi를 꼬리(tail), Vj를 머리(head)라고 함.
** 헷갈릴 수 있는데, 출발점이 꼬리(tail), 도착점이 머리(head)다.
- V(G1) = {A, B, C, D}, E(G1) = {<A,B>,<A,D>,<B,C>,<C,D>}
3. 완전 그래프 (Complete Graph)
- 한 정점에서 다른 모든 정점과 연결되어, 최대 간선 수를 갖는 그래프.
- 정점이 n개인 완전 그래프에서 무방향 그래프의 최대 간선 수: n(n-1)/2- 정점이 n개인 완전 그래프에서 방향 그래프의 최대 간선 수: n(n-1)
4. 부분 그래프 (Subgraph)
- 기존의 그래프에서 일부 정점이나 간선을 제외하여 만든 그래프.
5. 가중 그래프 (Weight Graph)
- 정점을 연결하는 간선에 가중치(Weight)를 할당한 그래프.
6. 유향 비순환 그래프 (DAG: Directed Acyclic Graph)
- 방향 그래프에서 사이클이 없는 그래프.
7. 연결 그래프 (Connected Graph)
- 떨어져 있는 정점이 없는 그래프.
8. 단절 그래프 (Disconnected Graph)
- 연결되지 않은 정점이 있는 그래프.
3.그래프 용어
-
그래프에서 두 정점 Vi와 Vj가 연결되어 간선 (Vi, Vj)가 있을 때, 두 정점 Vi와 Vj를 인접(adjacent)한다고 한다.
-
간선 (Vi,Vj)는 정점 Vi와 Vj에 부속(incident)되어 있다고 한다.
-
차수(Degree): 정점에 부속되어 있는 간선의 수.
- 진입차수(in-degree): 정점을 머리로 하는 간선의 수.- 진출차수(out-degree): 정점을 꼬리로 하는 간선의 수.
-
경로(Path): 정점 Vi에서 Vj까지 간선으로 연결된 정점을 순서대로 나열한 리스트.
- 단순 경로(Simple Path): 모두 다른 정점으로 구성된 경로. -
경로 길이(Path Length): 경로를 구성하는 간선의 수
-
사이클(Cycle): 단순 경로 중에서 경로의 시작 정점과 마지막 정점이 같은 경로.
4. 그래프의 표현방식 - 인접 행렬(Adjecency Matrix), 인접 리스트(Adjecent List)
그래프를 표현하는 '인접 행렬', '인접 리스트' 방법에 대해 알아보고, Python을 이용해 구현해보도록 하자.
1. 인접 행렬 (Adjecency Matrix)
-
2차원 배열을 활용해 그래프를 표현하는 방식.
-
자기 자신인 경우/연결되어 있지 않은 경우 0으로 표현하고, 연결되어 있다면 1로 표현.
-
장점)
구현이 직관적, 다중 간선 및 가중치 처리 간단.
두 정점 간 간선 존재 여부를O(1)에 즉시 확인 가능.
-
단점)
공간 복잡도: VxV 크기의 2차원 배열 사용 -> 메모리 사용량 ↑
시간 복잡도: 간선의 개수와 상관없이 모든 정점을 순회해야 -> 간선에 접근하거나 순회할 떄O(V^2)의 시간이 걸림.
가중치가 없는 경우
graph = [
[0, 1, 1, 0],
[1, 0, 1, 1],
[1, 1, 0, 0],
[0, 1, 0, 0]
]- 가중치 그래프의 경우, 1 대신 가중치를 직접 2차원 배열에 입력해주면 될 것이다.
가중치가 있는 경우
graph = [
[0, 1, 4, 0],
[1, 0, 2, 5],
[4, 2, 0, 0],
[0, 5, 0, 0]
]2. 인접 리스트 (Adjacent List)
-
연결 리스트를 활용해 그래프를 표현하는 방식.
-
장점)
공간 복잡도: 간선의 개수만큼만 리스트에 저장 -> 공간 효율성 ↑
시간 복잡도: 모든 간선을 순회할 때O(E)로 빠르게 처리 가능. -
단점)
두 정점 간 연결 여부를 확인하려면 해당 리스트를 모두 순회해야 -> 최악의 경우O(V)
구현이 인접 행렬보다 상대적으로 복잡.
가중치가 없는 경우
graph = [[] for _ in range(4)]
# 노드 A
graph[0].append('B')
graph[0].append('C')
# 노드 B
graph[1].append('A')
...
graph = [['B', 'C'], ['A', 'C', 'D'], ['A', 'B'], ['B']]
가중치가 있는 경우
- 가중치가 있는 경우는 가중치값을 튜플로 함께 묶어 그래프에 연결하는 식으로 구현할 수 있겠다.
# 가중치가 있는 그래프
graph = [[] for _ in range(4)]
# 노드 A (노드 0에 해당)
graph[0].append(('B', 1)) # B와 연결된 가중치는 1
graph[0].append(('C', 4)) # C와 연결된 가중치는 4
# 노드 B (노드 1에 해당)
graph[1].append(('A', 1)) # A와 연결된 가중치는 1
graph[1].append(('C', 2)) # C와 연결된 가중치는 2
graph[1].append(('D', 5)) # D와 연결된 가중치는 5
# 노드 C (노드 2에 해당)
graph[2].append(('A', 4)) # A와 연결된 가중치는 4
graph[2].append(('B', 2)) # B와 연결된 가중치는 2
# 노드 D (노드 3에 해당)
graph[3].append(('B', 5)) # B와 연결된 가중치는 5
print(graph)각 표현 방식의 사용
1. 인접 행렬의 사용이 적합한 경우
- 정점의 개수(V)가 적고 간선의 개수(E)가 많을 때 (즉, 밀집 그래프).
- 두 정점 간의 연결 여부를 빠르게 확인해야 하는 경우.
- 메모리보다 시간 효율성이 더 중요한 경우.
2. 인접 리스트의 사용이 적합한 경우
- 정점의 개수(V)가 많고 간선의 개수(E)가 적을 때 (즉, 희소 그래프).
- 메모리 효율성이 중요할 때.
- 그래프의 모든 간선을 순회하거나, 연결된 정점들에 대해 반복 작업을 수행하는 경우.
이미지 / 참고자료 출처 ::
[자료구조] 그래프(Graph)의 개념 설명
https://leejinseop.tistory.com/43
[그래프] 인접 행렬과 인접 리스트
https://sarah950716.tistory.com/12
[Python] 그래프 (인접 행렬, 인접 리스트) + DFS/BFS를 배우기 앞서 알아야 할 개념들(탐색 알고리즘, 자료구조)
https://veggie-garden.tistory.com/28
