트리와 그래프

그래프

트리와 그래프에서 그래프는 노드와 에지로 상태들의 연결 관계를 표현한 것이다. 지도에서 도시는 노드, 도시간 도로는 에지, 도로의 거리는 비용으로 볼 수 있다.

$$G=(V,E)$$

$V$는 노드 집합, $E\subseteq V\times V$는 에지 집합이다.

트리

트리는 루트 노드가 있고, 각 자식 노드가 하나의 부모만 가지는 구조이다. 탐색에서는 시작 상태를 루트로 두고 가능한 다음 상태를 자식으로 확장해 탐색 트리를 만든다.

노드가 $n$개인 연결된 트리의 에지 수는 다음과 같다.

$$|E|=|V|-1$$

탐색에서의 차이

그래프는 같은 상태로 돌아오는 경로가 있을 수 있다. 그래서 중복 방문을 막기 위해 OPEN과 CLOSED 같은 리스트를 사용한다. 트리는 탐색 과정을 펼쳐 보기 좋지만, 실제 문제는 그래프 구조인 경우가 많다.