#5 그래프(Graph)

1. 그래프(Graph)

 그래프는 정점(Vertex)들과 그 정점들 사이를 연결하는 간선(Edge)으로 이루어진 비선형자료구조이다.  정점은 

노드(Node) 라고도 부른다.  또한 각 노드에 연결된 간선의 갯수를 그 노드의 차수(Degree) 라고 한다.

 

그래프의 예시

위의 예시는 0부터 5 까지의 숫자를 담고있는 6개의 노드와 그 사이를 잇는 8개의 간선으로 이루어진 그래프이다.

 

 

2. 그래프의 종류

  1) 유향 그래프(Directed Graph)

• 위와 같이 간선에 방향성이 있는 그래프를 의미한다.  노드 사이의 경로가 왕복 불가능한 것이어야할 경우 사용된다.

 

  2) 무향 그래프(Undirected Graph)

• 위와 같이 간선에 방향성이 없는 그래프를 의미한다.  단순히 두 노드가 연결되어있다는 정보만을 제공한다.
  
  
• 일반적으로 그래프라고 하면 무향 그래프를 의미하는 경우가 많다.  두 노드 사이의 경로가 왕복 가능한 경로일
  경우 사용된다.

 

  3) 가중 그래프(Weighted Graph)

• 위와 같이 간선에 가중치가 존재하는 그래프를 의미한다. 
  
  
• 가중치의 의미는 노드 사이의 이동에 드는 비용이나 두 노드 사이의 거리 등 경우에 따라 다르다.

 

  4) 완전 그래프(Complete Graph)

• 위와 같이 임의의 두 노드 사이에 반드시 하나의 간선이 존재하는 그래프를 의미한다. 
  
  
• 이 경우 간선의 갯수는 (노드의 갯수 * (노드의 갯수 - 1)) / 2 개가 된다. 

 

 

  5) 부분 그래프(SubGraph)

그래프 A                                                      그래프 B                                                    그래프 C

• 어떤 그래프 U 의 모든 노드와 간선이 다른 그래프 V 에 속한다고 할 때, 그래프 U는 그래프 V 의 부분 그래프이다.
  위 예시에서 그래프 B와 C는 모두 그래프 A의 부분그래프이다.
   
• 그래프 C와 같이 임의의 두 노드간의 관계가 그래프 A의 두 노드간의 관계와 동일한 부분 그래프를 유도 부분
  그래프(Induced SubGraph) 라고 한다. 그래프 B의 경우 노드 3과 5의 연결관계가 그래프 A와 다르기 때문에
  그래프 A의 유도 부분 그래프가 아니다.
  
  
• 그래프 B와 같이 노드의 집합(Node Set)이 그래프 A와 동일한 부분 그래프를 신장 부분 그래프(Spanning
  SubGraph) 라고 한다. 그래프 C의 경우 노드 0이 빠져있기 때문에 그래프 A의 신장 부분 그래프가 아니다.

 

  6) 유향 비순환 그래프(Directed Acyclic Graph)

• 위와 같이 유향 그래프 중에서도 한번 지나친 노드를 다시 방문할 수 없는, 즉 순환(Cycle)이 존재하지 않는
  유향 그래프를 유향 비순환 그래프(DAG)라고 한다.  위상 정렬이 존재하는 그래프라고 생각하면 편하다.
  
  
• 선후 관계가 정의된 데이터를 그래프화 하여 표현하기에 좋다.  대표적인 예시로 스프레드 시트에서 셀 간의
  참조관계를 표현하는데 활용할 수 있다.

 

3. 그래프의 표현

 그래프를 표현하는 두 가지 대표적인 방법을 알아본다.  여기서는 무향 그래프를 기준으로 설명한다.

  

  1) 인접 행렬

 

• 위와 같이 노드간의 연결관계를 행렬로 나타내는 방식이다.  mat[i][j] = 1이라면 노드 i와 j가 연결되어있음을,
  0이라면 연결되어있지 않음을 의미한다.  가중 그래프를 나타낼 경우 1 대신 가중치를 사용하면 된다.
  
  
• 예시와 같이 무향 그래프일 경우에 한해서 인접행렬은 대각 성분을 기준으로 대칭을 이루는 성질을 가진다.
  
  
• 구현이 간단하고 임의의 두 노드간의 연결여부를 확인에 O(1) 의 시간복잡도를 보인다는 장점이 있다.
• 특정 노드와 연결된 모든 노드를 탐색하기 위해 반드시 노드의 총 갯수만큼의 탐색이 필요하다는 단점이 있다.
  노드 갯수가 V인 그래프에서 한 노드에 연결된 노드를 탐색하는데 O(V)의 시간복잡도를 보인다.
  
  
• 위의 특성으로 인해 노드 갯수에 비해 간선의 갯수가 적은 희소 그래프(Sparse Graph)일 경우 메모리와 시간낭비가
  심해진다.

 

  2) 인접 리스트

• 위와 같이 노드간의 연결관계를 각 노드에 연결된 노드들의 리스트로 나타내는 방식이다.  가중 그래프를 나타낼
  경우 노드 번호와 가중치를 함께 리스트의 요소로 넣어주면 된다.
  
  
• 한 노드에 연결된 모든 노드를 탐색하기 위해 그 노드에 연결된 노드의 갯수만큼의 탐색만이 필요하며
  간선의 갯수만큼의 메모리만 차지하기 때문에 메모리와 시간을 절약 가능하다는 장점이 있다.
  
  
• 임의의 두 노드 u, v 간의 연결 여부를 알기 위해 list[u] 또는 list[v] 의 길이만큼의 탐색이 필요하다는 단점이 있다.