[자료구조] Graph

Graph 

객체간의 관계를 정점(Vertex)과 간선(Edge)으로 나타낸 자료구조이다.

현실의 다양한 문제를 효과적으로 모델링하기 쉽다.

쉽게 생각하면 지하철노선도를 생각하면 쉽다. 지하철역은 정점, 역이 연결된 노선은 간선으로. 다른 예시로는 sns에서의 팔로잉, 네비게이션의 길찾기정도로 생각하면 될거같습니다. 

 

 

용어

• 간선
• 정점
• 차수 -한개의 정점에 있는 간선의 수
• 노란글자는 인접 ( 9에 인접한것은 6, 10이다)
• 경로(정점에서 정점으로 가는 노드의 길)
  • 5 - 6까지의 경로의 개수
    • 5-7-3-0-1-6
    • 5-7-1-6

 

 

Graph의 종류

• 무방향 그래프 : 간선의 방향이 없음
• 방향 그래프 : 간선의 방향이 존재
• 비가중 그래프 : 간선에 가중치가 없음
• 가중 그래프 : 간선에 가중치가 있음
• 비순환 그래프 
• 순환 그래프

등이 있다