[c++] 알고리즘 개념공부 :: 자료구조 - 그래프

그래프

1. 용도

2. 용어 정리

   1. 기본

   2. 심화

3. 구현

   1. 인접 행렬

   2. 인접 리스트

   3. 비교

4. 연산

5. 분류

   1. 방향성에 따른 분류

   2. 연결에 따른 분류

   3. 사이클에 따른 분류

   4. 특수한 그래프

6. 탐색

7. 도출된 문제들

8. 관련 알고리즘

9.  

   참고

    

    

그래프

 그래프란 '노드'와 노드를 연결하는 '간선'으로 이루어진 자료구조이다. 지금까지의 살펴본 자료구조들(리스트, 스택, 큐 등)과는 달리 그래프는 비선형 자료구조 이다.

 

용도

 그래프는 일상생활에서 연결되어있는 객체 간의 관계를 표현할 때 사용된다. 예로 지도나 지하철 노선도, 전기회로, 도로 등을 들 수 있다. 또한 컴퓨터 세부전공에서는 통신 네트워크 분야에서도 쓰이며, 논리회로를 설계하고 분석하는 데에도 사용된다.

 최근에는 웹사이트의 링크 연결(Page Rank)이나 SNS 상의 친구관계를 표현하는 데에도 사용되고 있다.

 

용어 정리

기본

G = (V, E) (G는 그래프, V는 Vertex, E는 Edge이다.)

• 정점 (vertex) : 노드라고도 부르는 객체이다.

• 간선 (edge) : 정점 간의 관계를 나타내며, 정점을 연결하는 데에 사용되는 선이다. link나 branch, arcs라고도 불린다.

• 인접 정점(adjacent vertex) : 하나의 간선에 의해 직접 연결된 정점이다.

• 정점의 차수 (degree) : 정점에 연결되어있는 간선의 갯수이다.

  <무방향 그래프>

  무방향 그래프에서 정점의 모든 차수의 합이 간선 수의 2배이다.

  <방향 그래프>

  방향 그래프에서 정점의 진입 차수, 진출 차수의 총합이 간선 수이다.

  • 진입 차수 (in-degree) : 방향 그래프에서 정점으로 들어오는 간선의 수이다. 내차수라고도 불린다.
  • 진출 차수 (out-degree) : 방향 그래프에서 정점에서 나가는 간선의 수이다. 외차수라고도 불린다.

• 부분 그래프 (subgraph) : 어떤 그래프의 정점과 간선의 일부로 이루어진 그래프이다.

• 경로 (path) : 특정 정점에서 다른 정점으로 가는 간선의 리스트이다.

  • 단순 경로 (simple path) : 경로 중 같은 정점이 없는 경로이다.
  • 순환 (cycle) : 단순 경로의 시작 정점과 종료 정점이 동일한 경로이다.
  • 경로의 길이 (length) : 경로를 구성하는데 사용된 간선의 수이다.

 

심화

• 단절 점(articulation point) : 그래프 상에 존재하는 정점으로, 제거 시 연결그래프의 특성을 잃게 하는 점이다.

 

• bridge edge : 그래프 상에 존재하는 간선으로, 제거 시 연결그래프의 특성을 잃게 하는 선이다.

 

구현

배열과 연결리스트로 구현할 수 있다.

 

인접 행렬

인접행렬로 구현하면 불필요한(연결되어있지 않은) 연결관계도 표현해야하므로 공간을 많이 차지한다. 정확히 ''정점의 갯수'의 제곱'에 해당하는 공간인 O(V^2)을 차지한다. 무방향 그래프에서는 symmetric한 행렬이 나오고, 가중치 그래프는 1이 아닌 해당 간선의 가중치가 기록된다. 두 정점이 연결되어있는지를 확인할 때는(간선이 존재하는지를 확인할 때는) O(1)의 시간밖에 걸리지 않는다는 장점이 있다.

 

인접 리스트

 인접리스트로 구현하면 전체 정점을 표현한 후, 해당 정점에 연결되어있는 정점들만을 연결리스트로 나타내면 된다. 따라서 전체 정점을 표현하는데에 '정점의 갯수'만큼의 공간이, 각 정점에 연결된 정점을 표현하는데에 '간선의 갯수'만큼의 공간이 필요하기 때문에 공간복잡도는 O(E)이다. 정확히 나타내면 포인터라는 요소가 들어가기 때문에 데이터만 저장할 때보다 공간이 더 필요하다.

 인접리스트로 두 정점이 연결되어있는지를 확인하려면(간선이 존재하는지를 확인하려면) 연결된 정점들을 순차접근해서 확인해야하므로 O(E) 만큼의 시간이 필요하다.

 

비교

기준	인접 행렬	인접 리스트
공간복잡도	O(V^2)	O(E)
간선 삽입	O(1)	O(E)
간선 존재 확인	O(1)	O(E)
정점 연결 확인	O(V)	O(E)

E : 간선의 갯수

V : 정점의 갯수

 

연산

1. 새로운 정점 추가
2. 특정 값의 정점이 존재하는 지 확인
3. 정점 삭제 및 간선 제거
4. 새로운 간선 추가
5. 두 정점 간의 간선이 존재하는 지 확인
6. 간선 제거
7. 그래프 순회

 

분류

방향성에 따른 분류

• 방향 그래프 (directed graph)

  정점 A에서 B로 가는 간선은 <A,B>와 같이 표현한다.

  => <B,A>와 다르다.

• 무방향 그래프 (undirected graph)

  정점 A와 B를 연결하는 간선은 (A,B) 와 같이 표현한다.

  => (B,A)와 같다.

모든 directed graph는 Strongly Connected Graph와 Directed Acyclic Graph로 표현할 수 있다. 자세한 설명은 새로운 글로 작성하겠다.

(SCC, DAG)

 

연결에 따른 분류

• 연결 그래프 (connected graph)

  모든 정점 간의 경로가 존재하는 그래프이다. 방향성 그래프일 때는 strongly connected graph라고 불린다.

  • strongly connected graph

    방향 그래프에서 모든 노드에 대해 서로간의 경로가 존재하는 그래프이다.

  • weakly connected graph

    무방향 그래프에서 모든 노드에 대해 서로간의 경로가 존재하는 그래프이다.

• 비연결 그래프 (disconnected graph)

  무방향 그래프에서 특정 정점쌍 사이에 경로가 존재하지 않는 그래프이다.

  Giant Component : 가장 노드가 많이 연결된 그래프의 노드들

 

사이클에 따른 분류

• 순환 그래프 (cyclic graph)

  순환이 존재하는 그래프이다.

• 비순환 그래프 (acyclic graph)

  순환이 존재하지 않는 그래프이다.

=> acyclic인지 알 수 있는 방법은 In(N) 교집합 Out(N) 가 공집합인지 확인하는 것이다. 특정노드 N을 기준으로 In(N)은 간선을 계속 따라가보면 되고, Out(N)은 역방향그래프를 만들어 간선을 따라가보면 된다. 간선을 따라가는 방법은 DFS를 사용하면 된다. 두 집합의 교집합이 공집합이라면 Acyclic하다.

 

특수한 그래프

• 가중치 그래프 (Weighted graph)

  간선에 비용(cost)이나 가중치(weight)가 할당된 그래프로 네트워크라고도 불린다.

• 완전 그래프 (Complete graph)

  모든 정점이 간선으로 연결된 그래프이다. 방향성 그래프일 때는 모든 정점이 진입 간선과 진출 간선으로 연결되어있어야하며, 이를 strongly complete graph라고 불린다. 완전그래프에서 정점의 갯수를 n이라고 한다면, 간선의 갯수는n*(n-1) / 2이다.

• 이분 그래프 (bipartite graph)

 

전체 그래프 G를 서로 다른 2개의 집합 V1, V2로 나누었을 때, V1에 속해 있는 어떤 두 정점도 G에서 인접하지 않고 V2로 마찬가지일 때 전체 그래프 G는 이분 그래프이다.

• 평면 그래프 (planar graph) : 평면에 그래프를 그렸을 때, 간선이 서로 교차하지 않는 그래프이다.

• 보통 그래프 (regular graph) : 모든 정점의 차수가 같은 그래프이다.

• 멀티 그래프 (multigraph) : 같은 간선이 존재하는 그래프이다. 보통 그래프 자료구조에서 허용되지 않는다.

• 이중 결합 그래프(biconnected graph) : 단절점이 존재하지 않는 그래프이다.

  • 이중 결합 요소(biconnected component) : 이중 결합 그래프에서 이중 결합 되어있다고 볼 수 있는 가장 큰 요소이다.

• 트리 (Tree)

  DAG(Directed Acyclic Graph)이며 바로 뒷 파트에 나온다.

 

탐색

• DFS(Depth First Search)

  깊이 우선 탐색이다. 스택을 사용한다.

• BFS(Breath Frist Search)

  너비 우선 탐색이다. 큐를 사용한다.

(DFS / BFS 링크)

 

도출된 문제들

• 오일러 경로 (Euler path)

  그래프에 존재하는 모든 간선을 한 번씩만 통과하는 경로이다. (처음 정점으로 되돌아갈 필요는 없다.)

  '쾨니히스 베르크의 다리건너기'라는 문제가 이에 관련된 문제이다.

  <존재 조건>

  • 모든 정점의 차수가 짝수이거나 2개이다.

    차수가 2개인 정점이 존재한다면, 해당 정점 2개가 경로의 시작과 끝점이다.

• 오일러 순환 (Euler cycle)

  그래프에 존재하는 모든 간선을 한 번씩만 통과하면서 처음 정점으로 되돌아오는 경로이다.

  <존재 조건>

  • 모든 정점의 차수가 짝수이다.

• 헤밀턴 순환 (Hamiltonian cycle)

  그래프에 존재하는 모든 정점을 한 번씩만 통과하면서 처음 정점으로 되돌아오는 경로이다. 모든 간선을 지날 필요는 없다.

• 외판원순환 문제 (TravelingSalespersonProblem)

  헤밀턴 순환 중 가장 적은 비용의 경로를 찾는 문제이다.

 

관련 알고리즘

(알고리즘 - 그래프 정리)

 

참고

http://59.23.150.58/30stair/graph/graph.php?pname=graph