TIL - 2024/03/28

박상우·2024년 3월 28일

TIL

📝 TIL

목록 보기

6/45

그래프 알고리즘

그래프

에지로 연결한 추상적이고 일반적인 자료구조.

트리의 경우 사이클이 없는 그래프이고, 링크드 리스트의 경우 하나의 경로로만 이루어진 그래프이다.

용어

정점(vertext), 노드(node) ⇒ 어떤 대상의 객체
에지(Edge), 링크(Link) ⇒ Vertex 간의 관계
방향성
- 무방향 그래프
- 방향 그래프
Arc
- 간선(Edge)과 같은 의미로 사용되며 방향성이 있는 그래프에서의 간선(Edge)을 의미한다.
- 간선(Edge)과 마잔가지로 두 vertex를 연결한다는 점이 같지만 간선(Edge)의 경우 A-B와 B-A를 동일하게 표시하지만, Arc의 경우 A → B, B → A는 서로 다르게 취급한다.
가중치(weight)
- a.k.a 비용(Cost). 두 노드를 연결하는 경로의 길이는 경로에 포함된 가중치의 합으로 정의. 최단 경로는 경로의 길이가 가장 짧은 경로로 정의.
- 가중치가 있는 그래프
분지수(degree)
- in-deg(u)(in-dgree): 노드 u로 들어오는 방향 에지의 개수
- out-deg(u)(out-dgree): 노드 u에서 나가는 방향 에지의 개수
- deg(u) (degree of vertex) : 노드 u에 연결된 무방향 에지의 개수
- deg(G) (degree of graph) : 무방향 그래프 G의 최대 노드 분지수
사이클(cycle) ⇒ 한 노드에서 해당 노드로 다시 돌아오는 원형 구조
트리 ⇒ 사이클이 없는 연결 그래프
신장 그래프 → 부 그래프 중 모든 그래프의 노드가 등장하는 그래프

그래프의 표현 방식

인접 리스트 (Adjacency Matrix)

인접 행렬 (Adjacency List)

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

루트 노드에서 시작해서 다음 분기로 가기 전에 해당 분기를 완벽하게 탐색하는 것을 말한다.

모든 노드를 방문하는 경우 사용
깊이 우선 탐색이 너비 우선 탐색보다 간단.
stack 또는 재귀함수를 통해 구현

def recursive_dfs(v, discovered = []):
  discovered.append(v)

  for w in adj_list[v]:
    if not w in discovered:
      discovered = recursive_dfs(w, discovered)

  return discovered

def loop_dfs(start):
  discovered = [ ]
  stack = [start]
  while stack:
    v = stack.pop()
    if v not in discovered:
      discovered.append(v)
      for w in adj_list[v][::-1]:
        stack.append(w)

  return discovered

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

루트 노드에서 시작해서 인접한 노드를 먼저 탐색하는 방법.

노드 사이 최단 거리를 찾고 싶을 때 사용
큐를 통해 구현

def bfs(start):
  discovered = [ start ]
  queue = [ start ]

  while queue:
    v = queue.pop(0)
    for w in adj_list[v]:
      if w not in discovered:
        discovered.append(w)
        queue.append(w)

  return discovered