Graph

1. Graph의 ꡬ쑰

  • 직접적인 관계가 μžˆλŠ” 경우, 두 점 사이λ₯Ό μ΄μ–΄μ£ΌλŠ” 선이 있음

  • 간접적인 관계라면 λͺ‡ 개의 점과 선에 걸쳐 이어짐

  • ν•˜λ‚˜μ˜ 점을 κ·Έλž˜ν”„μ—μ„œλŠ” 정점(vertex)라고 ν‘œν˜„, ν•˜λ‚˜μ˜ 선을 κ°„μ„ (edge)라고 함

2. Graph의 ν‘œν˜„ 방식

  • 인접 ν–‰λ ¬

    • 두 정점을 λ°”λ‘œ μ΄μ–΄μ£ΌλŠ” 간선이 μžˆλ‹€λ©΄ 이 두 정점은 μΈμ ‘ν•˜λ‹€κ³  말함

    • μ„œλ‘œ λ‹€λ₯Έ 정점듀이 μΈμ ‘ν•œ μƒνƒœμΈμ§€λ₯Ό ν‘œμ‹œν•œ ν–‰λ ¬λ‘œ 2차원 λ°°μ—΄μ˜ ν˜•νƒœλ‘œ λ‚˜νƒ€λƒ„

  • 인접 리슀트

    • 각 정점이 μ–΄λ–€ 정점과 μΈμ ‘ν•˜λŠ”μ§€ 리슀트 ν˜•νƒœλ‘œ ν‘œν˜„

3. μ•Œμ•„λ‘μ–΄μ•Ό ν•  Graph μš©μ–΄λ“€

  • 정점(vertex)

    • λ…Έλ“œλΌκ³ λ„ ν•˜λ©°, 데이터가 μ €μž₯λ˜λŠ” κ·Έλž˜ν”„μ˜ κΈ°λ³Έ μ›μ†Œ

  • κ°„μ„ (edge)

    • 정점 κ°„μ˜ 관계(정점을 μ΄μ–΄μ£ΌλŠ” μ„ )

  • 인접 정점(adjacent vertex)

    • ν•˜λ‚˜μ˜ μ •μ μ—μ„œ 간선에 μ˜ν•΄ 직접 μ—°κ²°λœ 정점

  • κ°€μ€‘μΉ˜ κ·Έλž˜ν”„ (weighted Graph)

    • μ—°κ²°μ˜ 강도가 μ–Όλ§ˆλ‚˜ λ˜λŠ”μ§€ μ ν˜€ μžˆλŠ” κ·Έλž˜ν”„

  • λΉ„ κ°€μ€‘μΉ˜ κ·Έλž˜ν”„ (unweighted Graph)

    • μ—°κ²°μ˜ 강도가 μ ν˜€ μžˆμ§€ μ•Šμ€ κ·Έλž˜ν”„

  • 무ν–₯(무방ν–₯) κ·Έλž˜ν”„ (undirected graph)

  • μ§„μž…μ°¨μˆ˜ (in-degree) / μ§„μΆœμ°¨μˆ˜ (out-degree)

    • ν•œ 정점에 μ§„μž…ν•˜κ³  μ§„μΆœν•˜λŠ” 간선이 λͺ‡ κ°œμΈμ§€ λ‚˜νƒ€λƒ„

  • 인접 (adjacency)

    • 두 정점 간에 간선이 직접 이어져 μžˆλ‹€λ©΄ 이 두 정점은 μΈμ ‘ν•œ 정점

  • 자기 루프 (self loop)

    • μ •μ μ—μ„œ μ§„μΆœν•˜λŠ” 간선이 κ³§λ°”λ‘œ 자기 μžμ‹ μ—κ²Œ μ§„μž…ν•˜λŠ” 경우 자기 루프λ₯Ό κ°€μ‘Œλ‹€λΌκ³  ν‘œν˜„

    • λ‹€λ₯Έ 정점을 κ±°μΉ˜μ§€ μ•ŠλŠ”λ‹€λŠ” 것이 νŠΉμ§•

  • 사이클(cycle)

    • ν•œ μ •μ μ—μ„œ μΆœλ°œν•˜μ—¬ λ‹€μ‹œ ν•΄λ‹Ή μ •μ μœΌλ‘œ λŒμ•„κ°ˆ 수 μžˆλŠ” 경우

4. BFS와 DFS

  • BFS(Breadth-First Search)

    • λ„ˆλΉ„λ₯Ό λ¨Όμ € νƒμƒ‰ν•˜λŠ” 방법을 Breadth-First Search, λ„ˆλΉ„ μš°μ„  탐색이라고 함

    • 주둜 두 정점 μ‚¬μ΄μ˜ μ΅œλ‹¨ 경둜λ₯Ό 찾을 λ•Œ μ‚¬μš©

  • DFS(Depth-First Search)

    • ν•œ μ •μ μ—μ„œ μ‹œμž‘ν•΄μ„œ λ‹€μŒ 경둜둜 λ„˜μ–΄κ°€κΈ° 전에 ν•΄λ‹Ή 경둜λ₯Ό μ™„λ²½ν•˜κ²Œ 탐색할 λ•Œ μ‚¬μš©

    • BFS보닀 탐색 μ‹œκ°„μ€ 쑰금 였래 걸릴지라도 λͺ¨λ“  λ…Έλ“œλ₯Ό μ™„μ „νžˆ 탐색 κ°€λŠ₯

PreviousAlgorithmNextQueue

Last updated