그래프 개념

그래프의 정의를 하나의 문장을 딱 내리기에는 애매하니, 제 성격상 그냥 트리에서 좀 더 발전한 자료구조라고만 하겠습니다.

어차피, 정의를 달달 외우고 다니는 것보다, 실제 특징들을 제대로 설명할 수 있는 게 더 중요하니깐요.

바로 아래 내용들을 보면서 어떤 개념들을 가지고 있는지 확인해봅시다.

방향

그래프에 있는 노드간 간선(edge)들은 방향을 가질 수도, 가지지 않을 수도 있습니다.

(출처 : math insight)

위와 같이 간선들이 방향을 가지는 그래프는 directed graph라고 합니다.

(출처 : math insight)

그에 반해, 위와 같이 간선들이 방향이 없는 그래프는 undirected graph라고 합니다.

그래서 사실, 트리도 항상 위에서 아래로 가는 방향성을 가지므로 directed하다고 할 수 있습니다.

하지만, 어차피 트리는 아래로 가는 방향밖에 없기 때문에 간선의 방향 표시를 생략하는 경우가 대다수입니다.

directed graph에서는 self edge라고 해서, 간선이 자기 자신을 가리키는 경우도 있습니다.(loop라고도 하는 것 같습니다.)

(출처 : ycpcs.github.io)

순환

그래프에서는 순환(cycle)이라는 개념이 있는데 노드간 간선으로 인해 하나의 cycle을 만들 수 있으면 cyclic graph, 만들 수 없다면 acyclic graph라고 합니다.

(출처 : study.com)

위 그래프에서는 노드 B-C-E-D에서 cycle을 형성하므로 cyclic graph라고 할 수 있습니다.

(출처 : study.com)

그에 반해 위 그래프는 cycle이 없으므로 acyclic graph입니다.

얼핏 보면 노드 B-C-E-D가 cycle을 형성하는 것처럼 보이지만, 간선의 방향을 잘 보시면 B에서 뻗어나간 간선들이 다시 B로 돌아오는 케이스가 없습니다.

위에 예시로 붙여넣은 cyclic graph는 B에서 출발하여 C → E → D 경로를 거쳐 다시 D에서 B로 오기 때문에 cyclic graph입니다.

그러나 acyclic graph의 예시 이미지는 B에서 출발하여 C와 D와 E로 가고, C와 D는 무조건 E, E는 무조건 F로만 가므로 다시 B로 돌아오지 않으니, cyclic graph라고 할 수 없습니다.

따라서, cyclic graph인지 판별할 때는 간선의 방향도 유심히 살펴보아야 합니다.

여기서, 하나 더 첨언하자면 트리는 부모-자식 관계만 성립하기에 절대 사이클이 생길 일이 없습니다. 따라서, acyclic graph의 한 종류라고 할 수 있을 것 같습니다.

노드간 연결 관계 표현 방법

그래프의 노드간 연결 관계를 표현하는 방법에는 adjacency matrix, adjacency list가 있습니다.

adjacency matrix는 노드 간의 연결 관계를 2차원 배열을, adjacency list는 링크드리스트를 이용해 표현하는 방법입니다.

Adjacency Matrix

위와 같은 그래프가 있을 때, 이 그래프의 노드간 연결 관계를 2차원 배열을 이용하여 표현하는 방법입니다.

2차원 배열 요소들에 노드가 서로 연결되어 있으면 1(true), 연결되어 있지 않다면 0(false)로 값을 넣어줍니다.

위 그래프의 adjacecny matrix는 아래와 같습니다.

	1	2	3	4
1	0	1	1	1
2	1	0	0	0
3	1	0	0	1
4	1	0	1	0

여기서 중요한 점은 adjacency은 인접을 뜻합니다.

2와 3은 서로 1을 거치면 연결되어 있다고 볼 수 있지만, connection matrix가 아닌 adjacency matrix이므로 간선 하나를 통해서만 연결되어 있을 때만 1로 표시하고, 아닌 경우에는 모두 0으로 표시합니다.

Adjacency List

adjacency list는 노드의 개수만큼 링크드리스트 배열을 만들어서, 각 노드에 해당하는 배열 방의 링크드리스트에 인접한 노드들을 추가하는 것입니다.

똑같이 위와 같은 그래프가 있을 때, 이를 adjacency list로 표현하면 아래와 같습니다.

이렇게 노드별로 각 배열 방이 있고, 이 배열은 링크드리스트 배열입니다.

각 배열 방은 링크드리스트이므로 해당 노드와 인접해있는 노드들을 모두 링크드리스트에 추가해줍니다.

1은 2, 3, 4와 인접해있으므로 1의 링크드리스트에는 2, 3, 4가 들어가있고,

2는 1과 인접해있으므로 2의 링크드리스트에는 1만 들어가있습니다.

여기서 특징 하나는, 모든 배열 방(링크드리스트)에 들어가 있는 요소의 갯수는 그래프의 간선 갯수의 2배라는 것입니다.(그래프의 간선 갯수를 m이라 하면, 링크드리스트에 들어간 모든 요소의 갯수는 2m)

이 이유는 그래프 상에서는 1과 2를 연결하는 간선을 표현할 때 하나만 이용하지만, 실제 링크드리스트에 추가할 때는 1의 링크드리스트에 2를 넣고, 2의 링크드리스트의 1을 넣기에 2번씩 들어가기 때문입니다.