알고리즘 이론 - 그래프 이론 기본

☑️ To-do

• 그래프 이론 기본 정리
• Week03 문제 풀이
  • 1991 / 11725 / 1707 / 2178 / 1260 / 11724 / 2606 / 5639

 

 

그래프 🆚 트리

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

 

 

 

트리(tree) 관련 용어

• 노드(node) (=정점)
• 엣지(edge) (=간선)
• 루트(root) : 최상위 노드
• 리프(leaf)
  • 단말 노드 (terminal node)
  • 외부 노드 (external node)
  • 리프를 제외한 노드 : 비단말 노드(non-terminal node = internal node)
• 노드 간 관계 표현
  • 자식 (child)
  • 부모 (parent)
  • 형제 (sibling)
  • 조상 : 위로 가지를 따라가며 만나는 모든 노드
  • 자손 : 아래로 가지를 따라가며 만나는 모든 노드
  • 레벨 : 루트에서 얼마나 멀리 떨어져 있는지를 나타냄
• 차수 : 각 노드가 갖는 자식의 수
• 높이 : 루트에서 가장 멀리 있는 리프까지의 거리
• 서브트리 : 어떤 노드를 루트로 하고 그 자손으로 구성된 트리
• 빈 트리 : 노드와 가지가 전혀 없는 트리

 

 

 

---

그래프 표현 방법

 

1. 에지 리스트

• 벨만 포드, 크루스칼
• 에지를 중심으로 그래프 표현
  • 출발 노드 | 도착 노드
  • 출발 노드 | 도착 노드 | 가중치
• 방향이 있는 그래프, 없는 그래프 둘 다 표현 가능
  • (방향) 1 → 2 : [1, 2]
  • (무방향) 1 ↔ 2 : [1, 2] , [2, 1] 동일
  • (가중치 - 시작, 도착, 가중치) [1, 2, 4]

 

 

---

2. 인접 행렬

• $n^2$ 형태의 배열로 표현
• 노드 개수에 비해 에지가 적을 때는 공간 효율성이 떨어짐
• ⭐ 자바의 경우 노드 개수가 3만개를 넘으면 힙 스페이스 에러 발생!

 

• 가중치 ❌

• 단순히 표시 중심

 

• 가중치 ⭕

• 배열에 가중치 값을 함께 저장

 

 

---

3. 인접 리스트

• 노드 개수만큼 배열을 선언
  • 자바에선 노드 개수만큼 ArrayList를 선언한다.
• N번 노드와 연결되어 있는 노드를 배열의 위치 N에 연결된 노드 개수만큼 배열을 연결한다.
• 에지 탐색 시간 및 공간 효율성이 좋다.
• BFS, DFS

 

• 가중치 ❌

• 단순히 연결된 노드만 넣어준다.

 

• 가중치 ⭕

• 노드 연결 상태와 가중치를 넣어준다.
• Python : tuple
• Java : Node 선언