그래프(Graph)

정의

• 노드와 노드를 연결하는 간선을 하나로 모아 놓은 자료구조이다.
• 정점과 간선의 집합으로 표현할 수 있다.
• 그래프는 현상이나 사물을 정점과 간선으로 표현한 형태로, 정점(Vertex)은 대상이나 개체를 나타내고 간선(Edge)은 이들 간의 관계를 나타낸다.

특징

• 그래프의 종류에는 방향 그래프와 무방향 그래프가 있으며, 간선에 방향의 유무에 따른 차이가 존재한다.

• 추상적인 개념의 연결 관계를 표현하기 위해서 많이 사용한다.

• 사이클이 없는 Graph는 Tree와 같다.

• 사이클(순환경로를 말하며 경로의 시작 정점과 종료 정점이 동일한 경우)이 발생할 수 있다.

• 2개 이상의 경로가 가능하다.

• 부모 - 자식 관계라는 개념이 없다. (루트 로드라는 개념이 없음)

• 정점은 여러 개의 간선을 가질 수 있다.

• 간선은 가중치를 가질 수 있다.

  → 가중치 : cost(비용). ex) 깊이우선탐색(DFS) 그래프에 많이 사용

• 도시를 연결하는 도로망이나 웹 사이트간에 링크 관계에 사용하고 있다.

용어