[Algorithm] 그래프(Graph)

이번 글은 그래프에 관한 내용입니다. 그래프는 연결되어 있는 객체 간의 관계를 표현하는 자료구조입니다. 실생활에서 자주 볼 수 있는 그래프는 지하철 노선도, 항공노선도, 전기회로 등이 있습니다. 항공노선도는 도시들이 항공편으로 어떻게 연결되어 있는지를 확인할 수 있고 전기회로는 각 소자들의 연결 관계를 확인할 수 있습니다. 그래프는 다양한 객체가 서로 복잡하게 연결된 구조를 표현할 수 있습니다. 

 

그래프 이론

그래프와 관련된 다양한 문제를 연구하는 학문 분야로 수학자인 오일러가 최초로 창안하였습니다. 쾨니히스베르크에 7개의 다리가 있었는데 사람들은 같은 다리를 두 번 이상 건너지 않으면서 모두 건널 수 있을까에 대한 물음을 가지고 있었습니다. 1736년 오일러는 7개의 다리에는 그러한 경로가 존재하지 않는다는 사실에 대한 수학적 증명을 제시했습니다. 이때 오일러는 다리들을 하나의 그래프로, 링크에 의해 연결되는 노드들의 집합으로 파악하였습니다. 

 

모든 다리를 한 번만 건너서 처음 출발했던 장소로 돌아오는 문제를 오일러 문제라고 하고 오일러 정리는 모든 정점에 연결된 간선의 수가 짝수일 때만 오일러 경로 존재한다는 것을 말합니다. 

 

그래프 정의

그래프 G는 정점과 간선의 집합으로 G = (V,E)로 표시합니다. 정점(노드)은 객체를 의미하고 V(G), 간선(링크)라고 정점들 간의 관계를 의미하고 E(G)라고 표현합니다. 동일한 그래프인지 확인할 때 시각적인 모습을 통해 동일한 그림인지 보는 것이 아닌 모든 정점 사이의 관계가 동일한지를 보는 것입니다. 

 

그래프 종류

• 무방향그래프: 간선에 방향이 존재하지 않는 그래프로 (A, B) = (B, A)로 표현
• 방향 그래프: 간선에 방향이 존재하는 그래프로  <A, B> != <B, A>로 표현
• 가중치 그래프: 간선에 비용이나 가중치가 할당된 그래프
  • 간선이 두 정점 간 연결 유무 뿐만 아니라 연결 강도도 표현함으로써 복잡한 관계도 표현 가능
  • 도시 간 도로의 길이, 이동 시간, 통신망 사용 등을 연결 강도 즉, 가중치를 주어 표현 가능
• 부분 그래프: V(G), E(G)의 부분집합으로 이루어진 그래프 

 

그래프 용어 

• 인접 정점: 간선에 의해 직접 연결된 정점으로 아래 그림에서 B의 인접 정점은 A, C를 나타냄.

• 차수(degree): 정점에 연결된 간선의 수
  • 무방향 그래프일 때와 방향 그래프일 때 차수를 계산하는 방법은 다름.
  • 무방향 그래프: 하나의 간선이 2개의 정점에 인접해 있기 때문에 차수의 합은 간선 수의 2배입니다.
  • 방향 그래프: 외부에서 오는 간선의 수인 진입 차수, 정점에서 외부로 향하는 간선의 수인 진출 차수 2가지 차수가 존재하는데 진입 기준으로 보았을 때나 진출 기준으로 보았을 때나 동일하게 모든 차수의 합은 간선의 수와 동일
• 경로: 간선을 따라갈 수 있는 길
  • 무방향 그래프: 정점 s로부터 정점 e까지의 경로 
  • 경로의 길이=경로를 구성하는데 사용된 간선의 수
  • 단순 경로: 경로 중에서 반복되는 간선이 없는 경로
  • 사이클: 단순 경로와 시작 정점과 종료 정점이 동일한 경로 
• 연결 그래프(Connected Graph): 모든 정점들 사이에 경로가 존재하는 그래프
  • 모든 정점들 사이에 간선이 존재하진 않아도 되고 경로상에 존재해야 함.
• 트리: 연결 그래프에서 사이클이 없으면 그래프의 임의의 두 정점을 연결하는 경로는 오직 하나뿐인 그래프(사이클이 없는 연결 그래프)
  • 만약 2개의 경로가 존재한다면 이들에 의해 사이클이 형성
• 완전 그래프(Complete graph): 모든 정점 간에 간선이 존재하는 그래프

 

그래프 표현

• 인접 행렬(adjacency matrix)을 이용한 표현
  • 정점의 개수가 n이라면 n*n행렬 M이 필요 
  • 간선 (i, j)가 있으면 M [i, j] =1 또는 True, 그렇지 않으면 0  또는 FALSE
  • 가중치 그래프일 때는 간선이 있는 성분에 가중치 값으로 표시하고 자신에서 출발하고 자신으로 들어오는 간선은 0 또는 None으로 표현
  • 무방향 그래프에서 인접 행렬은 대칭 행렬이 되고 배열의 상위 삼각이나 하위 삼각만 저장하여 메모리를 절약할 수 있음. (방향 그래프일 때는 대칭 행렬이 아님)
  • 시간 복잡도: 
• 인접 리스트를 이용한 표현
  • 인접 리스트는 각 정점과 연결된 인접 정점들을 각각의 리스트로 표현한 것으로 각 정점은 인접 리스트를 이용해 자신과 간선으로 직접 연결된 인접 정점을 관리할 수 있습니다. 리스트는 연결 구조를 이용할 수도 있고 배열구조를 이용할 수도 있습니다.
  • 연결구조를 이용하는 경우 
    • U는 V, W와 연결되어 있기 때문에 
    • V는 U, W, X와 연결되어 있다.
    • 방향 그래프: 인접 리스트의 노드 수 = 간선 수
    • 무방향 그래프: 연결 리스트에 실제로 만들어지는 노드 수 = 간선 수의 2배

 

자료구조 선택

정점과 간선이 어떻게 연결되어있는지에 따라 인접 행렬이나 인접 리스트를 선택하는 것이 시간복잡도나 공간복잡도를 줄이기에 좋습니다. 정점의 수보다 간선의 수가 많은 그래프일 경우 인접행렬을 사용하는 것이 좋고 정점의 수가 간선의 수보다 적은 그래프의 경우 인접리스트를 사용하는 것이 좋습니다.