그래프란?
노드와 간선으로 이루어진 자료구조
그래프의 종류
- 무방향 그래프(Undirected Graph): 방향성이 없고 노드(정점)이 연결된 그래프
- 방향 그래프(Directed Graph): 무방향 그래프에서 방향성이 추가된 그래프
- 완전 그래프(Complete Graph): 각 정점에서 다른 모든 정점을 연결하여 최대 간선 수를 가진 그래프
-> 정점이 n개인 무방향 그래프에서는 최대 간선 수 = n(n-1)/2
-> 정점이 n개인 방향 그래프에서 최대 간선 수 = n(n-1)
- 가중(치) 그래프(Weight Graph): 간선에 가중치를 담아서 표현(방향 여부 상관X)
- 부분 그래프(Sub Graph): 일부 정점과 간선으로 구성된 그래프(가중치 그래프에서 조금 떼어낸 그래프)
그래프의 집합 표현
- 정점의 집합을 V(G), 간선의 집합을 E(G)로 표현한다.
- 방향성이 없는 경우 괄호로 묶고, 방향성이 있는 경우 부등호로 묶고, 간선의 시작 부분을 먼저 표현한다.
-> V(그래프이름) = {1, 2, 3, 4}
-> E(그래프이름) = {(1, 2), (1, 3), (2, 3), (3, 4)}
그래프의 구현 방법
- 인접 행렬 기반
-> 그래프의 연결 관계를 2차원 배열로 나타내는 방식
-> 노드 i와 노드 j의 연결 여부에 따라 arr[i][j]의 값이 정해짐. (가중 그래프: 연결 - 가중값, 연결X - INF(무한의 비용), 자신 - 0 일반 그래프: 연결 - 1, 연결X - INF, 자신 - 0)
-> 장점: 구현이 쉽다. 둘의 연결 여부를 확인 할 때 시간 복잡도 O(1). arr[i][j]값 확인만 하면 되기 때문.
-> 단점: 노드 i에 연결된 노드가 어떤 노드가 있는지를 확인하려면 arr[i][0]~arr[i][N]을 전부 방문해봐야 함. O(N)의 시간이 소요됨.
INF = 999999999 # 무한의 비용
graph = [
[0, 2, 3, INF, INF],
[2, 0, 15, 2, INF],
[3, 15, 0, INF, 13],
[INF, 2, INF, 0, 9],
[INF, INF, 13, 9, 0],
]
print(graph)
- 인접 리스트 기반
-> 그래프의 연결 관계를 연결 리스트로 나타내는 방식
-> 장점: 연결된 정보만 저장하므로 메모리를 효율적으로 사용한다. 노드 i에 어떤 노드가 연결되어 있는지 확인이 빠르다.
-> 단점: 특정 두 노드가 연결되어 있는지 확인이 느리다.
graph_list = [[] for _ in range(6)]
# 노드 0에 연결된 노드 정보 저장(노드, 거리)
graph_list[0].append((1, 3))
graph_list[0].append((2, 5))
# 노드 1에 연결된 노드 정보 저장(노드, 거리)
graph_list[1].append((3, 2))
# 노드 2에 연결된 노드 정보 저장(노드, 거리)
graph_list[2].append((3, 1))
# 노드 3에 연결된 노드 정보 저장(노드, 거리)
graph_list[3].append((4, 4))
graph_list[3].append((5, 8))
# 노드 4에 연결된 노드 정보 저장(노드, 거리)
graph_list[4].append((5, 6))
# 노드 5에서 뻗어나가는건 없음.
print(graph_list)
'Computer Science > 자료구조' 카테고리의 다른 글
해시 테이블(Hash Table) (0) | 2022.06.17 |
---|---|
우선순위 큐(Priority Queue) & 힙(Heap) (0) | 2022.06.17 |
트리(Tree) (0) | 2022.06.17 |
연결리스트(Linked List) (0) | 2022.06.17 |
큐(Queue) (0) | 2022.06.17 |