그래프

그래프

1. 자료구조 개념:

• 노드(vertex)와 간선(edge)을 이용한 비선형 데이터 구조
• 데이터 간의 관계를 표현하는 데 사용
  • 데이터 노드: 노드 간의 관계나 흐름을 간선으로 표현
  • 간선은 방향이 있을 수도 없을 수도 있다.
  • 흐름에서 정도 표현이 필요하면 가중치라는 개념 추가
• 특징 및 종류:
  • 흐름을 표현하는 방향성: 간선은 방향을 가질수도 있고 없을 수도 있다.
    • 방향 그래프(방향있는 간선 포함) / 무방향 그래프(방향이 없는 간선)
  • 흐름의 정도를 표현하는 가중치: 가중치 그래프
  • 시작과 끝의 연결 여부를 보는 순환:
    • 순환: 특정 노드에서 시작해 간선을 따라 다시 돌아오는 경로가 있는 것
    • 순환 그래프(순환 존재) / 비순환 그래프(순환 미존재)

2. 해당 자료구조를 활용하는 분야:

3. 자료구조의 시간 복잡도:

   • 인접 행렬: O(1)
   • 인접 리스트: O(N)

4. 상세 내용:

   • 인접 행렬 그래프 표현
     • 2차원 배열 활용
     • 배열의 인덱스 => 노드
     • 배열의 값 => 가중치
     • 인덱스 세로 방향 => 출발 노드
     • 가로 방향 => 도착 노드
     • 단점:
       • 인접 행렬로 희소 그래프를 표현할 경우(희소 그래프 : 노드 수에 비해 간선 수가 매우 적은 그래프)
         • 인접 행렬은 크기가 고정되어 있으므로 최악의 경우 고려해야한다. 간선수가 적어도 N x N 크기의 인접 행렬 공간을 확보해야한다.
       • 노드들의 값의 차이가 매우 큰 그래프를 표현하는 경우
     • 장점:
       • 간선의 정보를 확인할 때의 시간 복잡도 O(1); 인덱스 임의 접근이기 떄문
   • 인접 리스트 그래프 표현
     • 값(v), 가중치(w), 다음 노드(next)를 묶어 관리
     1. 노드 개수만큼 배열을 준비
     2. 배열의 인덱스는 각 시작 노드의미, 배열의 값에는 다음 노드를 연결한다.
     • 단점:
       • 특정 노드에 연결된 노드 개수가 많을수록 연결한 리스트의 길이만큼 탐색해야한다.
     • 장점:
       • 실제 연결된 노드에 대해서만 노드의 값을 노드에 담아 연결 => 메모리 효율

5. 그래프 탐색

   1. 깊이 우선 탐색: 더 이상 탐색할 노드가 없을 때 까지 진행, 더 이상 탐색할 노드가 없으면 최근에 방문했던 노드로 되돌아간 다음 가지 않은 노드를 방문
      • 시작 노드를 정하고, 스택에 시작 노드를 푸쉬
      • 스택에 있는 노드는 아직 방문 예정인 노드
      1. 스택이 비었는지 확인, 스택이 비었다는 건 방문할 수 있는 모든 노드를 방문했다는 의미 => 탐색 종료
      2. 스택에서 노드를 팝, 팝한 원소는 최근에 스택에 푸시한 노드
      3. 팝한 노드의 방문 여부 확인, 이미 방문한 노드라면 별도의 처리가 없다. 아직 방문하지 않았다면 노드를 방문 처리함.
      4. 방문한 노드와 인접한 모든 노드 확인, 그 중에서 아직 방문하지 않은 노드를 스택에 푸시, 스택은 LIFO 구조이므로 방문 순서를 오름차순으로 고려한다면 역순으로 노드를 푸시해야한다.
      • 탐색할 노드가 없을 떄까지 간선을 타고 내려갈 수 있어야 한다.
      • 가장 최근에 방문한 노드를 알아야 한다.
      • 이미 방문한 노드인지 확인할 수 있어야한다.
      • 배열과 재귀로 탐색
      • 가장 깊은 곳을 우선하여 탐색하고, 더 이상 탐색할 수 없으면 백트래킹 하여 최근 방문 노드부터 다시 탐색 => 모든 가능한 해 찾는 백트래킹 알고리즘 / 그래프의 사이클 감지에 활용
   2. 너비 우선 탐색: 현재 위치에서 거리가 가장 가까운 노드부터 모두 방문하고 다음 노드로 넘어간다. 그 노드에서 또 다시 가장 가까운 노드부터 모두 방문
      • 거리 === 시작 노드와 목표 노드까지의 차수
      • 시작 노드를 정하고, 큐에 시작 노드를 푸시
      • 큐에 있는 노드는 이미 방문 처리 한 노드, 그 노드와 인접한 노드는 아직 탐색전
      1. 큐가 비었는지 확인, 비었따면 방문할 수 있는 모든 노드를 방문했다는 의미 => 탐색 종료
      2. 큐에서 노드 팝
      3. 팝한 노드와 인접한 모든 노드를 확인하고 그 중 아직 방문하지 않은 노드를 큐에 푸시하여 방문 처리
      • 현재 방문한 노드와 직접 연결된 모든 노드를 방문할 수 있어야한다.
      • 이미 방문한 노드인지 확인할 수 있어야한다.
      • 시작 노드로부터 직접 간선으로 연결된 모든 노드를 먼저 바문하기 떄문에 최단 경로임을 보장한다.

6. 그래프 최단 경로 구하기

   • 최단 경로는 그래프의 종류에 따라 진의가 다르게 해석 될 수 있다.
   • 가중치 유무에 따라 다름;
     • 가중치 없다면, 간선 개수가 가장 적은 경로가 최단 경로
     • 가중치 있다면, 간성의 가중치의 총합이 최소가 되는 경로
   1. 다익스트라 알고리즘
   2. 밸만-포드 알고리즘