|
탐색과 너비우선탐색에
대해 비교, 설명하시오.
◎ 깊이 우선 탐색(DFS, Depth First Search)
- 주어진 장점 v를 출발점으로 하여 이를 방문
- 다음 v에 인접하고 아직 방문하지 않은 장점 w를 선택하여 w를 출발점으
로 해서 다시 깊이 우선 탐색을 시
|
|
|
/*********************************************************/
/* Graph 및 Queue class 정의 */
/*********************************************************/
#include <iostream>
using namespace std;
/* Node class */
template <class T>
class Node
{
|
|
|
|
#include <stdio.h>
#include <malloc.h>
#define MAX_VERTICES 50
#define true 1
#define false 0
//GraphType
typedef struct GraphType *Graph_ptr;
typedef struct GraphType{
int vertex;
Graph_ptr link;
}GraphType;
Graph_ptr g_root;
typedef struct LinkType *Link_ptr;
typed
|
|
|
//0을 입력 할 경우 입력 종료
}
void enqueue(int item) //큐에 원소 저장 , 큐가 꽉 찼을 경우 오류 메세지 출력
{
if(count == SIZE){
printf("\n\nFULL QUEUE\n\n");
}else {
queue[rear] = item;
rear = ++rear % SIZE;
++count;
}
}
int dequeue(void) //큐에서 원소 제거후 값 리턴, 큐
|
|
|
탐색 종료
단점 : 목표 노드가 없는 경로에 깊이 빠질 수 있음 <- 깊이 제한
너비우선탐색(BFS, Breadth First Search)
생성된 순서에 따라 노드 확장
큐 구조, 큐의 첫 정점을 보고 그 정점에 인접한 정점들 탐색
새롭게 발견되는 정점 enqueue,
|
|
메뉴펼치기
