λ³Έλ¬Έ λ°”λ‘œκ°€κΈ°
πŸ“š Computer Science/Data Structure

[자료ꡬ쑰] κ·Έλž˜ν”„(Graph)

by hyebin (Helia) 2023. 3. 8.
λ°˜μ‘ν˜•

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

  • μ—°κ²°λ˜μ–΄μžˆλŠ” μ›μ†Œκ°„μ˜ 관계λ₯Ό ν‘œν˜„ν•œ 자료ꡬ쑰
  • λ…Έλ“œ(Node)와 κ·Έ λ…Έλ“œλ₯Ό μ—°κ²°ν•˜λŠ” κ°„μ„ (Edge)을 ν•˜λ‚˜λ‘œ λͺ¨μ•„ 놓은 자료ꡬ쑰

κ·Έλž˜ν”„ κ΄€λ ¨ μš©μ–΄

  • 정점(vertex): μœ„μΉ˜λΌλŠ” κ°œλ… (node 라고도 뢀름)
  • κ°„μ„ (edge): μœ„μΉ˜ κ°„μ˜ 관계, λ…Έλ“œλ₯Ό μ—°κ²°ν•˜λŠ” μ„  (link, branch 라고도 뢀름)
  • 인접 μ •μ (adjacent vertex): κ°„선에 μ˜ ν•΄ μ§μ ‘ μ—°κ²°λœ μ •μ 
  • μ •μ μ˜ μ°¨μˆ˜(degree): λ¬΄λ°©ν–₯ κ·Έλž˜ν”„μ—μ„œ ν•˜λ‚˜μ˜ μ •μ μ— μΈμ ‘ν•œ μ •μ μ˜ μˆ˜
    • 무방ν–₯ κ·Έλž˜ν”„에 μ‘΄μž¬ν•˜λŠ” μ •μ μ˜ λͺ¨λ“  μ°¨μˆ˜μ˜ ν•© = κ·Έλž˜ν”„μ˜ κ°„μ„  μˆ˜μ˜ 2λ°°
  • μ§„μž… μ°¨μˆ˜(in-degree): λ°©ν–₯ κ·Έλž˜ν”„μ—μ„œ μ™ΈλΆ€μ—μ„œ μ˜€λŠ” κ°„μ„ μ˜ μˆ˜ (λ‚΄μ°¨μˆ˜ λΌκ³ λ„ λΆ€λ¦„)
  • μ§„μΆœ μ°¨μˆ˜(out-degree): λ°©ν–₯ κ·Έλž˜ν”™μ—μ„œ μ™ΈλΆ€λ‘œ ν–₯ν•˜λŠ” κ°„μ„ μ˜ μˆ˜ (μ™Έμ°¨μˆ˜ λΌκ³ λ„ λΆ€λ¦„)
    • λ°©ν–₯ κ·Έλž˜ν”„에 μžˆλŠ” μ •μ μ˜ μ§„μž… μ°¨μˆ˜ λ˜λŠ” μ§„μΆœ μ°¨μˆ˜μ˜ ν•© = λ°©ν–₯ κ·Έλž˜ν”„μ˜ κ°„μ„ μ˜ μˆ˜(λ‚΄μ°¨μˆ˜ + μ™Έμ°¨μˆ˜)
  • 경둜 κΈΈμ΄(path length): κ²½λ‘œλ₯Ό κ΅¬μ„±ν•˜λŠ” λ° μ‚¬μš©λœ κ°„μ„ μ˜ μˆ˜
  • λ‹¨μˆœ κ²½λ‘œ(simple path): κ²½λ‘œ μ€‘μ—μ„œ λ°˜λ³΅λ˜λŠ” μ •μ μ΄ μ—†λŠ” κ²½μš°
  • 사이클(cycle): λ‹¨μˆœ 경둜의 μ‹œμž‘ 정점과 μ’…λ£Œ 정점이 λ™μΌν•œ 경우

κ·Έλž˜ν”„μ˜ νŠΉμ§•

  • λ„€νŠΈμ›Œν¬ λͺ¨λΈ 
  • 2개 μ΄μƒμ˜ κ²½λ‘œκ°€ κ°€λŠ₯
    • λ…Έλ“œλ“€ 사이에 무방ν–₯/λ°©ν–₯μ—μ„œ μ–‘λ°©ν–₯ 경둜λ₯Ό κ°€μ§ˆ 수 있음
  • self-loop 뿐 μ•„λ‹ˆλΌ loop/circuit λͺ¨λ‘ κ°€λŠ₯
  • 루트 λ…Έλ“œλΌλŠ” κ°œλ…μ΄ μ—†μŒ
  • λΆ€λͺ¨-μžμ‹ κ΄€κ³„λΌλŠ” κ°œλ…μ΄ μ—†μŒ
  • μˆœνšŒλŠ” DFSλ‚˜ BFS둜 이루어짐
  • κ·Έλž˜ν”„λŠ” μˆœν™˜(Cyclic) ν˜Ήμ€ λΉ„μˆœν™˜(Acyclic)
  • κ·Έλž˜ν”„λŠ” ν¬κ²Œ λ°©ν–₯ κ·Έλž˜ν”„와 λ¬΄λ°©ν–₯ κ·Έλž˜ν”„κ°€ μžˆμŒ
  • κ°„μ„ μ˜ μœ λ¬΄λŠ” κ·Έλž˜ν”„μ— 따라 닀름

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

1. 무방ν–₯ κ·Έλž˜ν”„ (Undirected Graph)

  • 두 정점을 μ—°κ²°ν•˜λŠ” 간선에 λ°©ν–₯이 μ—†λŠ” κ·Έλž˜ν”„
  • 정점 A와 정점 Bλ₯Ό μ—°κ²°ν•˜λŠ” 간선은 (A, B)와 같이 μ •μ μ˜ 쌍으둜 ν‘œν˜„
    • (A, B)λŠ” (B, A) 동일

2. λ°©ν–₯ κ·Έλž˜ν”„ (Directed Graph)

  • 두 정점을 μ—°κ²°ν•˜λŠ” 간선에 λ°©ν–₯이 μžˆλŠ” κ·Έλž˜ν”„
  • A -> B둜만 갈 수 μžˆλŠ” 간선은 <A, B>둜 ν‘œμ‹œ
    • <A, B>λŠ” <B, A>λŠ” 닀름

3. μ™„μ „ κ·Έλž˜ν”„ (Complete Graph)

  • κ·Έλž˜ν”„μ— 속해 μžˆλŠ” λͺ¨λ“  정점이 μ„œλ‘œ μ—°κ²°λ˜μ–΄ μ΅œλŒ€ κ°„μ„  수λ₯Ό κ°–λŠ” κ·Έλž˜ν”„
  • 정점이 n개인 μ™„μ „ κ·Έλž˜ν”„μ—μ„œ 무방ν–₯ κ·Έλž˜ν”„μ˜ μ΅œλŒ€ κ°„μ„ μˆ˜λŠ” n*(n-1)/2
  • 정점이 n개인 μ™„μ „ κ·Έλž˜ν”„μ—μ„œ λ°©ν–₯ κ·Έλž˜ν”„μ˜ μ΅œλŒ€ κ°„μ„ μˆ˜λŠ” (n-1)

4. λΆ€λΆ„ κ·Έλž˜ν”„ (Subgraph)

  • 기쑴의 κ·Έλž˜ν”„μ—μ„œ 일뢀 μ •μ μ΄λ‚˜ 간선을 μ œμ™Έν•˜μ—¬ λ§Œλ“  κ·Έλž˜ν”„

5. 가쀑 κ·Έλž˜ν”„ (Weight Graph)

  • 정점을 μ—°κ²°ν•˜λŠ” 간선에 κ°€μ€‘μΉ˜(Weight)λ₯Ό ν• λ‹Ήν•œ κ·Έλž˜ν”„

6. 유ν–₯ λΉ„μˆœν™˜ κ·Έλž˜ν”„ (DAG, Directed Acyclic Graph)

  • λ°©ν–₯ κ·Έλž˜ν”„μ—μ„œ 사이클이 μ—†λŠ” κ·Έλž˜ν”„

7. μ—°κ²° κ·Έλž˜ν”„ (Connected Graph)

  • λ–¨μ–΄μ Έ μžˆλŠ” 정점이 μ—†λŠ” κ·Έλž˜ν”„

8. λ‹¨μ ˆ κ·Έλž˜ν”„ (Disconnected Graph)

  • μ—°κ²°λ˜μ§€ μ•Šμ€ 정점이 μžˆλŠ” κ·Έλž˜ν”„

 

κ·Έλž˜ν”„μ˜ κ΅¬ν˜„

인접 리슀트

  • κ·Έλž˜ν”„ λ‚΄μ— μ μ€ μˆ«μžμ˜ κ°„μ„ λ§Œμ„ κ°€μ§€λŠ” ν¬μ†Œ κ·Έλž˜ν”„(Sparse Graph) μ˜ κ²½μš°
  • μž₯점
    • μ–΄λ–€ λ…Έλ“œμ— μΈμ ‘ν•œ λ…Έλ“œλ“€ 을 μ‰½κ²Œ 찾을 수 있음
    • κ·Έλž˜ν”„μ— μ‘΄μž¬ν•˜λŠ” λͺ¨λ“  κ°„μ„ μ˜ 수 λŠ” O(N+E) μ•ˆμ— μ•Œ 수 있음 -> 인접 리슀트 전체λ₯Ό 쑰사함
  • 단점
    • κ°„μ„ μ˜ μ‘΄μž¬ μ—¬λΆ€μ™€ μ •μ μ˜ μ°¨μˆ˜: μ •μ  i의 λ¦¬μŠ€νŠΈμ— μžˆλŠ” λ…Έλ“œμ˜ μˆ˜ μ¦‰, μ •μ  μ°¨μˆ˜λ§ŒνΌμ˜ μ‹œκ°„이 ν•„μš”

인접 ν–‰λ ¬

  • κ·Έλž˜ν”„μ— κ°„선이 λ§Žμ΄ μ‘΄μž¬ν•˜λŠ” λ°€μ§‘ κ·Έλž˜ν”„(Dense Graph) μ˜ κ²½μš°
  • μž₯점
    • 두 μ •μ μ„ μ—°κ²°ν•˜λŠ” κ°„μ„ μ˜ μ‘΄μž¬ μ—¬λΆ€ (M[i][j])λ₯Ό O(1) μ•ˆμ— μ¦‰μ‹œ μ•Œ μˆ˜ μžˆμŒ
    • μ •μ μ˜ 차수 λŠ” O(N) μ•ˆμ— μ•Œ 수 있음 -> 인접 λ°°μ—΄μ˜ i번 μ§Έ ν–‰ λ˜λŠ” 열을 λͺ¨λ‘ 더함
  • 단점
    • μ–΄λ–€ λ…Έλ“œμ— μΈμ ‘ν•œ λ…Έλ“œλ“€μ„ μ°ΎκΈ° μœ„ν•΄μ„œλŠ” λͺ¨λ“  λ…Έλ“œλ₯Ό μ „λΆ€ μˆœνšŒν•΄μ•Ό ν•¨
    • κ·Έλž˜ν”„μ— μ‘΄μž¬ν•˜λŠ” λͺ¨λ“  κ°„μ„ μ˜ μˆ˜λŠ” O(N^2) μ•ˆμ— μ•Œ 수 있음 -> 인접 ν–‰λ ¬ 전체λ₯Ό 쑰사

κ·Έλž˜ν”„μ˜ 탐색

1. 깊이 μš°μ„  탐색(DFS, Depth-Firsh Search)

  • 루트 λ…Έλ“œ(ν˜Ήμ€ λ‹€λ₯Έ μž„μ˜μ˜ λ…Έλ“œ)μ—μ„œ μ‹œμž‘ν•΄μ„œ λ‹€μŒ λΆ„κΈ°(branch)둜 λ„˜μ–΄κ°€κΈ° μ „에 ν•΄λ‹Ή λΆ„κΈ°λ₯Ό μ™„λ²½ν•˜κ²Œ νƒμƒ‰ν•˜λŠ” λ°©λ²•
  • λͺ¨λ“  λ…Έλ“œλ₯Ό λ°©λ¬Έ ν•˜κ³ μž ν•˜λŠ” κ²½μš°μ— 이 방법을 선택
  • BFS 보닀 μ’€ 더 간단

2. λ„ˆλΉ„ μš°μ„  탐색(BFS, Breadth-Firsh Search)

  • 루트 λ…Έλ“œ(ν˜Ήμ€ λ‹€λ₯Έ μž„μ˜μ˜ λ…Έλ“œ)μ—μ„œ μ‹œμž‘ν•΄μ„œ μΈμ ‘ν•œ λ…Έλ“œλ₯Ό λ¨Όμ € νƒμƒ‰ν•˜λŠ” 방법
  • 두 λ…Έλ“œ μ‚¬μ΄μ˜ μ΅œλ‹¨ 경둜 ν˜Ήμ€ μž„μ˜μ˜ 경둜λ₯Ό μ°Ύκ³  싢을 λ•Œ 이 방법을 선택

λ°˜μ‘ν˜•
μ €μž‘μžν‘œμ‹œ λΉ„μ˜λ¦¬ λ³€κ²½κΈˆμ§€ (μƒˆμ°½μ—΄λ¦Ό)

'πŸ“š Computer Science > Data Structure' μΉ΄ν…Œκ³ λ¦¬μ˜ λ‹€λ₯Έ κΈ€

[자료ꡬ쑰] νž™(Heap)  (0) 2023.03.13
[자료ꡬ쑰] 트리(Tree)  (0) 2023.03.09
[자료ꡬ쑰] Time Complexity (μ‹œκ°„ λ³΅μž‘λ„)  (0) 2023.03.07
[자료ꡬ쑰] 큐(Queue)  (0) 2023.03.06
[자료ꡬ쑰] μŠ€νƒ(Stack)  (0) 2023.02.14

κ΄€λ ¨κΈ€

ν‹°μŠ€ν† λ¦¬νˆ΄λ°”