• 정점(Vertex) + 간선(Edge)로 구성
  • 루트와 부모-자식 관계가 없음

  • 방향, 연결, 순환의 유무에 따라 그래프 종류가 다름

  • 용어
    • 정점 = 노드
    • 간선 = 링크, 선분
    • 인접 : 직접 연결되어 있는 노드
    • 정점의 차수 : 정점에 연결되어 있는 간선 수
      • 무방향 그래프 : 존재하는 정점의 모든 차수의 합 = 그래프 간선 수 X 2
      • 방향 그래프 : 진입 차수(내차수)와 진출 차수(외차수) 존재, 정점의 진입차수 or 진출차수의 합 = 그래프 간선 수(내차수 + 외차수)

그래프 종류

  1. 무방향 그래프 : 간선에 방향이 없는 그래프 (양방향 통행가능)
    • 정점 A 와 정점 B를 연결하는 간선 (A,B) = (B,A)
  2. 방향 그래프 : 간선에 방향이 있는 그래프
    • 정점 A → 정점 B로 갈 수 있는 간선 <A, B>
  3. 연결 그래프 : 모든 정점 사이에 경로가 있는 그래프

  4. 비연결 그래프 : 특정 정점 사이에 경로가 없는 그래프

  5. 순환 그래프(사이클) : 시작 정점와 종료 정점가 동일한 경우

  6. 비순환 그래프 : 사이클이 없는 그래프
    ex) 트리

  7. 완전 그래프 : 모든 정점가 서로 연결되어 있는 그래프
  8. 가중치 그래프 : 간선에 가중치가 할당된 그래프

그래프 구현 방법

1. 인접 리스트 (연결리스트)

  • 정점의 갯수 만큼 헤드 노드를 생성
  • 인접한 정점을 포인트로 연결

2. 인접 행렬 (행렬)

  • 정점의 갯수가 n 일경우 n x n 행렬 생성
  • 행렬의 원소에 간선이 존재할 경우 1, 존재하지 않을 경우 0 입력

그래프 순회

1. 깊이 우선 탐색(DFS, Depth-First Search) : 시작 정점에서 출발하여 한 방향으로 갈 수 있는 깊이까지 먼저 탐색하는 방법

  • 후입선출(LIFO) : 스택 사용
  • 저장공간을 적게 사용함

2. 너비 우선 탐색(BFS, Breadth-First Search) : 시작 정점에서 가까운 정점을 먼저 탐색하는 방법

  • 선입선출(FIFO) : 큐 사용
  • 최단 경로의 길이를 구할 수 있음

3. 최소 비용 신장 트리 : 무방향 가중치 그래프에서 가중치 합이 최소인 신장트리

= 가장 적은 비용으로 모든 정점을 연결하는 방법(최단경로)

  • 신장 트리 : 모든 정점을 포함하는 트리

(1) Prim 알고리즘

  • 가중치가 가장 작은 간선을 선택해 나가면서 정점을 하나하나 연결해 나감

(2) Kruskal 알고리즘

  • 모든 간선의 가중치를 오름차순으로 정렬 한 후 작은 순서대로 선택해가며 n-1개를 선택하면 완성됨

4. 다익스트라 알고리즘 (BFS + 최단경로)

  • 매 탐색마다 해당 정점까지의 가중치 합을 최소값으로 갱신해 나감
  • 음이 아닌 가중치에서만 사용 가능