DataStructure - Graph

Tae Yun ChoiΒ·2023λ…„ 4μ›” 18일
Graphdatastructure
0

κ°œλ°œμƒˆλ°œ 자료ꡬ쑰

λͺ©λ‘ 보기
3/3
post-thumbnail

정점과 κ°„μ„ μœΌλ‘œ 이루어진 자료ꡬ쑰

  • 정점(Vertex)와 κ°„μ„ (Edge)둜 이루어진 자료ꡬ쑰λ₯Ό μ˜λ―Έν•œλ‹€.
  • cf) νŠΈλ¦¬λŠ” 루트 λ…Έλ“œκ°€ μ‘΄μž¬ν•˜λŠ” 것에 λ°˜ν•΄ κ·Έλž˜ν”„λŠ” μ‘΄μž¬ν•˜μ§€ μ•ŠλŠ”λ‹€.
  • cf) 트리 λ˜ν•œ κ·Έλž˜ν”„λ‘œ λ³Ό 수 있으며 사이클이 ν—ˆμš©λ˜μ§€ μ•Šμ•„μ•Ό ν•œλ‹€.

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

λ°©ν–₯μ„±

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

  • A β†’ B, B β†’ A
  • λ…Έλ“œλ₯Ό μž‡λŠ” 간선은 λ°©ν–₯성이 μ—†κΈ° λ•Œλ¬Έμ— 좜발 λ…Έλ“œμ™€ 상관없이 두 λ…Έλ“œ κ°„ 이동이 κ°€λŠ₯ν•˜λ‹€.
  • μ–‘μͺ½μ„ μž‡λŠ” 간선이 μ‘΄μž¬ν•œλ‹€.

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

  • A β†’ B둜 갈 수 μžˆμ§€λ§Œ B β†’ A둜 갈 수 없을 μˆ˜λ„ μžˆλ‹€.
  • 즉 λ…Έλ“œ 사이에 μ‘΄μž¬ν•˜λŠ” 간선에 λ°©ν–₯이 μ‘΄μž¬ν•œλ‹€.

Degree

  • 무방ν–₯ κ·Έλž˜ν”„μ—μ„œ 각 정점에 μ—°κ²°λœ κ°„μ„ μ˜ 개수λ₯Ό Degree라 ν•œλ‹€.
  • λ°©ν–₯ κ·Έλž˜ν”„μ—μ„œ λ…Έλ“œμ—μ„œ μΆœλ°œν•˜λŠ” κ°„μ„ μ˜ 개수λ₯Ό OutDegree, λ…Έλ“œλ‘œ λ„μ°©ν•˜λŠ” κ°„μ„ μ˜ 개수λ₯Ό InDegree라 ν•œλ‹€.

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

  • κ°€μ€‘μΉ˜ κ·Έλž˜ν”„λŠ” 각 간선에 κ°€μ€‘μΉ˜λ₯Ό 두어 κ΅¬μ„±ν•œ κ·Έλž˜ν”„μ΄λ‹€.

λΆ€λΆ„ κ·Έλž˜ν”„

  • κ·Έλž˜ν”„μ˜ 일뢀 정점 및 κ°„μ„ μœΌλ‘œ 이루어진 κ·Έλž˜ν”„μ΄λ‹€.
  • cf) λΆ€λΆ„ μ‹ μž₯ κ·Έλž˜ν”„λž€, λΆ€λΆ„ κ·Έλž˜ν”„ 쀑 μ›λž˜ κ·Έλž˜ν”„μ˜ λͺ¨λ“  정점을 ν¬ν•¨ν•˜λŠ” κ·Έλž˜ν”„μ΄λ‹€.

κ·Έλž˜ν”„λ₯Ό κ΅¬ν˜„ν•˜λŠ” 방법


인접 ν–‰λ ¬ (adjacent matrix)

  • 정점 κ°„ μ—°κ²° μ—¬λΆ€λ₯Ό ν™•μΈν•˜κΈ° μœ„ν•΄μ„œλŠ” ν•΄λ‹Ή μœ„μΉ˜μ˜ value에 직접 μ ‘κ·Όν•˜λŠ” λ°©μ‹μœΌλ‘œ λ°”λ‘œ 확인할 수 μžˆμœΌλ―€λ‘œ O(1)의 μ‹œκ°„μ΄ κ±Έλ¦°λ‹€.
  • κ³΅κ°„λ³΅μž‘λ„λŠ” Edge κ°œμˆ˜μ™€ 관계없이 O(Vertex^2)

인접 리슀트 (adjacent list)

  • 정점 κ°„ μ—°κ²° μ—¬λΆ€λ₯Ό ν™•μΈν•˜κΈ° μœ„ν•΄μ„œλŠ” 각 μ •μ λ§ˆλ‹€ μΈμ ‘λ¦¬μŠ€νŠΈλ₯Ό ν™•μΈν•΄μ•Όν•˜λ―€λ‘œ 정점 κ°„ 연결이 λ˜μ–΄μžˆλŠ”μ§€ 순차적으둜 λͺ¨λ‘ νƒμƒ‰ν•΄μ•Όν•œλ‹€.
    • 무방ν–₯ κ·Έλž˜ν”„μΌ μ‹œ - O(λ…Έλ“œ 1의 κ°„μ„  개수 or λ…Έλ“œ 2의 κ°„μ„  개수)
    • λ°©ν–₯ κ·Έλž˜ν”„ 일 μ‹œ - O(좜발 λ…Έλ“œμ˜ κ°„μ„  개수)
  • κ³΅κ°„λ³΅μž‘λ„λŠ” O(Edge + Vertex)

κ·Έλž˜ν”„ 탐색 방법


깊이 μš°μ„  탐색 - DFS (Depth First Search)

  • κ·Έλž˜ν”„μ— μ—°κ²°λœ 정점듀을 따라 ν•œ λ°©ν–₯으둜 계속 λ‚˜μ•„κ°„λ‹€
  • 더 이상 λ‚˜μ•„κ°ˆ 곳이 μ—†μœΌλ©΄ 이전 λ‹¨κ³„λ‘œ λŒμ•„κ°„λ‹€. - μž¬κ·€μ™€ λΉ„μŠ·ν•˜μ§€ μ•Šμ€κ°€?
  • μ‹œκ°„λ³΅μž‘λ„λŠ” ν•΄λ‹Ή 곡간 만큼의 μ‹œκ°„μ΄ κ±Έλ¦¬λ―€λ‘œ O(V + E)
  • μŠ€νƒ or μž¬κ·€λ₯Ό μ΄μš©ν•˜μ—¬ κ΅¬ν˜„ν•  수 μžˆλ‹€.
  • 사이클 쑴재 μ—¬λΆ€λ₯Ό 확인할 λ•Œ μ‚¬μš©ν•œλ‹€.
    • μ‚¬μ΄ν΄μ˜ μ‘΄μž¬ν•˜λŠ” λ°©ν–₯만 찾으면 사이클을 확인할 수 μžˆλ‹€.

λ„ˆλΉ„ μš°μ„  탐색 - BFS (Breadth First Search)

  • κ·Έλž˜ν”„μ— μ—°κ²°λœ 정점듀을 ν˜„μž¬ λ…Έλ“œμ™€ μΈμ ‘ν•œ μˆœμ„œλ‘œ νƒμƒ‰ν•œλ‹€.
    • κ°€κΉŒμš΄ μˆœμ„œλ‘œ νƒμƒ‰ν•˜κΈ° λ•Œλ¬Έμ— μ΅œλ‹¨κ±°λ¦¬λ₯Ό 계산할 λ•Œ 주둜 μ‚¬μš©ν•œλ‹€.
  • 더 이상 λ°©λ¬Έν•  인접 λ…Έλ“œκ°€ 없을 λ•ŒκΉŒμ§€ λ°˜λ³΅ν•œλ‹€.
  • μ‹œκ°„λ³΅μž‘λ„λŠ” ν•΄λ‹Ή 곡간 만큼의 μ‹œκ°„μ΄ κ±Έλ¦¬λ―€λ‘œ O(V + E)
  • 큐λ₯Ό μ΄μš©ν•˜μ—¬ κ΅¬ν˜„ν•  수 μžˆλ‹€.

좜처

profile
Tae Yun Choi
hello dev!!
이전 포슀트

DataStructure - Queue

0개의 λŒ“κΈ€