4-1. 그래프와 BFS

그래프

• 정점(Node, Vertex)과 간선(Edge)으로 이루어진 자료구조이다. 이때 간선은 정점간의 관계를 나타낸다.
  • G = (V, E)로 나타낸다.
• 자세한 내용은 생략한다.

그래프의 표현

인접 행렬(Adjacency-matrix)

• 정점의 개수를 V라고 했을 때 VxV크기의 이차원 배열을 이용한다. a[i][j]는 i에서 j로 가는 간선의 존재 유무를 나타낸다.(0: 有, 1:無) 가중치를 표현하고 싶다면 0일때 간선이 없음, 1이상의 수일때 가중치로 표현할 수 있다.

인접 리스트(Adjacency-list)

• 리스트를 이용해서 구현한다. A[i]=i와 연결된 정점을 리스트로 표현한다.
• 리스트는 크기를 동적으로 변경할 수 있어야 하기 때문에, 일반적인 배열은 사용할 수 없다.
• 가중치를 표현할때는 리스트 내에 정점과 가중치의 쌍으로 표현한다.

공간복잡도

• 인접 행렬의 공간복잡도는 O(V^2)이다.
  • 인접 행렬로 구현하는 경우 공간복잡도가 더 들기는 하지만, 간선을 찾는데 시간복잡도가 O(1)이다. 항상 상수시간이 된다.
• 인접 리스트의 공간복잡도는 O(E)이다.
  • 인접 리스트로 구현하는 경우 간선을 찾는데 시간복잡도가 더 들기는 하지만, 공간복잡도가 인접 행렬에 비해 훨씬 적다.

간선 리스트

• 배열을 이용해서 구현할 수 있으며, 간선을 모두 저장한다. 그 후 각 간선의 앞 정점을 기준으로 갯수를 센다. 이를 통해서 간선의 갯수를 구할 수 있다.

13023 ABCDE, 백준 온라인 저지

• 총 N명의 친구 관계가 주어졌을 때, 주어진 두 사람이 서로 친구인지 구하는 문제이다.
• A->B->C->D->E
• A->B, C->D는 단순 간선이므로, 간선 리스트를 이용해서 찾을 수 있다.
• B->C는 인접 행렬로 찾을 수 있다.
• D->E는 인접 리스트로 찾을 수 있다.