자료구조 :: 그래프(2) 탐색, 깊이우선, 너비우선 탐색

# 그래프 탐색

그래프 탐색은 그래프의 가장 기본적인 연산으로서 하나의 정점으로부터 시작하여 차례대로 모든 정점들을
한번씩 방문하는 것이다. 그래프의 많은 문제들이 단순히 그래프의 노드를 탐색하는 것으로 해결된다.


# 깊이 우선 탐색(depth first search : DFS)

깊이 우선 탐색은 그래프의 시작 정점에서 출발하여 먼저 시작 정점 v를 방문하고 표시한다.
v에 인접한 정점들 중에서 아직 방문하지 않은 정점u를 선택하고 만약 그러한 정점이 없다면 탐색은 종료된다.
아직 방문하지 않은 정점 u가 있다면 u를 시작 정점으로 깊이 우선 탐색을 다시 시작한다.

/* 깊이 우선 탐색 : 인접 행렬 */
void dfs_mat(GraphType *g,int v) 
{ 
int w; 

    visited[v]=true; // 정점v 방문 표시
    printf("%d-> ", v); // 방문한 정점 출력

for(w=0;w<g->n;w++) 
    { 
if(g->adj_mat[v][w] && !visited[w]) // 방문하지 않은 인접 정점 탐색
            dfs_mat(g,w); // 정점 w에서 DFS 새로 시작
    } 
} 

/* 깊이 우선 탐색 : 인접 리스트 */
void dfs_list(GraphType *g,int v) 
{ 
    GraphNode *w; 

    visited[v]=true; 
    printf("%d-> ",v); 

for(w=g->adj_list[v];w;w=w->link)  
    { 
if(!visited[w->vertex])  
            dfs_list(g,w->vertex); 
    } 
} 

# 너비 우선 탐색(breath first search : BFS)

너비 우선 탐색은 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는
순회 방법이다. 너비 우선 탐색을 위해서는 가까운 거리에 있는 정점들을 차례로 저장한 후 꺼낼 수 있는 큐가
필요하다. 즉, 정점들이 방문될 때마다 큐에 방문된 정점을 삽입하고, 더 이상 방문할 인접 정점이 없는 경우
큐의 앞에서 정점을 꺼내어 그 정점과 인접한 정점들을 모두 차례대로 방문하게 된다. 초기 상태의 큐에는 시작
정점만이 저장되고, 너비우선 탐색과정은 큐가 소진될 때까지 계속한다.

/* 너비 우선 탐색 : 인접 행렬 */
void bfs_mat(GraphType *g, int v) 
{   
int w; 
    QueueType q; 
    init(&q);     /* 큐 초기화 */
    visited[v] = TRUE;          // 정점 v 방문 표시 
    printf("%d ", v);            
    enqueue(&q, v);            // 시작 정점을 큐에 저장 
while(!is_empty(&q)){ 
         v = dequeue(&q);        // 큐에 정점 추출 
for(w=0; w<g->n; w++)    // 인접 정점 탐색 
if(g->adj_mat[v][w] && !visited[w]){  
               visited[w] = TRUE;    // 방문 표시
                  printf("%d ", w);    
                  enqueue(&q, w);     // 방문한 정점을 큐에 저장
         } 
    } 
} 

/* 너비 우선 탐색 : 인접 리스트 */
void bfs_list(GraphType *g, int v) 
{   
    GraphNode *w; 
    QueueType q; 
    init(&q);                    // 큐 초기 화 
    visited[v] = TRUE;      // 정점 v 방문 표시 
    printf("%d ", v);          // 방문한 정점 출력 
    enqueue(&q, v);            // 시작정점을 큐에 저장 
while(!is_empty(&q)){             
         v = dequeue(&q);        // 큐에 저장된 정점 선택 
for(w=g->adj_list[v]; w; w = w->link) //인접 정점 탐색
if(!visited[w->vertex]){    // 미방문 정점 탐색 
                visited[w->vertex] = TRUE;   // 방문 표시
                 printf("%d ", w->vertex);   
                 enqueue(&q, w->vertex);    //정점을 큐에 삽입
            } 
    } 
}