Graph

Created : February 07, 2021

Graph = 객체의 일부 쌍(pair)들이 연관되어 있는 객체 집합 구조

관련 용어

  • 정점(Vertex)
  • 간선(Edge)
  • 차수(Degree)

그래프를 표현하는 방법

  • 인접 행렬(Adjacency Matrix)
  • 인접 리스트(Adjacency List)

    • 출발노드를 key로, 도착노드를 value로.
    • 도착노드는 여러 개가 될 수 있음 → List 형태로.
graph = {
  1: [2, 3, 4],
  2: [5],
  3: [5],
  4: [],
  5: [6, 7],
  6: [],
  7: [3],
}

오일러 경로

  • 오일러의 정리: 모든 정점이 짝수 개의 차수를 갖는다면, 모든 간선을 한 번씩만 그
  • 오일러 회로:
  • 오일러 경로 존재여부 판단?

    • 무향 그래프인 경우, Degree가 홀수인 정점이 2개이면 오일러 경로, 0개면 오일러 회로가 존재.

해밀턴 경로 (Hamiltonian Path)

각 정점을 한번씩만 방문하는 무향 or 유향 그래프 경로

  • 오일러 경로: 간선 기준 / 해밀턴 경로: 정점 기준
  • 오일러 경로: 모든 edge를 정확히 1번씩만 방문하는 연속된 경로

    • 오일러 회로: 시작점과 도착점이 같은 경우
  • 해밀턴 경로를 찾는 문제는 최적 알고리즘이 없는 NP-완전 문제
  • 해밀턴 순환(Hamiltonian Cycle): 정점을 한번씩만 방문하고 원래 출발점으로 돌아오는 경로
  • 외판원 문제: 정점을 한번씩만 방문하고 원래 출발점으로 돌아오는 경로 중 가장 짧은 경로

    • = 해밀턴 순환 중 최단거리

그래프 순회 (Graph Traversals) - DFS/BFS

그래프의 각 정점을 방문하는 과정 (=그래프 탐색)

깊이 우선 탐색 (DFS = Depth-First Search)

  • BFS보다 널리 쓰임
  • 주로 스택 or 재귀로 구현됨
  • 백트래킹을 통해 효용 뛰어남
  • 재귀 구조로 구현
def recursive_dfs(v, discovered=[]):
  discovered.append(v)
  for w in graph[v]:
    if not w in discovered:
      discovered = recursive_dfs(w, discovered)
  
  return discovered

너비 우선 탐색 (BFS = Breadth-First Search)

  • 주로 로 구현됨
  • 최단 경로를 찾는 다익스트라 알고리즘 등에 유용