Graph

정점과 간선으로 이루어진 자료구조 (cf. 트리는 사이클이 없는 그래프이다)

 

정점(V) : 노드라고도 하며, 데이터가 저장된다.

간선(E) : 링크라고도 하며, 노드 간의 관계를 나타낸다.

차수(D) : 무방향 그래프에서 하나의 정점에 인접한 정점의 수

 

• 구현 방법
  • 인접 행렬
    • 그래프의 노드를 2차원 배열로 만든 것
    • 노드에 다른 노드들이 인접 정점이라면 1
    • 아니면 0
    • 장점
      • 구현이 편리하다
      • 연결 정보를 조회할 때 O(1)의 시간이 걸린다
    • 단점
      • 정보를 입력할 때 O(n^2)의 시간이 걸린다.
      • 필요이상의 공간이 낭비된다.
  • 인접 리스트
    • 그래프의 노드들을 리스트로 표현한 것
    • 장점
      • 연결 정보를 탐색할 때 O(N(E))의 시간이 걸린다.
      • 공간 낭비가 적다. O(E+V)
    • 단점
      • 연결 정보를 조회할 때 시간이 오래 걸림
      • 구현이 어려움
• 종류
  • 무방향 그래프 : 간선에 방향성이 없음
  • 방향 그래프 : 간선에 방향성이 존재함
  • 가중치 그래프 : 간선에 가중치가 존재함.
• 탐색
  • DFS(깊이 우선 탐색)
    • 갈 수 있는 만큼 최대한 깊이 가고, 더 이상 갈 곳이 없다면 이전 정점으로 돌아오는 방식
    • 재귀 또는 스택을 사용하여 구현이 가능
  • BFS(너비 우선 탐색)
    • 시작 정점부터 인접한 모든 정점을 방문하면서 나아가는 방식
    • 큐를 사용해서 구현 가능
• 최소신장트리
  • 신장트리
    • 연결 그래프의 부분 그래프로서 모든 정점과 간선의 부분집합으로 구성되는 트리.
    • 모든 노드는 적어도 하나의 간선에 연결되어 있어야 한다.
    • DFS 또는 BFS로 구현이 가능하다.
    • 하나가 아니라 다양할 수 있다.
  • 가중치의 합이 최소가 되는 신장트리
  • 크루스칼 알고리즘 또는 프림 알고리즘으로 찾을 수 있다.
• 크루스칼 알고리즘
  • Greedy Algorithm 이다
  •  간선을 하나씩 추가하여 최종지점이 되면 최소신장트리가 된다.
    • 모든 간선을 오름차순으로 정렬한다.
    • 최소 가중치의 간선을 선택한다.
    • 남은 간선들 중에 가장 가중치가 작은 간선을 찾은 후, 이 간선을 추가해도 사이클이 생기지 않을경우, 간선을 선택한다.
    • 간선의 갯수가 (V-1)이 될때까지 반복한다.
• 프림 알고리즘
  • Greedy Algorithm 이다
    • 정점과 간선을 하나씩 선택하여 트리를 구성하되, 가중치 합이 가장 적게 증하도록 하는 방법
      • 트리의 시작점을 정한다.
      • 나머지 정점에서 시작점과 연결된 최소 가중치의 간선과 그에 따른 정점을 트리에 추가한다.
      • 이미 추가된 정점을 제외한 외부의 나머지 정점 중에서 트리와 가장 비용이 적게는 정점을 연결한다.
      • 간선의 갯수가 (V-1)이 될때까지 반복한다.