[이코테] 09. 그래프 이론

---

📢 '이것이 코딩 테스트다 with 파이썬' 책을 공부하고 복습하기 위해 작성했습니다.

---

그래프 이론

코딩 테스트에서 자주 등장하는 기타 그래프 이론

다양한 그래프 알고리즘

앞의 "DFS/BFS"와 "최단 경로"에서 다룬 내용은 모두 그래프 알고리즘의 한 유형으로 볼 수 있다. 이외의 다양한 그래프 알고리즘에 대해 알아보자

예를 들어 크루스칼 알고리즘(Kruskal Algorithm)은 그리디 알고리즘으로 분류되며, 위상 정렬 알고리즘(Topology Sort Algorithm)은 큐 자료구조 혹은 스택 자료구조를 활용해 구현할 수 있다.

---

그래프

그래프(Graph)란 노드(node)와 노드 사이에 연결된 간선(Edge)의 정보를 가지고 있는 자료구조를 의미한다.

알고리즘 문제에서 "서로 다른 개체가 연결되어 있다"라고 하면 그래프 알고리즘을 떠올려야 한다.

더불어 그래프 자료구조 중에서 트리(Tree) 자료구조는 다양한 알고리즘에서 사용된다. 트리 자료구조는 부모에서 자식으로 내려오는 계층적인 모델에 속한다.

참고로 트리는 전통적인 수학에서는 무방향 그래프로 간주되지만, 컴퓨터 공학 분야에서는 방향 그래프로 간주된다.

	그래프	트리
방향성	방향 그래프혹은 무방향 그래프	방향 그래프
순환성	순환 및 비순환	비순환
루트 노드 존재 여부	루트 노드가 없음	루트 노드가 존재
노드간 관계성	부모와 자식 관계 없음	부모와 자식 관계
모델의 종류	네트워크 모델	계층 모델

그래프의 구현 방법은 2가지 방식이 존재한다.

1. 인접 행렬(Adjacency Matrix): 2차원 배열을 사용하는 방식
2. 인접 리스트(Adjacency List): 리스트를 사용하는 방식

두 방법은 메모리와 속도 측면에서 구별된다.

 

---

서로소 집합

2024.01.15 - [Algorithm] - [이코테] 09. 그래프 이론 - 서로소 집합

신장 트리

2024.01.15 - [Algorithm] - [이코테] 09. 그래프 이론 - 신장 트리

위상 정렬

2024.01.15 - [Algorithm] - [이코테] 09. 그래프 이론 - 위상 정렬

---