[파이썬(python) 자료구조] 그래프 (Graph)

그래프

: 연결되어 있는 객체 간의 관계를 표현하는 비선형 자료구조

가장 일반적인 자료구조의 형태로, tree도 그래프의 특수한 경우이다. 예를 들면, 전기회로의 소자 간 연결 상태나 혹은 운영체제의 프로세스와 자원 관계 또한 그래프로 표현이 가능하다.

 

그래프의 정의

그래프 G는 (V,E)로 표시하며, 이때 V는 정점 vertex의 집합을 E는 간선 edge의 집합을 의미함.

 

(그림 A)

- vertex (정점)

: 여러 가지 특성을 가질 수 있는 객체를 의미함. 노드(node)라고도 함.

- edge (간선)

: 정점들 간의 관계를 의미. link라고도 함.

 

그래프의 종류

   1) 무향 그래프 (undirected graph)

      : 무향 에지는 양방향의 의미임. 예컨대 조합(combination)처럼 (A,B) = (B,A)로 순서에 의미가 없다는 것.

   2) 방향 그래프 (directed graph)

      : 에지를 통해서 한쪽 방향으로만 갈 수 있다는 특징. 즉, <A.B> ≠ <B,A> 라는 특성을 보임.

(그림 B)

cf.) 가중치 그래프: 각 간선에 가중치를 부여한 형태의 그래프. 예를 들면 edge에 비용을 부과하는 형식으로 가중치가 부과될 수 있음.

 

그래프 관련 특성

인접 정점

: 어떤 정점에서 에지에 의해 직접 연결된 정점. 위의 그림 A를 참고했을 때, 정점4의 인접 정점은 정점 3이다.

 

그래프 차수

1) 무향 그래프

하나의 정점에 연결된 다른 정점의 수 (인접 정점의 수)

그림 A에서 정점 4의 차수는 1, 정점 3의 차수는 3.

무향 그래프 정점들의 모든 차수의 합은 에지 개수의 2배이다.

 

2) 유향 그래프

유향 그래프에서의 차수는 진입 차수와 진출 차수 두 가지로 구분된다. 진입 차수(in-degree)는 외부에서 오는 에지의 수이며, 진출 차수(out-degree)는 외부로 향하는 에지의 수이다.

그림 B에서의 유향 그래프에서 정점 B의 진입 차수는 1이고, 진출 차수는 2이다.

방향 그래프의 모든 진입(또는 진출) 차수의 합은 에지의 수와 같다. 즉, 진입 차수의 합 == 진출 차수의 합 == 그래프 내 모든 에지의 수라고 할 수 있다.

 

그래프의 경로

: 그래프의 경로라 함은, 그래프 내의 정점 s로부터 정점 t까지의 경로를 의미하며, 두 정점 간의 경로 상의 모든 정점의 나열을 통해 표현된다.

ex. s→v1→v2→...→vk→t

 

이때 나열된 정점들 간에 반드시 에지 (s,v1), (v1, v2), ..., (vk,t)가 존재한다. 여기서는 무향 그래프의 표현 방식을 따랐지만 이는 유향 그래프의 경우에도 동일하게 적용이 된다.

해당 경로의 길이는 경로를 구성하는 에지의 수로 정의되며, 사이클(순환)은 경로의 시작 정점과 끝 정점이 동일한 경로를 의미한다. 여기서의 경로는 경로 중에서 반복되는 정점 및 에지가 없는 경로인 단순 경로로 한정하도록 한다.

 

그래프의 연결성 (connectivity)

연결 그래프 (connected graph)

 무향 그래프 G에 있는 모든 정점 쌍에 대하여 경로가 존재할 경우, 무향 그래프 G는 연결 그래프이다. 여기서 주의할 점은, 모든 정점 쌍에 대하여 경로가 존재한다는 것은 임의의 두 정점 간에 edge가 존재한다는 걸 의미하는 게 아니다. 하나의 정점에서 다른 정점으로 갈 수 있느냐 없느냐의 문제이다. 그래프가 네트워크를 의미하는 경우 그래프의 연결성은 네트워크의 reliability와 밀접한 연관이 있는 개념이라고 할 수 있다.

 

트리(tree)

 그래프의 특수한 형태로서, 무순환 연결 그래프이다 (connected acyclic graph). 시작 정점에서 다시 시작 정점으로 돌아올 때 이미 방문한 엣지를 무조건 다시 방문하지 않고서는 불가능한 구조이다.

연결성의 입장에서는 최소로 연결이 되어있다. 최소로 연결되어 있다는 것은 하나의 edge만 삭제해도 연결그래프가 아니게 된다는 의미이다.

 

완전 그래프 (complete graph)

 모든 정점이 서로 연결되어 있는 그래프.

n개의 정점을 가지는 완전 그래프의 에지 개수

→ (무향): n(n-1)/2, (유향): n(n-1)

 

그래프의 표현 방법

인접 행렬

정점의 개수를 k라고 했을 때, kXk matrix를 정의함. 각 row는 해당 정점의 연결 상태를 의미함. 

공간 복잡도는 O(n^2)으로 희소 그래프인 경우 매우 비효율적이다.

 

[pseudo code]

for i=1~n_row
	for j=1~n_row
    	if (edge exists) A[i][j] = 1
        else A[i][j] = 0

 

자가 루프가 없는 단순 그래프의 경우 인접 행렬의 대각선 성분은 모두 0이 된다. 무향 그래프의 인접 행렬은 대칭행렬이다.

 

그래프 인접 행렬이 대칭행렬이라는 것은, upper or lower triangular matrix만 사용하여 표현이 가능하다는 것을 의미하고 이 경우 메모리 사용량을 save할 수 있다.

보통 0,1값을 갖는 행렬로 표현하지만 가중치 그래프의 경우 행렬의 성분에 가중치를 입력하는 형식으로 표현이 가능하다.

 

if ((i,j) exists)
	A[i][j] = W_ij
else if (i==j) A[i][j] = 0
else A[i][j] = infinity // i,j 간 에지가 존재하지 않는 경우

 

인접 리스트

- 각 정점에 인접한 정점들을 연결 리스트로 표현한다. 정점이 n개인 그래프라면 n개의 연결리스트로 구성한다. 각 연결리스트마다 포인터 변수가 리스트의 처음 노드를 가리키며 연결리스트가 없는 경우, 즉 차수가 0인 경우 포인터 변수의 값은 null이 된다.

- 공간복잡도: $O(n+m)$

정점의 개수가 n, 에지의 개수가 m이라고 가정하자.

                                                                             

1) 무향그래프: n+2m

 n개의 포인터 변수가 있어야 하고, 2m개의 일반 노드가 필요하다.

2m개의 일반 노드가 필요한 이유: 앞서 무향 그래프는 "양방향"의 의미라고 하였다. 따라서 정점0과 정점1간의 에지를 표현하고자 할 때, 정점0을 의미하는 포인터 변수에서 정점0→정점1 을 표현함과 동시에 정점1을 의미하는 포인터 변수에서 정점1→정점0을 표현해주어야 한다.                                                                                   

 

2) 방향그래프: n+m

 n개의 포인터 변수와 m개의 일반 노드.

m개의 일반 노드가 필요한 이유: 일방향이기 때문에 하나의 에지로 연결된 두 정점에 대해 중복으로 표기하는 것이 아니다. 따라서, 시작 정점에서 끝 정점만 연결해주면 되므로 에지 하나당 하나의 노드만 필요하다.

만약 그래프 G가 완전 그래프이고 이를 인접 리스트로 표현하고자 한다면, 이는 $O(n^2)$의 비용이 들 것이다. (인접 리스트여도 완전 그래프를 표현하고자 한다면 인접 행렬과 동일한 비용이 든다는 것)

 

- 인접리스트의 구현 in Python

파이썬은 포인터가 따로 존재하지 않으므로, 연결리스트를 구현하기 까다롭다. 따라서 인접 리스트를 출발 노드를 키로, 도착 노드를 값으로 표현하는 딕셔너리 형태로 표현한다. 도착 노드의 경우에는 여러 개의 노드가 가능하므로 값은 리스트 형태로 표현한다.

 

graph = { 0: [1], 
	  1: [0,2], 
          2: [] } # 인접 리스트 그림 (c)를 파이썬으로 표현한 형태