Graph 자료구조

 

 

그래프는 노드(Node, 또는 정점 -vertex- 라고도 부릅니다), 그리고 노드와 노드를 연결하는 간선(edge)으로 구성된 자료구조 입니다.

그래프는 무방향(undirected)일 수 있습니다. 이는 간선에 의해 연결된 2개의 노드가 대칭 일 수 있다는 의미입니다.

한편 방향성(directed)을 가질 수도 있는데, 이는 비대칭 관계를 의미합니다.

 

 

그래프 G = ( V, E )로 정의하는데, V( Vertex )는 그래프에 있는 정점들의 집합을 의미하고 E( Edge )는 정점을 연결하는 간선들의 집합을 의미합니다.

 

 

그래프 용어

 

• 정점 (Vertex) : 연결한 객체들을 의미
  
  
• 간선 (Edge) : 정점들을 연결하는 선
  
  
• 차수 (Degree) : 정점에 연결되어 있는 간선의 수, 방향 그래프에서 진입 / 진출 차수의 합
  
  
• 진입차수 (In-Degree) : 방향 그래프에서 정점을 머리로 하는 간선의 수, 정점으로 들어오는 간선
  
  
• 진출차수 (Out-Degree) : 방향 그래프에서 정점을 꼬리로 하는 건선의 수, 정점에서 나가는 간선
  
  
• 경로 (Path) : 정점 A에서 정점B까지 간선을 따라 갈 수 있는 길을 순서대로 나열한 것을 의미
  
  
• 사이클 (Cycle) : 경로의 시작 정점과 마지막 정점이 같은 경로를 의미
  
  
• 인접 정점 (adjacent vertex) : 간선에 의해 직접 연결된 정점

 

 

 

그래프는 아래의 그림처럼 방향이 있는 Directed Graph 와  방향이 없는 Undirected Graph 로 나뉩니다.

 

 

위의 사진처럼 화살표가 있는 그래프는 방향이 있는 그래프이고, 화살표가 없는 그래프는 서로가 서로를 연결하고 있는 무방향 그래프입니다.

 

 

 

 

 Cyclic Graph VS Acyclic Graph

 

 

그래프는 아래의 그림과 같이 노드들이 그래프 내부에 circle을 만드는 그래프가 있고 아닌 그래프가 있습니다.

하나이상의 circle이 있는 그래프를 Cyclic Graph라고 하고, circle이 하나도 없는 그래프를 Acyclic Graph라고 합니다.

 

 

 

Cyclic Graph는 노드1, 노드2, 노드4가 방향성을 이루면서 circle을 그리는 것을 확인할 수 있습니다.

반면에 Acyclic Graph는 노드4에서 노드2로 가는 방향이 없기 때문에 circle을 형성하지 않으므로 Acyclic Graph입니다.

 

 

 

 Graph를 표현하는 방법

 

Graph를 표현하는 방법에는 다음과 같은 두 가지 방법이 있습니다. 

 

 

1.  Adjacency Matrix (인접 행렬)

 

그래프를 표에다가 표현하는 방법입니다. 즉, 이차원 배열에 표현한다 라고 볼 수 있습니다.

서로 연결된 노드들이 있으면 1, 연결된 노드가 없으면 0 으로 이차원 배열을 채우는 것입니다.

 

이 이차원 배열로 표현된 표를 읽는 방법은 간단합니다.

먼저 표는 abj, 행과 열은 각각 [i]와 [j]라고 가정해보도록 하겠습니다.

즉, 노드 i에서 노드 j로 가는 간선이 있다는 말은 노드 j에서 노드 i로 가는 간선도 존재한다는 의미가 될 것입니다.

 

인접 행렬은 서로 연결되어 있으면 1이고 연결되어 있지 않으면 0 이라고 앞서 설명했듯이, abj[i]에 존재하는 노드 1과 abj[j]에 존재하는 노드 1은 자기 자신을 연결하고 있는 것은 아니기 때문에 0 이고, abj[i]에 존재하는 노드1과 abj[j]에 존재하는 노드2는 연결되어 있으므로 1 입니다.

주의해야 할 것은 노드 2와 노드 3은 노드1을 통해 간접적으로 연결되어 있지만 직접적으로 연결되어 있지 않기 때문에 0 입니다.

따라서 모든 노드들의 연결상태를 작성하면 위와 같은 표가 완성될 수 있습니다.

 

 

 

인접 행렬의 장점과 단점

 

• 장점
  
  인접 행렬의 장점은 구현이 쉽다는 점입니다.
  
  그리고, 노드 i와 노드 j가 연결되어 있는지 확인하고 싶을 때, adj[i][j]가 1인지 0인지만 확인하면 되기 때문에 O(1)이라는 시간 복잡도로 즉시 알 수 있습니다.
  
  
  
• 단점
  
  전체 노드의 개수를 V개, 간선의 개수를 E개라고 한다면 노드 i에 연결된 모든 노드들에 접근해보고 싶은 경우 adj[i][1]부터 adj[i][V]를 모두 확인해 보아야 하기 때문에 총 O(V)의 시간이 걸린다는 점입니다.
  
  즉, 어떤 노드에 인접한 노드들을 찾기 위해서는 모든 노드들을 전부 순회해야 한다는 것입니다.
  
  (이러한 단점을 보완할 수 있는 연결 관계 표현 방식이 인접 리스트 입니다.)

 

 

 

 

2. Adjacency List (인접 리스트) 

배열 방에다가 모든 노드를 넣고 각 배열방에 있는 해당 노드와 인접한 노드들을 Linked List로 나열하는 방법입니다.

 

 

 

 

 

위의 그림은 노드1, 노드2, 노드3, 노드4를 abj[1], abj[2], abj[3], abj[4]로 표현하여 각각 배열로 놓고 각 노드들과 인접한 노드들을 Linked List로 나열한 그림입니다.

 

인접 리스트는 그래프의 연결 관계를 vector의 배열로 나타내고, 인접 리스트는 adj[i]( vector의 배열이기 때문에, adj[i]는 vector가 됩니다 )를 다음과 같이 정의할 수 있습니다.

adj[i] : 노드 i에 연결된 노드들을 원소로 갖는 vector

 

노드1과 인접한 노드들은 노드2, 노드3, 노드4가 있으므로 Linked List로 나열하는데, 이 때, 순서는 상관이 없습니다. 다만 위의 그림은 보기좋게 하기 위해 오름차순으로 표현한 것입니다.

따라서 adj[1]의 노드 2와 노드3사이에 화살표가 있는 것을 노드 2와 노드 3사이에 간선이 있다는 의미가 아니라 단순히 vector에 노드 3이 노드2보다 나중에 push 되었기 때문이라고 이해하면 됩니다.

 

인접 리스트는 Adjacency Matrix (인접 행렬) 와 같이 직접적으로 연결되어 있지 않다면 나열하지 않습니다.

노드3은 노드1을 통해 노드2와 간접적으로 연결되어 있지만 직접적으로 연결되어 있지 않기 때문에 abj[3]의 리스트에 나열하지 않았습니다.

 

각 노드들에 접근하기 위해서는 이차원 배열과 같은 방식을 이용하면 됩니다. adj[1]의 vector는 총 세 개의 노드를 가지고 있으므로 다음과 같이 접근할 수 있겠습니다.

adj[1][0] = 2, adj[1][1] = 3, adj[1][2] = 4, adj[2][0] = 3

 

 

 

그렇다면 여기에서 Linked List의 갯수는 어떻게 계산하는 것일까요?

 

각 vector들에 Linked List와 같이 연결되어 있는 이 노드들은 각 노드들의 관계를 나타내는 것입니다.

왼쪽에 있는 무방향 그래프에서 보이는 선을 위에 그래프의 용어에서 설명했듯이 Edge라 부른다고 했습니다.

이 Edge들을 m이라고 할 때, 총 노드들의 계수는 2m개가 됩니다.

왜냐하면 연결은 두 개의 노드가 서로 연결되는 것이므로 원래의 Edge 개수보다 2배 더 많아지는 것입니다.

 

 

 

 

인접 리스트의 장점과 단점

 

• 장점
  
  인접리스트는 인접 행렬과 달리, 실제로 연결된 노드들에 대한 정보만 저장하기 때문에, 모든 백터들의 원소의 개수의 합이 간선의 개수와 같다는 점이 있습니다. 
  즉, 간선의 개수에 비례하는 메모리만 차지하는 것입니다.
  
  전체 노드에 대한 탐색을 수행하는 상황으로 생각해보면 노드가 V개, 간선이 E개라고 한다면 인접 행렬의 경우, 각 노드에 연결된 노드를 방문해보기 위해서 모든 노드에 대해 확인이 필요하기 때문에 총 O(V*V)의 시간이 걸릴 것입니다.
  
  하지만 인접 리스트의 경우 각 Vector 마다 연결된 노드들만 확인하는 것이 가능하기 때문에 전체 간선의 개수만큼만 확인해 볼 수가 있습니다. 따라서, O(E)의 시간 복잡도를 가진다고 할 수 있습니다.
  
  
  
• 단점
  
  노드i와 노드j가 연결되어 있는지 알고 싶다면 인접행렬의 경우에는 위에서 언급했듯이 adj[i][j]가 1인지 0인지만 확인하면 되기 때문에 O(1)의 시간 복잡도를 갖게 되지만 인접 리스트에서는 adj[i]의 Vector 전체를 돌며, j를 성분으로 갖는지 확인해 보아야 할 것입니다. 따라서, 인접 리스트의 경우 시간 복잡도가 O(V)가 됩니다.