그래프

책 <파이썬 자료구조와 알고리즘>을 기본으로 배운 알고리즘 내용입니다

목차

• 1. 그래프(Graph)
  
• 2. 그래프(Graph)의 특징
  
• 3. 그래프(Graph) 관련 용어
  
• 4. 그래프(Graph)의 종류
  
• 5. 그래프와 트리의 차이
  
• 6. 그래프(Graph)의 구현 2가지

 

<그래프>

1. 그래프(Graph)

• 그래프(Graph)는 일련의 노드(node, 정점) 집합 V와 간선(arc, 아크) 집합 E로 구성된다.
• 일반적으로 노드엔 데이터, 간선엔 노드와 노드 사이의 관계 정보가 포함되어 있다. 

 

 

2. 그래프(Graph)의 특징

• 그래프는 네트워크 모델 이다.
  
• 2개 이상의 경로가 가능하다. 즉, 노드들 사이에 무방향/방향에서 양방향 경로를 가질 수 있다.
• self-loop 뿐 아니라 loop/circuit 모두 가능하다.
  
• 루트 노드라는 개념이 없다.
  
• 부모-자식 관계라는 개념이 없다.
  
• 순회는 DFS나 BFS로 이루어진다.
  
• 그래프는 순환(Cyclic) 혹은 비순환(Acyclic)이다.
  
• 그래프는 크게 방향 그래프와 무방향 그래프가 있다.
  
• 간선의 유무는 그래프에 따라 다르다.
  

 

 

3. 그래프(Graph) 관련 용어

3-1) 차수(degree)

해당 노드에 연결된 엣지의 수(혹은 엣지 가중치의 합)

 

3-2) loop/고립(isolated)

loop : 한 간선이 같은 노드에 부속해 있는 것

이와 반대로 임의의 한 노드에 부속해 있는 간선이 전혀 없을 때 해당 노드를 고립(isolated)되었다고 한다.

 

3-3) 경로(path)

• 그래프에서 경로(path)란 인접한 노드들로 구성된 시퀀스(1개 이상)를 가리킨다.
• 간선이 겹치지 않는 경로를 simple하다고 하고, 노드가 겹치지 않는 경로를 elementary하다고 한다.
• 경로의 길이(length)는 경로 내 존재하는 간선의 수를 나타낸다.

1. [v1,v2,v3,v4,v5,v3,v4,v5] : 인접한 노드들로 구성돼 있기 때문에 경로라고 할 수 있다. 그러나 간선도, 노드도 겹치기 때문에 simple하지도, elementary하지도 않다.
2. [v1,v2,v3,v4,v5,v8,v6,v4,v7] : 인접한 노드들로 구성돼 있기 때문에 경로라고 할 수 있다. 간선이 겹치지 않기 때문에 simple하다. 하지만 노드가 겹치기 때문에 elementary하지는 않다.

 

3-4) 사이클(cycle)

• 사이클(cycle)이란 한 노드에서 시작해 해당 노드에서 끝나는 경로를 가리킨다.
• 사이클(cycle) 또한 간선이 겹치지 않는 경우 simple하다고 하고, 노드가 겹치지 않을 경우 elementary하다고 한다.

1. [v1,v2,v3,v4,v5,v8,v6,v5,v9,v1] : 인접한 노드들로 구성돼 있고 v1으로 시작해 v1으로 끝났으므로 사이클이다. 간선이 겹치지 않기 때문에 simple하다고 말할 수 있다. 하지만 노드가 겹치기 때문에 elementary하지는 않다.
2. [v1,v2,v3,v4,v5,v9,v1] : 인접한 노드들로 구성돼 있고 v1으로 시작해 v1으로 끝났으므로 사이클이다. 간선도, 노드도 겹치지 않기 때문에 각각 simple하고, elementary하다고 말할 수 있다.

 

3-5) 연결 connected

임의의 두 노드가 연결되었다(connected)는 것은 두 노드 사이에 경로가 존재한다는 것이다. 연결된다는 것은 다음과 같이 정의된다.

• 모든 노드쌍 사이에 경로가 존재하는 무방향그래프는 연결되었다고 말한다.
• 임의의 방향그래프에서 방향을 무시하고 보면 연결되어 있을 경우, 해당 방향 그래프는 연결되었다고 말한다.
• 방향그래프의 임의의 노드쌍 aa, bb에 대해 aa에서 bb로 가는 경로, bb에서 aa로 가는 경로가 존재한다면, 해당 방향그래프는 강연결(strongly connected)되었다고 말한다.

아래 방향그래프에서 방향을 무시하고 보면 이 그래프 내 임의의 노드쌍 사이에 모두 경로가 존재하므로 아래 방향그래프는 연결 그래프(connected graph)이다. 하지만 v1에서 v3로 가는 경로는 존재(v1,v2,v3,v9,v3)하지만, v3에서 v1으로 가는 경로는 존재하지 않으므로 strongly conntected graph는 아니다.

 

3-6) 연결요소(connected component)

• 원 그래프 G에서 노드와 엣지가 서로 겹치지 않는(independent) 부분그래프를 G의 요소(component)라고 한다.
• 요소들 중에 요소 내 모든 노드쌍에 대해 경로가 존재하는 부그래프 S를 G의 연결요소(connected component)라고 한다.
• 연결그래프(connected graph)는 하나의 연결요소만 가진다.
• 연결요소 가운데 노드 수가 가장 많은 연결요소를 최대연결요소(maximal connected component)라고 한다.

 

3-7) 오일러 경로(Eulerian tour)

• 그래프에 존재하는 모든 간선을 한 번만 통과하면서 처음 노드로 되돌아오는 경로를 말한다.
  
• 그래프의 모든 정점에 연결된 간선의 개수가 짝수일 때만 오일러 경로가 존재한다.
  

 

 

4. 그래프(Graph)의 종류

4-1) 방향그래프(directed graph, digraph)

간선이 순서가 있는 쌍으로 표현된 그래프의 일종(간선이 방향성을 가짐.)

만약 V2에서 V1으로 향하는 엣지 e1가 있다면, e1을 V2의 진출 간선, V1의 진입간선이라고 한다.

방향그래프에서 한 노드의 차수(degree)는 incoming degree(한 노드에 들어오는 간선의 수)와 outgoing degree(한 노드에서 나가는 간선의 수)로 나뉜다. 

 

4-2) 부분그래프(subgraph)

임의의 그래프 G=(V,E)가 주어졌을 때 다음을 만족하는 G′=(V′,E′)는 G의 부분그래프(subgraph)라고 한다.

• E′는 V′에만 부속(=V′에 속한 모든 간선이 G′에 있어야 함)되어 있으며 E의 부분집합이다.
• V′는 V의 부분집합이다.

이 가운데 V=V′를 만족하는 부분그래프를 신장 부분 그래프(spanning subgraph)라고 한다. 쉽게 말해 원 그래프와 노드는 같고 일부 간선만 포함된 부분그래프를 가리킨다.

이 부분그래프가 트리을 만족할 경우 신장 트리 그래프(spanning tree)라고 한다. 

원그래프(좌측), 신장 부분그래프(우측)

 

4-3) 완전그래프(complete graph)/ 다중그래프(multigraph)

완전그래프(complete graph) : 모든 노드들이 간선으로 연결되어 있어, 간선의 수가 최대인 그래프

다중그래프(multigraph) : 노드 사이를 잇는 엣지가 하나 이상일 경우

완전그래프(좌측), 다중그래프(우측)

 

4-4) 가중치그래프(weighted graph)

• 간선에 가중치 내지 우선순위 정보가 추가된 형태의 그래프
• 함수 G는 간선을 가중치로 매핑하는 역할을 한다.
• 방향가중치그래프(directed weighted graph) : 방향그래프가 가중치를 가지는 것

가중치 그래프

 

 

5. 그래프와 트리의 차이

 

6. 그래프(Graph)의 구현 2가지
6-1) 인접 리스트(Adjacency List)

• 인접 리스트(Adjacency List)로 그래프를 표현하는 것이 가장 일반적인 방법이다.
  
• 모든 정점(혹은 노드)을 인접 리스트에 저장한다. 즉, 각각의 정점에 인접한 정점들을 리스트로 표시한 것이다.

 

6-2) 인접 행렬(Adjacency Matrix)

• 정점(노드)의 개수가 N인 그래프를 인접 행렬로 표현
  
• 무방향 그래프를 인접 행렬로 표현한다면 이 행렬은 대칭 행렬(Symmetric Matrix)이 된다.
  
• 인접 리스트를 사용한 그래프 알고리즘들(Ex. 너비 우선 탐색) 또한 인접 행렬에서도 사용이 가능하다. 하지만 인접 행렬은 조금 효율성이 떨어진다.
  
• 인접 리스트는 어떤 노드에 인접한 노드들을 쉽게 찾을 수 있지만 인접 행렬에서는 인접한 노드를 찾기 위해서는 모든 노드를 전부 순회해야 한다.