알고리즘 - Breath First Tree, Depth First Tree, Prim알고리즘, Kruscal알고리즘, Dijkstra알고리즘

소개글

알고리즘 - Breath First Tree, Depth First Tree, Prim알고리즘, Kruscal알고리즘, Dijkstra알고리즘에 대한 보고서 자료입니다.

목차

Breath First Tree

Depth First Tree

Prim 알고리즘

Kruscal 알고리즘

Dijkstra 알고리즘을 C로 구현

본문내용

Breadth First Tree (너비우선 탐색트리)
트리 탐색작업을 할 때 너비우선으로 검색을 하는 트리로 무방향 그래프 G(V,E)에서 시작해 정점 V를 방문한 후 V에 인접한 아직 방문하지 않은 모든 정점들을 방문한 뒤, 다시 이 정점에 인접하면서 방문하지 않은 모든 정점들에 대해 너비우선 검색을 반복적으로 수행하는 트리를 말한다.
BFT의 탐색 순서
1. 특정 vertex를 시작점으로 선택한다.
2. 선택된 vertex에 “방문”표시를 한다.
3. 선택된 vertex에 연결된 여러 vertex들을 검사하여 미방문 vertex들을 큐에 삽입한다.
4. 큐의 front에서 하나의 vertex를 꺼내어 새롭게 선택한다.
5. 큐가 빌 때까지 2-4의 과정을 반복한다.

키워드

알고리즘,   Breath First Tree,   Depth First Tree,   Prim 알고리즘,   Kruscal 알고리즘,   Dijkstra 알고리즘