Today I Learned - Graph

그래프(Graph)란?

그래프란 상하위의 개념이 없이 각각의 node와 그 node들 간의 간선(edge)을 하나로 모아 놓은 자료 구조

 

 

그래프의 특징

그래프는 꼭 모든 node들이 서로 관계를 갖고 있어야만 하지 않다.

따라서 그래프는 node간 연결이 없는 고립된 부분이 있을 수도 있고, 순환할 수도 있고,

안할 수도 있기 때문에 가장 형식에 얽매이지 않은 자료구조라고 볼 수 있다.
이러한 특성 때문에 그래프 자료구조를 네트워크 모델 이라고 부른다.

 

 

 

그래프 용어 정리

 

노드(node): 위치라는 개념. (vertex 라고도 부름)

간선(edge): 위치 간의 관계. 즉, 노드를 연결하는 선 (link, branch 라고도 부름)

인접 노드(adjacent vertex): 간선에 의 해 직접 연결된 노드

노드의 차수(degree): 무방향 그래프에서 하나의 노드에 인접한 정점의 수

무방향 그래프에 존재하는 노드의 모든 차수의 합 = 그래프의 간선 수의 2배

진입 차수(in-degree): 방향 그래프에서 외부에서 오는 간선의 수 (내차수 라고도 부름)

진출 차수(out-degree): 방향 그래픙에서 외부로 향하는 간선의 수 (외차수 라고도 부름)

방향 그래프에 있는 정점의 진입 차수 또는 진출 차수의 합 = 방향 그래프의 간선의 수(내차수 + 외차수)

경로 길이(path length): 경로를 구성하는 데 사용된 간선의 수

단순 경로(simple path): 경로 중에서 반복되는 정점이 없는 경우

사이클(cycle): 단순 경로의 시작 정점과 종료 정점이 동일한 경우