Skip to content

Latest commit

Β 

History

History
170 lines (137 loc) Β· 6.55 KB

Graph.md

File metadata and controls

170 lines (137 loc) Β· 6.55 KB

Graph

κ·Έλž˜ν”„

λ…Έλ“œ(N)와 κ·Έ λ…Έλ“œλ₯Ό μ—°κ²°ν•˜λŠ” κ°„μ„ (E)을 ν•˜λ‚˜λ‘œ λͺ¨μ•„ 놓은 자료ꡬ쑰

  • 지도, 노선도, λ„λ‘œμ²˜λŸΌ μ—°κ²°λ˜μ–΄ μžˆλŠ” κ°μ²΄κ°„μ˜ 관계λ₯Ό ν‘œν˜„ν•  수 μžˆλŠ” 자료ꡬ쑰
  • κ·Έλž˜ν”„λŠ” μ—¬λŸ¬ 개의 고립된 λΆ€λΆ„ κ·Έλž˜ν”„(Isolated Subgraph)λ“€λ‘œ ꡬ성될 수 μžˆλ‹€

κ·Έλž˜ν”„μ™€ 트리의 차이

Untitled

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

  • 인접 정점(adjacent vertex) : 간선에 μ˜ν•΄ 직접 μ—°κ²°λœ 정점
  • 인접(adjacent) & 뢀속(incident) : μž„μ˜μ˜ 두 정점이 ν•˜λ‚˜μ˜ κ°„μ„ μœΌλ‘œ μ—°κ²°λ˜μ–΄ μžˆμ„ 경우, 이 정점듀은 μ„œλ‘œ 인접해 μžˆλ‹€κ³  ν•œλ‹€. ν•΄λ‹Ή 간선은 두 λ…Έλ“œμ— 뢀속해 μžˆλ‹€κ³  ν•œλ‹€
  • λΆ€λΆ„ κ·Έλž˜ν”„(subgraph) : κ·Έλž˜ν”„μ— ν¬ν•¨λœ 일뢀 정점과 κ°„μ„ μœΌλ‘œλ§Œ 이루어진 κ·Έλž˜ν”„
    • λΆ€λΆ„ μ‹ μž₯ κ·Έλž˜ν”„(sapnning subgraph) : λΆ€λΆ„ κ·Έλž˜ν”„ 쀑 원본 κ·Έλž˜ν”„μ˜ λͺ¨λ“  정점을 ν¬ν•¨ν•œ κ·Έλž˜ν”„ (λΆ€λΆ„ μ‹ μž₯ κ·Έλž˜ν”„μ˜ κ°„μ„ μ˜ 수 ≀ 원본 κ·Έλž˜ν”„μ˜ κ°„μ„ μ˜ 수)
  • μ •μ μ˜ 차수(degree) : 정점에 μ—°κ²°λœ κ°„μ„ μ˜ 수 ν˜Ήμ€ κ°€μ€‘μΉ˜μ˜ 합을 μ˜λ―Έν•œλ‹€
    • μ§„μž… 차수(in-degree) : λ°©ν–₯ κ·Έλž˜ν”„μ—μ„œ μ™ΈλΆ€μ—μ„œ ν•΄λ‹Ή λ…Έλ“œλ‘œ μ˜€λŠ” κ°„μ„ μ˜ 수
    • μ§„μΆœ 차수(out-degree) : λ°©ν–₯ κ·Έλž˜ν”„μ—μ„œ ν•΄λ‹Ή λ…Έλ“œμ—μ„œ μ™ΈλΆ€λ‘œ ν–₯ν•˜λŠ” κ°„μ„ μ˜ 수
  • 루프(loop) : 같은 정점을 μ—°κ²°ν•˜λŠ” κ°„μ„ (두 정점이 같은 정점)
  • 고립 정점(isolated vertex) : μ—°κ²°λœ 간선이 μ—†λŠ” 정점
  • 경둜(path) : 간선을 따라 μ΄μ–΄κ°ˆ 수 μžˆλŠ” κΈΈ (정점을 λ‚˜μ—΄ν•˜μ—¬ 경둜λ₯Ό ν‘œν˜„ν•œλ‹€)
    • 경둜의 길이(length) : 경둜λ₯Ό μ΄λ£¨λŠ” κ°„μ„ μ˜ 수
    • simple path : λ°˜λ³΅λ˜λŠ” 간선이 μ—†λŠ” 경둜
    • elementary path : λ°˜λ³΅λ˜λŠ” 정점이 μ—†λŠ” 경둜
  • 사이클(cycle) : μ‹œμž‘ 정점과 μ’…λ£Œ 정점이 λ™μΌν•œ 경둜
  • μ—°κ²°(connected) : 두 정점 μ‚¬μ΄μ˜ κ²½λ‘œκ°€ μ‘΄μž¬ν•  λ•Œ 두 정점은 μ—°κ²°λ˜μ—ˆλ‹€κ³  ν•œλ‹€
    • κ°•ν•œ μ—°κ²°(strongly connected) : 정점 a β†’ b, b β†’ a의 κ²½λ‘œκ°€ μ‘΄μž¬ν•  경우, ν•΄λ‹Ή λ°©ν–₯ κ·Έλž˜ν”„λŠ” κ°•ν•œ μ—°κ²°λ˜μ—ˆλ‹€κ³  ν•œλ‹€
    • μ•½ν•œ μ—°κ²°(weakly connected) : a β†’ b λ˜λŠ” b β†’ a 경둜 쀑 ν•˜λ‚˜λ§Œ μ‘΄μž¬ν•  경우, ν•΄λ‹Ή λ°©ν–₯ κ·Έλž˜ν”„λŠ” μ•½ν•œ μ—°κ²°λ˜μ—ˆλ‹€κ³  ν•œλ‹€

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

  • 무방ν–₯ κ·Έλž˜ν”„(undirected graph)
    • 간선을 톡해 μ–‘λ°©ν–₯으둜 이동할 수 있음 (a,b 정점을 μ—°κ²°ν•˜λŠ” 간선을 (a, b) 둜 ν‘œν˜„)
  • λ°©ν–₯ κ·Έλž˜ν”„(directed graph)
    • 간선에 λ°©ν–₯이 μ‘΄μž¬ν•¨ (a β†’ b둜만 갈 수 μžˆλŠ” 간선을 <a, b> 둜 ν‘œν˜„)
  • κ°€μ€‘μΉ˜ κ·Έλž˜ν”„(weighted graph)
    • 간선에 λΉ„μš©μ΄λ‚˜ κ°€μ€‘μΉ˜κ°€ ν• λ‹Ήλœ κ·Έλž˜ν”„
  • μ—°κ²° κ·Έλž˜ν”„(conntected graph)
    • 무방ν–₯ κ·Έλž˜ν”„μ—μ„œ μžˆλŠ” λͺ¨λ“  정점 μŒμ— κ²½λ‘œκ°€ 항상 μ‘΄μž¬ν•˜λŠ” 경우
  • λΉ„μ—°κ²° κ·Έλž˜ν”„(disconnected graph)
    • 무방ν–₯ κ·Έλž˜ν”„μ—μ„œ νŠΉμ • μ μ •μŒ 사이에 κ²½λ‘œκ°€ μ‘΄μž¬ν•˜μ§€ μ•ŠλŠ” 경우
  • μˆœν™˜ κ·Έλž˜ν”„(cycle graph)
    • 사이클(μ‹œμž‘ 정점과 μ’…λ£Œ 정점이 λ™μΌν•œ 경둜)을 가진 κ·Έλž˜ν”„
  • λΉ„μˆœν™˜ κ·Έλž˜ν”„(acyclic graph)
    • 사이클이 μ—†λŠ” κ·Έλž˜ν”„
  • μ™„μ „ κ·Έλž˜ν”„(complete graph)
    • κ·Έλž˜ν”„μ— μ†ν•œ λͺ¨λ“  정점이 μ„œλ‘œ μ—°κ²°λ˜μ–΄ μžˆλŠ” κ·Έλž˜ν”„
    • 무방ν–₯ μ™„μ „ κ·Έλž˜ν”„ : μ •μ μ˜ μˆ˜κ°€ n이면 κ°„μ„ μ˜ μˆ˜λŠ” n * (n - 1) / 2
    • λ°©ν–₯ μ™„μ „ κ·Έλž˜ν”„ : μ •μ μ˜ μˆ˜κ°€ n이면 κ°„μ„ μ˜ μˆ˜λŠ” n * (n - 1)

κ·Έλž˜ν”„μ˜ ν‘œν˜„

인접행렬 방식 & μΈμ ‘λ¦¬μŠ€νŠΈ λ°©μ‹μœΌλ‘œ κ·Έλž˜ν”„λ₯Ό ν‘œν˜„ν•  수 있음

3.png

  • 인접 ν–‰λ ¬(adjacency matrix) : 2차원 λ°°μ—΄λ‘œ κ·Έλž˜ν”„μ˜ μ—°κ²° 관계λ₯Ό ν‘œν˜„ν•˜λŠ” 방식
    • 정점 a,bκ°€ μ„œλ‘œ μΈμ ‘ν•˜λ‹€λ©΄(ν•˜λ‚˜μ˜ κ°„μ„ μœΌλ‘œ μ—°κ²°λ˜μ–΄ μžˆλ‹€λ©΄) β†’ ν–‰λ ¬[a][b] = 1 , μΈμ ‘ν•˜μ§€ μ•Šλ‹€λ©΄ β†’ ν–‰λ ¬[a][b] = 0
    • 간선에 κ°€μ€‘μΉ˜κ°€ μžˆλ‹€λ©΄ 1 λŒ€μ‹  κ°€μ€‘μΉ˜μ˜ 값을 직접 λ„£λŠ”λ‹€.
    • μž₯점
      • 두 정점에 λŒ€ν•œ μ—°κ²° 정보 쑰회 β†’ O(1)
      • κ΅¬ν˜„μ΄ 쉬움
    • 단점
      • κ°„μ„ μ˜ μˆ˜μ™€ λ¬΄κ΄€ν•˜κ²Œ n^2 의 λ©”λͺ¨λ¦¬ 곡간이 ν•„μš” β†’ λ©”λͺ¨λ¦¬ 곡간 λ‚­λΉ„κ°€ 큼
      • νŠΉμ • 정점과 μΈμ ‘ν•œ 정점듀을 μ°ΎκΈ° μœ„ν•΄ ν–‰ 전체λ₯Ό μˆœνšŒν•΄μ•Ό 함 β†’ O(N) (μΈμ ‘ν•˜μ§€ μ•ŠλŠ” λ…Έλ“œκΉŒμ§€ 탐색해야 함)

4.png

  • 인접 리슀트(adjacency list) : 리슀트둜 κ·Έλž˜ν”„μ˜ μ—°κ²° 관계λ₯Ό ν‘œν˜„ν•˜λŠ” 방식
    • μž₯점
      • νŠΉμ • 정점과 μΈμ ‘ν•œ 정점듀을 찾을 λ•Œ ν•΄λ‹Ή μ •μ μ˜ 인접 리슀트만 순회 β†’ O(N) (μΈμ ‘ν•œ λ…Έλ“œλ“€λ§Œ 탐색할 수 있음)
      • μ •μ μ˜ 수 + κ°„μ„ μ˜ 수(n+e) 만큼의 λ©”λͺ¨λ¦¬ 곡간이 ν•„μš” β†’ λ©”λͺ¨λ¦¬ 곡간 λ‚­λΉ„κ°€ 적음
    • 단점
      • 두 정점에 λŒ€ν•œ μ—°κ²° 정보λ₯Ό μ‘°νšŒν•˜κΈ° μœ„ν•΄ 인접 리슀트 전체λ₯Ό 탐색해야 함 β†’ μ΅œμ•… O(N)
      • κ΅¬ν˜„μ΄ 어렀움

κ·Έλž˜ν”„ 탐색

깊이 μš°μ„  탐색(dfs)와 λ„ˆλΉ„ μš°μ„  탐색(bfs)κ°€ 있음

  • dfsλŠ” μŠ€νƒμœΌλ‘œ κ΅¬ν˜„ν•  수 있음

18.png

def dfs(graph, v, visited):
    # λ…Έλ“œvλ₯Ό 방문처리
    visited[v] = True
    print(v, "visit!")
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)
    print(v, "pop!")


graph = [
    [1, 2, 4],
    [0, 2],
    [0, 1, 3, 4],
    [2, 4],
    [0, 2, 3]
]
visited = [False] * 5

dfs(graph, 0, visited)

"""
0 visit!
1 visit!
2 visit!
3 visit!
4 visit!
4 pop!
3 pop!
2 pop!
1 pop!
0 pop!
"""

  • bfsλŠ” queue둜 κ΅¬ν˜„ν•  수 있음

19.png

from collections import deque


def bsf(graph, start, visited):
    # 큐에 startλ…Έλ“œλ₯Ό 집어 λ„£λŠ”λ‹€
    queue = deque([start])
    # startλ…Έλ“œλ₯Ό λ°©λ¬Έμ²˜λ¦¬ν•œλ‹€
    visited[start] = True
    while queue:
        print(queue, end=" ")
        # νμ—μ„œ λ…Έλ“œλ₯Ό κΊΌλ‚Έλ‹€
        now = queue.popleft()
        # κΊΌλ‚Έ λ…Έλ“œλ₯Ό 좜λ ₯ν•œλ‹€ : λ°©λ¬Έμ²˜λ¦¬ν• λ•Œ 좜λ ₯해도 λ¬΄κ΄€ν•˜μ§€λ§Œ, 이 방법이 더 κ°„κ²°
        print(now, "visit!")
        for i in graph[now]:
            if not visited[i]:
                queue.append(i)
                # 큐의 μ§‘μ–΄λ„£κ³ λ‚˜μ„œ, λ°©λ¬Έ μ²˜λ¦¬ν•œλ‹€
                visited[i] = True


graph = [
    [1, 2, 4],
    [0, 2],
    [0, 1, 3, 4],
    [2, 4],
    [0, 2, 3]
]
visited = [False] * 5
bsf(graph, 0, visited)

"""
deque([0]) 0 visit!
deque([1, 2, 4]) 1 visit!
deque([2, 4]) 2 visit!
deque([4, 3]) 4 visit!
deque([3]) 3 visit!
"""