주니어 백엔드 개발자 인터뷰

# 그래프(Graph)

# 그래프란 무엇인가요?

  • 정점(vertex)과 간선(edge)으로 이루어진 자료구조입니다.
  • 연결되어 있는 객체 간의 관계를 표현할 수 있는 자료구조입니다.
  • 부모-자식, 루트노드의 개념이 존재하지 않습니다.
  • 지도, 지하철 노선도의 최단경로, 도로 등과 같은 문제에 사용합니다.
  • DFS, BFS를 통해 순회합니다.

# 그래프와 관련된 용어

  • 정점(vertex): 위치라는 개념. (node 라고도 부름)
  • 간선(edge): 위치 간의 관계. 즉, 노드를 연결하는 선 (link, branch 라고도 부름)
  • 인접 정점(adjacent vertex): 간선에 의해 직접 연결된 정점
  • 차수(degree): 무방향 그래프에서 하나의 정점에 인접한 정점의 수
  • 진입 차수(in-degree): 방향 그래프에서 외부에서 오는 간선의 수 (내차수 라고도 부름)
  • 진출 차수(out-degree): 방향 그래픙에서 외부로 향하는 간선의 수 (외차수 라고도 부름)
  • 경로 길이(path length): 경로를 구성하는 데 사용된 간선의 수
  • 단순 경로(simple path): 경로 중에서 반복되는 정점이 없는 경우
  • 사이클(cycle): 단순 경로의 시작 정점과 종료 정점이 동일한 경우

# 그래프의 종류

  • 가중치 그래프 : 간선에 비용(가중치)가 할당된 그래프로, 두 정점을 이동할 때 비용이 듭니다.
    가중치 그래프
  • 방향성
    • 무방향 그래프 : 간선에 방향이 없는 그래프로, (A,B)로 표시합니다.
      무뱡향그래프
    • 방향 그래프 : 간선에 방향이 있는 그래프로, A->B로 가는 간선을 <A,B>로 표시합니다.
      방향그래프
  • 사이클
    • 순환 그래프 : 단순 경로에서 시작정점과 도착정점이 동일한 그래프입니다.
      순환그래프
    • 비순환 그래프 : 순환 그래프를 제외한 그래프로, 사이클이 없는 그래프입니다.
      비순환그래프
  • 연결
    • 연결 그래프 : 무방향 그래프에서 노드들이 모두 간선에 의해 연결되어 있는 그래프로, 트리(tree)가 대표적인 예입니다.
      연결그래프
    • 비연결 그래프 : 무방향 그래프에서 간선에 의해 연결되어 있지 않은 노드가 있는 그래프입니다.
      비연결그래프
    • 완전 그래프 : 그래프의 모든 정점이 서로 연결되어 있는 그래프입니다.
      완전그래프

오일러 경로

그래프에 존재하는 모든 간선을 한번만 통과하면서 처음 정점으로 되돌아오는 경로를 말합니다. 그래프의 모든 정점에 연결된 간선의 개수가 짝수일 때만 오일러 경로가 존재합니다.

# 그래프의 표현

  1. 인접 행렬 (Adjacency Matrix)
    인접행렬은 그래프의 노드를 2차원으로 만든 것입니다.
    노드들 간에 직접 연결이 되어 있으면 1을, 아니면 0을 넣어서 행렬을 완성시킵니다.
    인접행렬

    • 장점
      1. 두 정점에 대한 연결 정보(M[i][j])를 조회할 때 O(1)의 시간복잡도가 걸립니다.
      2. 인접리스트에 비해 구현이 쉽습니다.
      3. 정점의 차수를 O(n)안에 알 수 있습니다.
    • 단점
      1. 항상 n^2개의 메모리 공간이 필요해, 공간이 낭비될 경우가 많습니다.
      2. 인접한 노드를 찾기 위해서는 모든 노드를 전부 순회해야 합니다.

  2. 인접 리스트 (Adjacency List)
    인접리스트는 그래프의 노드를 리스트로 표현한 것입니다. 그래프를 표현하는 가장 일반적인 방식입니다.
    인접리스트

  • 장점
    1. 노드에 인접한 노드들을 쉽게 찾을 수 있습니다.
    2. 공간의 낭비가 적습니다.
    3. 그래프에 존재하는 모든 간선의 수를 O(n+e)안에 알 수 있습니다.
  • 단점
    1. 특정 두 점이 연결되어있는 지 확인하려면 인접행렬에 비해 사간이 걸립니다. O(e)시간 소요.
    2. 구현이 비교적 어렵습니다.

선택 기준

그래프에 간선이 많이 존재하는 밀집그래프의 경우에는 인접행렬을, 그래프에 적은 간선을 가지는 희소그래프의 경우에는 인접리스트를 사용하는게 좋습니다.

# 그래프의 탐색

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

    • 루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법입니다.
    • 넓게(wide) 탐색하기 전에 깊게(deep) 탐색하는 것입니다.
    • 모든 노드를 방문하고자 할 때 사용하는게 좋습니다.

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

    • 루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법입니다.
    • 깊게(deep)탐색하기 전에 넓게(wide)탐색하는 것입니다.
    • 두 노드 사이의 최단 경로, 임의의 경로를 찾고 싶을 때 사용하는게 좋습니다.

# 그래프와 신장트리

  • 신장트리(Spanning Tree)

    • 연결 그래프의 부분그래프로서 그 그래프의 모든 정점과 간선의 부분 집합으로 구성되는 트리입니다.
    • 모든 노드는 적어도 하나의 간선에 연결되어 있어야 하지만, 사이클이 형성되면 안됩니다.
    • 연결 그래프일 때 DFS, BFS를 통해서 구현이 가능합니다.
      신장트리

  • 최소 비용 신장 트리(Minimum Cost Spaning Tree)

    • 신장트리 중 간선의 가중치 합이 최소인 신장트리입니다.
    • 프림(Prim), 크루스칼(Kruskal) 등을 통해 최소비용신장트리를 찾아낼 수 있습니다.
      최소비용신장트리

# 참고자료

출처: https://hongcoding.tistory.com/78
출처: https://gmlwjd9405.github.io/2018/08/13/data-structure-graph.html
출처: https://kingpodo.tistory.com/49

← 트리 (Tree) →