공부하는 블로그

Graph ? 그래프(Graph)는 노드(N, Node)와 그 노드를 연결하는 간선(E, Edge)을 통해 정점간의 관계를 표현하는 자료구조이다. 일상 생활 속 지도나 지하철 노선도를 그래프라고 할 수 있다. 지도 어플에서 지점 간 최단 거리를 찾는 과정은 그래프를 탐색하는 과정이라 볼 수 있다. Graph 종류 그래프에서 간선은 방향성이 존재하며 화살표를 이용하여 표현한다. 간선은 순환이 가능하며 자체 간선(Self-loop)도 가능하다. 이러한 간선의 방향성과 순환성으로 그래프의 종류를 나눌 수 있다. 방향성의 유무에 따라 방향 그래프(Directed)와 무방향 그래프(Undirected)로, 순환성의 유무에 따라 순환 그래프(Cyclic)와 비순환 그래프(Acyclic)로 나뉜다. 간선에 가중치가 ..