그래프

그래프란

• 실제 세계의 현상이나 사물을 정점(vertex) or 노드(node) 와 간선(edge)로 표현하기 위해 사용한다.

그래프 용어

• 노드(node) : 위치를 뜻함 정점(vertex)라고도 불림

• 간선(edge) : 위치간의 관계를 표시한 선

• 인접정점(adjacent vertex) : 간선으로 직접 연결된 노드

그래프의 종류

• 무방향 그래프

방향이 없는 그래프로 간선을 통해서 노드는 양방향으로 이동이 가능한 그래프이다. A와 B가 있을때 (A,B) (B,A) 로 표기가 가능하다.

• 방향 그래프

방향이 있는 그래프로 양방향이 불가능한 그래프를 뜻한다. A 에서 B로 가는 그래프가 존재할 때 <A,B> 로 표기가 가능하다

• 가중치 그래프

간선에 비용 또는 가중치가 할당되어 있는 그래프

그래프와 트리의 차이

그래프

1. 노드와 노드를 연결하는 간선으로 표현된 자료구조

2. 방향그래프, 무방향 그래프 둘다 존재한다.

3. 사이클 순환이 가능하고 비순환 사이클 또한 가능하다.

4. 루트 노드가 존재하지 않는다.

5. 부모 자식 개념이 존재하지 않는다.

트리

1. 그래프의 한 종류로 방향성이 있는 비순환 그래프다.

2. 방향 그래프만 존재한다.

3. 비순환으로 사이클이 존재하지 않는다.

4. 루트 노드가 존재한다.

5. 부모 자식 개념이 존재한다.