πŸ’» CS/자료ꡬ쑰

[Swift] κ·Έλž˜ν”„(Graph)

JerryiOS 2023. 3. 29. 16:49

이 글은 개인적인 곡뢀λ₯Ό μœ„ν•΄ μž‘μ„±ν•˜λŠ” κ²ƒμž„μ„ λ°νž™λ‹ˆλ‹€.

μžμ„Έν•œ λ‚΄μš©μ€ https://babbab2.tistory.com/105 을 λ°©λ¬Έν•΄μ£Όμ„Έμš”!

κ·Έλž˜ν”„

κ·Έλž˜ν”„ 자료ꡬ쑰

λ…Έλ“œ(정점)κ³Ό κ°„μ„ (브랜치)둜 이루어진 자료ꡬ쑰

μ—°κ²°λ˜μ–΄μžˆλŠ” μ›μ†Œκ°„μ˜ 관계λ₯Ό ν‘œν˜„ν•œ 자료ꡬ쑰

μ‹€μƒν™œμ˜ ν˜„μƒμ΄λ‚˜ 사물을 κ·Έλž˜ν”„λ‘œ ν™œμš©ν•  수 있음

μ•Œκ³  μžˆμ–΄μ•Ό ν•  κ·Έλž˜ν”„ κ΄€λ ¨ μš©μ–΄

λ…Έλ“œ(정점)

컴퓨터 과학에 μ“°μ΄λŠ” 기초적인 λ‹¨μœ„

즉, μœ„μ˜ κ·Έλ¦Όμ—μ„œλŠ” 동그라미 ν•˜λ‚˜κ°€ λ…Έλ“œλ‹€.

κ·Έλž˜ν”„μ—μ„œ λ…Έλ“œλŠ” λŒ€μ‘ν•˜λŠ” 개체λ₯Ό λ‚˜νƒ€λ‚΄λŠ” 정점이닀.

κ°„μ„ (브랜치)

객체 사이λ₯Ό μž‡λŠ” μ—°κ²°

κ²½μš°μ— 따라 λ…Έλ“œ 사이λ₯Ό μž‡λŠ” 각 μ—°κ²°μ˜ 강도λ₯Ό λ‚˜νƒ€λ‚΄λŠ” κ°€μ€‘μΉ˜λ₯Ό κ°–λŠ”λ‹€.

인접 정점

간선에 μ˜ν•΄ 직접 μ—°κ²°λœ λ…Έλ“œ

μœ„μ˜ κ·Έλž˜ν”„ κ·Έλ¦Όμ—μ„œ 1의 인접 정점은 5와 2, 6의 인접 정점은 4

참고둜 μ΄ν•΄ν•˜λ©΄ 쒋은 μš©μ–΄

λ‹¨μˆœκ²½λ‘œ

λ°˜λ³΅λ˜λŠ” λ…Έλ“œκ°€ μ—†λŠ” 경둜 (같은 간선을 μ§€λ‚˜κ°€μ§€ μ•ŠλŠ” 경둜)

μ§„μž… 차수

λ°©ν–₯ κ·Έλž˜ν”„μ—μ„œ μ™ΈλΆ€ λ…Έλ“œμ—μ„œ λ“€μ–΄μ˜€λŠ” κ°„μ„ μ˜ 수

μ§„μΆœ 차수

λ°©ν–₯ κ·Έλž˜ν”„μ—μ„œ ν•œ λ…Έλ“œμ—μ„œ μ™ΈλΆ€ λ…Έλ“œλ‘œ ν–₯ν•˜λŠ” κ°„μ„ μ˜ 수

경둜 길이

경둜λ₯Ό κ΅¬ν•˜κΈ° μœ„ν•΄ μ‚¬μš©λœ κ°„μ„ μ˜ 수

 

κ·Έλž˜ν”„μ˜ μ’…λ₯˜

λ°©ν–₯ κ·Έλž˜ν”„

λ°©ν–₯ κ·Έλž˜ν”„

간선에 λ°©ν–₯이 μžˆλŠ” κ·Έλž˜ν”„λ‘œ, κ°„μ„  κ·Έλž˜ν”„ λ°©ν–₯으둜만 갈 수 있음

 

무방ν–₯ κ·Έλž˜ν”„

무방ν–₯ κ·Έλž˜ν”„

간선에 λ°©ν–₯이 μ—†λŠ” κ·Έλž˜ν”„λ‘œ, λ…Έλ“œλŠ” μ–‘λ°©ν–₯으둜 갈 수 있음

 

κ°€μ€‘μΉ˜ κ·Έλž˜ν”„

κ°€μ€‘μΉ˜ κ·Έλž˜ν”„

λ…Έλ“œλ₯Ό 이동할 λ•Œ λ“œλŠ” λΉ„μš©, λ˜λŠ” κ°€μ€‘μΉ˜κ°€ ν• λ‹Ήλœ κ·Έλž˜ν”„

 

μ™„μ „κ·Έλž˜ν”„

μ™„μ „ κ·Έλž˜ν”„

λͺ¨λ“  λ…Έλ“œκ°€ κ°„μ„ μœΌλ‘œ μ—°κ²°λ˜μ–΄ μžˆλŠ” κ·Έλž˜ν”„

 

κ·Έλž˜ν”„ ν‘œν˜„ 방법

인접 ν–‰λ ¬ κ·Έλž˜ν”„

좜처: https://babbab2.tistory.com/105

κ·Έλž˜ν”„μ˜ λ…Έλ“œλ₯Ό 2차원 Intν˜• λ°°μ—΄λ‘œ λ§Œλ“€μ–΄μ„œ 이동할 수 있으면 1, μ—†μœΌλ©΄ 0으둜 ν‘œκΈ°ν•œλ‹€.

 

μž₯점 : 직관적이며 μ‰½κ²Œ κ΅¬ν˜„ κ°€λŠ₯, 2차원 λ°°μ—΄μ΄λ―€λ‘œ 두 λ…Έλ“œμ— λŒ€ν•œ μ—°κ²° 정보λ₯Ό μ‘°νšŒν•  λ•Œ O(1)으둜 쑰회 κ°€λŠ₯

단점 : λͺ¨λ“  λ…Έλ“œμ— λŒ€ν•œ 간선정보λ₯Ό λŒ€μž…ν•˜λŠ” κ³Όμ •μ—μ„œ O(n^2)의 μ‹œκ°„λ³΅μž‘λ„κ°€ μ†Œμš”λ˜κ³ , λ©”λͺ¨λ¦¬ 곡간이 λ‚­λΉ„λœλ‹€.

 

인접 리슀트 방식

좜처: https://babbab2.tistory.com/105

주둜 λ…Έλ“œλ‘œ 배열을 λ§Œλ“€μ–΄μ„œ 이듀이 갈 수 μžˆλŠ” 간선을 λ°°μ—΄ λ˜λŠ” μ—°κ²°λ¦¬μŠ€νŠΈλ‘œ μ €μž₯ν•˜λŠ” 것이닀.

(λ…Έλ“œμ˜ 데이터λ₯Ό Key κ°’μœΌλ‘œ ν•΄μ„œ Dictionary둜 λ§Œλ“€κ³ ,  Valueλ₯Ό κ°„μ„ λ“€μ˜ λ°°μ—΄λ‘œ ν‘œν˜„ν•΄λ„ λœλ‹€.)

 

μž₯점 : ν•„μš”ν•œ μ •λ³΄λ§Œ μ €μž₯ν•˜λ―€λ‘œ λ©”λͺ¨λ¦¬ μ ˆμ•½μ΄ κ°€λŠ₯, λ…Έλ“œμ˜ 연결정보λ₯Ό 탐색할 λ•Œ O(n)의 μ‹œκ°„μ΄λ©΄ κ°€λŠ₯ν•˜λ‹€. (n: κ°„μ„ μ˜ 수)

단점 : 인접 행렬에 λΉ„ν•΄ κ΅¬ν˜„μ΄ μ–΄λ ΅λ‹€. νŠΉμ • 두 λ…Έλ“œκ°€ μ—°κ²°λ˜μ—ˆλŠ”μ§€ ν™•μΈν•˜λ €λ©΄ 인접 행렬에 λΉ„ν•΄ μ‹œκ°„μ΄ μ˜€λž˜κ±Έλ¦°λ‹€.

 

  κ·Έλž˜ν”„ 트리
μ •μ˜ λ…Έλ“œμ™€ λ…Έλ“œλ₯Ό μ—°κ²°ν•˜λŠ” κ°„μ„ μœΌλ‘œ ν‘œν˜„λ˜λŠ” 자료ꡬ쑰 κ·Έλž˜ν”„μ˜ ν•œ μ’…λ₯˜, λ°©ν–₯성이 μžˆλŠ” λΉ„μˆœν™˜ κ·Έλž˜ν”„
λ°©ν–₯μ„± λ°©ν–₯ κ·Έλž˜ν”„, 무방ν–₯ κ·Έλž˜ν”„ λ‘˜λ‹€ 쑴재 λ°©ν–₯ κ·Έλž˜ν”„λ§Œ 쑴재
사이클 사이클 κ°€λŠ₯, μˆœν™˜ 및 λΉ„μˆœν™˜ κ·Έλž˜ν”„ λͺ¨λ‘ 쑴재 λΉ„μˆœν™˜ κ·Έλž˜ν”„λ‘œ 사이클이 μ‘΄μž¬ν•˜μ§€ μ•ŠλŠ”λ‹€.
루트 λ…Έλ“œ X O
λΆ€λͺ¨ / μžμ‹ 관계 X O
λ°˜μ‘ν˜•