[Data Structure] Graph, etc

Graph는 기본적인 형태이다.

방향의 여부, 가중치의 여부, 연결의 여부, 순환의 여부 등에 따라서 이름이 변경되고 결정된다.

예를 들어, Minimum Spanning Tree의 의미를 하나씩 분석해보자.

 

Tree?

• 순환(Cycle)이 없어야 함.
• 1개의 Root Node를 갖는다.

Spanning Tree?

• 순환(Cycle)이 없어야 함.
• 1개의 Root Node를 갖는다.
• Spanning : (다리를) 놓다, ~의 양 끝을 연결하다
  • '모든 정점(노드)를 잇는다'로 해석할 수 있음.

Minimum Spanning Tree?

• 순환(Cycle)이 없어야 함.
• 1개의 Root Node를 갖는다.
• Spanning : (다리를) 놓다, ~의 양 끝을 연결하다
  • '모든 정점(노드)를 잇는다'로 해석할 수 있음.
• Minimum : 최저의, 최소한의
  • 즉, '모든 정점(노드)를 최소한으로 잇는다'로 해석할 수 있음.

 

이러한 단계적인 접근 방법을 통해서 Minimum Spanning Tree를 분석해보면, 왜 최단거리를 찾는 데 사용되는지 이해할 수 있음. 쉽쥬?

 

1. Graph

• 방향(Directed) 그래프 / 무방향(Undirected) 그래프
• 가중치(Weighted) 그래프
  • 간선에 비용이나 가중치가 할당된 그래프
  • '네트워크(Network)'라고도 함.
• 연결(Connected) 그래프 / 비연결(Disconnected) 그래프  ---- 무방향(Undirected) 그래프 하위 개념
  • 연결(Connected) 그래프 중 사이클이 없으면, 트리(Tree)
• 순환(Cycle) 그래프 / 비순환(Acyclic) 그래프
• 완전(Complete) 그래프
  • 그래프에 속하는 모든 정점이 서로 연결되어 있는 그래프
  • 무방향(Undirected) 완전(Complete) 그래프
    • 정점 수(n)이면 간선의 수(nC₂)