[자료구조] 그래프

그래프(Graph)란, 정점(노드)와 정점(노드)를 연결하는 간선을 하나로 모아놓은 자료구조이다.

1. 특징

• 구성

  • 정점(Vertex OR Node)과 간선(Edge)로 이루어짐
  • G = (V, E)

• 종류

  • 방향 있는 그래프
  • 방향 없는 그래프

• 루프

• 가중치 : 가중치가 없는 것은 1

2. 표현법

• 인접 행렬

  • A[i][j] = 1 인 경우, i -> j 의 간선이 있음을 의미
  • 장점) 접근이 쉬움
  • 단점) 공간복잡도가 높음(V^2)

• 인접 리스트

  • A[i] : i와 연결된 모든 정점이 포함되어 있음
  • 장점) 공간복잡도가 낮음(E)
  • 사용법) C++ vector, Python list
  • 주의) 가중치가 있는 경우, A[1] - (2, 2) (5, 7) 과 같이 저장

3. 이분 그래프

이분 그래프란, 인접한 정점끼리 서로 다른 색으로 칠해서 모든 정점을 두가지 색으로만 칠할 수 있는 그래프이다.

• 확인 방법
  • BFS, DFS 탐색을 이용하여 인접한 정점이 모드 다른 색인 경우 이분 그래프
  • 단, 연결 그래프와 비연결 그래프를 모두 고려해야한다.