11 ~ 12주차 - 그래프 알고리즘 및 최소신장트리

그래프

정의

• 현상이나 사물을 정점과 간선으로 표현한 것

\(Graph G = (V, E)\)‎‎

​ V : 정점 집합

​ E: 간선 집합

• 두 정점이 간선으로 연결되어 있으면 인접하다고 함

  ​ 간선은 두 정점의 관계를 나타냄

• 응용 예시

• 그래프	정점	간선
  통신	전화, 컴퓨터	광케이블
  회로	프로세서	선

종류

인접 행렬

• N x N의 행렬로 표현되는 그래프

  ​ (N은 정점의 총 갯수)

  • 원소 (i,j ) = 1 : 정점 i와 j 사이에 간선이 존재함
  • 원소 (i,j ) = 0 : 정점 i와 j 사이에 간선이 없음
• 유향 그래프의 경우
  • 원소(i, j)는 정점 i로부터 정점 j로 연결되는 간선이 있는지를 나타냄
• 가중치 있는 그래프의 경우
  • 원소(i, j)는 1대신 가중치를 가짐

인접 리스트

• N개의 연결 리스트로 표현 하는것
• i번째 리스트는 정점 i에 인접한 정점들을 리스트로 연결함
• 가중치 있는 그래프의 경우
  • 리스트에 가중치도 보관함

인접 배열

• N개의 연결 배열로 표현하는 것
• i번째 배열은 정점 i에 인접한 정점들을 집합함
• 가중치 있는 그래프의 경우
  • 인접 리스트와 동일하게 리스트에 가중치도 보관함

그래프에서 모든 정점 방문하기

방법

• BFS(너비 우선 탐색)
• DFS(깊이 우선 탐색)

최소 신장 트리

• 조건
  • 무향 연결 그래프
    • 연결 그래프: 모든 정점 간에 경로가 존재하는 그래프
• 트리
  • 사이클이 없는 연결 그래프
  • n개의 정점을 가진 트리는 항상 n-1개의 간선을 가짐
• 그래프 G의 신장 트리
  • G의 정점들과 간선들로만 구성된 트리
• G의 최소 신장 트리
  • G의 신장 트리 중, 간선의 합이 최소인 신장 트리

종류

• 크루스칼 알고리즘

  • 원리:

    • 모든 간선을 가중치 기준으로 오름차순으로 정렬하고, 모든 정점이 연결될때까지 연결하는 방식

  • 수행 방법:

    1. 1개의 정점만으로 이루어진 n개의 집합을 초기화 시킴

    2. 간선 집합 Q(=E) 가중치를 기준으로 오름차순으로 정렬 함

    3. 정렬된 간선 중 가중치가 낮은 간선부터 선택하여 간선의 정점을 연결 및 Q에서 최소비용 간선(u, v)를 제거함

       이때, 정점 u와 v가 다른 집합에 속하면 두 집합을 하나로 합쳐야 함

    4. 모든 정점이 연결될때까지 2의 과정을 반복함(while 신장트리 T의 간선 수 < n-1)

    단, 이때 이미 연결된 정점간의 간선을 선택해서는 안됨(사이클 생성)

  • 시간 복잡도

    • \[O(ElogV)\]

• 프림 알고리즘

  • 원리:

    • 특정 정점에서 갈 수 있는 연결 안된 정점으로 확장하는 방식

  • 시간 복잡도 :

    ​ 전체 간선 BFS 방문 시간 \(O(E + V)\)

    ​ 힙 사용 최소 간선 구하기 \(O(log V)\)

    ​ $$ O(E + V) x O(log V)

    ​ = O((E + V) log V)

    ​ = O(ElogV)$$

  • Prim(G, r) G: (V, E)로 이뤄진 그래프, r: 시작 정점

  • 수행 방법:

    1. 공집합 S를 생성함

    2. 정점 r을 방문했다고 표시하고, 집합 S에 포함시킴
    3. S가 V가 아닐때, S에서 V-S를 연결하는 간선 중 최소 길이 간선 (x,y)를 찾아, 정점 y를 표시하고 집합 S에 포함 시킴