자료구조 - Graph

Graph(그래프)

• 비선형 자료구조
• 점 : 노드(Node),정점(Vertex)
• 선 : link,edge(간선)
• degree : 정점(vertex)에 부속된 간선(edge) 수

그래프 종류

• 무방향 그래프 : 두 정점을 연결하는데 간선에 방향이 없는 그래프
• 방향 그래프 : 두 정점을 연결하는데 간선에 방향이 있는 그래프
• 완전 그래프 : 모든 정점들이 연결되고, 최대 간선수를 가지는 그래프
  -> n개 정점에서 무뱡향 & 완전그래프 최대 간선 수 : n(n-1)/2
  -> n개 정점에서 뱡향 & 완전그래프 최대 간선 수 : n(n-1)
• 부분 그래프 : 일부 정점이나 간선을 제외하여 만든 그래프
• 가중 그래프 : 간선에 가중치를 할당한 그래프
• 유향 비순환 그래프 : 방향그래프에서 cycle이 없는 그래프
• 연결 그래프 : 떨어져있는 정점이 없는 그래프
• 단절 그래프 : 떨어져있는 정점이 있는 그래프

Spinning Tree

MST(Minimum Spinning Tree)

구현하는 방법

1. krusal's Algorithm

2. prim's Algorithm