그래프(Graph)

그래프(Graph)란, 노드(node)와 그 노드를 연결하는 간선(edge)을 하나로 모아 놓은 자료 구조이다.

그래프(Graph)의 용어

출처: Graph

• 정점(vertex): 위치라는 개념인데, 노드라고도 함.
• 간선(edge): 위치 간의 관계. 즉, 노드를 연결하는 선 (link, branch 라고도 부름)
• 인접 정점(adjacent vertex): 간선에 의해 직접 연결된 정점
• 정점의 차수(degree): 무방향 그래프에서 하나의 정점에 인접한 정점의 수
• 무방향 그래프에 존재하는 정점의 모든 차수의 합 = 그래프의 간선 수의 2배
• 진입 차수(in-degree): 방향 그래프에서 외부에서 오는 간선의 수 (내차수 라고도 부름)
• 진출 차수(out-degree): 방향 그래픙에서 외부로 향하는 간선의 수 (외차수 라고도 부름)
• 방향 그래프에 있는 정점의 진입 차수 또는 진출 차수의 합 = 방향 그래프의 간선의 수(내차수 + 외차수)
• 경로 길이(path length): 경로를 구성하는 데 사용된 간선의 수
• 단순 경로(simple path): 경로 중에서 반복되는 정점이 없는 경우
• 사이클(cycle): 단순 경로의 시작 정점과 종료 정점이 동일한 경우

그래프(Graph)의 특징

• 그래프는 네트워크 모델이다.
• 그래프는 크게 방향 그래프와 무방향 그래프 2가지 종류가 있다.(노드들 사이에서 무방향 경로를 가질 수 있고, 단방향/양방향 경로를 가질 수 있다.)
• 루트노드라는 개념과, 부모/자식관계라는 개념이 없다.
• 그래프는 순환(Cyclic)/비순환(Acyclic)이 있다.(loop/circuit, self-loop 모두 가능하다.)
• 순회는 DFS/BFS로 이루어진다.

그래프(Graph)의 종류

• 무방향 그래프(Undirected Graph): 연결 관계에 있어서 방향성이 없는 그래프이다.

• 방향 그래프(Directed Graph): 간선에 방향성이 존재하는 그래프이다.

출처: Graph Types