[알고리즘/자료구조] BFS, 넓이우선탐색 (Breadth First Search)

넓이우선탐색 (BFS, Breadth First Search)

너비 우선 탐색(Breadth-first search, BFS)은 맹목적 탐색방법의 하나로 시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법이다. 더 이상 방문하지 않은 정점이 없을 때까지 방문하지 않은 모든 정점들에 대해서도 너비 우선 검색을 적용한다. OPEN List 는 큐를 사용해야만 레벨 순서대로 접근이 가능하다.

https://has3ong.tistory.com/54

Graph 소스 가져왔습니다.

소스

/*    
/*    khsh5592@naver.com
/*    has3ong.tistory.com
/*    
/*    2018 - 12 - 11
/*
*/
 
#include "graph.h"
 
#include <stdio.h>
#include <iostream>
#include <conio.h>
#include <queue>
 
using namespace std;
 
void initialize(Graph* G)
{
    Vertex* vertex0 = vertex_Create(0, 0);
    Vertex* vertex1 = vertex_Create(1, 1);
    Vertex* vertex2 = vertex_Create(2, 2);
    Vertex* vertex3 = vertex_Create(3, 3);
    Vertex* vertex4 = vertex_Create(4, 4);
    Vertex* vertex5 = vertex_Create(5, 5);
    Vertex* vertex6 = vertex_Create(6, 6);
    Vertex* vertex7 = vertex_Create(7, 7);
 
    add_Vertex(G, vertex0);
    add_Vertex(G, vertex1);
    add_Vertex(G, vertex2);
    add_Vertex(G, vertex3);
    add_Vertex(G, vertex4);
    add_Vertex(G, vertex5);
    add_Vertex(G, vertex6);
    add_Vertex(G, vertex7);
 
    Edge* edge0 = edge_Create(vertex0, vertex1, 0);
    Edge* edge1 = edge_Create(vertex0, vertex5, 0);
    Edge* edge2 = edge_Create(vertex0, vertex7, 0);
 
    Edge* edge3 = edge_Create(vertex1, vertex0, 0);
    Edge* edge4 = edge_Create(vertex1, vertex4, 0);
    Edge* edge5 = edge_Create(vertex1, vertex6, 0);
 
    Edge* edge6 = edge_Create(vertex2, vertex3, 0);
    Edge* edge7 = edge_Create(vertex2, vertex4, 0);
    Edge* edge8 = edge_Create(vertex2, vertex7, 0);
 
    Edge* edge9 = edge_Create(vertex3, vertex2, 0);
    Edge* edge10 = edge_Create(vertex3, vertex5, 0);
    Edge* edge11 = edge_Create(vertex3, vertex6, 0);
 
    Edge* edge12 = edge_Create(vertex4, vertex1, 0);
    Edge* edge13 = edge_Create(vertex4, vertex2, 0);
 
    Edge* edge14 = edge_Create(vertex5, vertex0, 0);
    Edge* edge15 = edge_Create(vertex5, vertex3, 0);
 
    Edge* edge16 = edge_Create(vertex6, vertex1, 0);
    Edge* edge17 = edge_Create(vertex6, vertex3, 0);
 
    Edge* edge18 = edge_Create(vertex7, vertex0, 0);
    Edge* edge19 = edge_Create(vertex7, vertex2, 0);
 
    add_Edge(vertex0, edge0);
    add_Edge(vertex0, edge1);
    add_Edge(vertex0, edge2);
    add_Edge(vertex1, edge3);
    add_Edge(vertex1, edge4);
    add_Edge(vertex1, edge5);
    add_Edge(vertex2, edge6);
    add_Edge(vertex2, edge7);
    add_Edge(vertex2, edge8);
    add_Edge(vertex3, edge9);
    add_Edge(vertex3, edge10);
    add_Edge(vertex3, edge11);
    add_Edge(vertex4, edge12);
    add_Edge(vertex4, edge13);
    add_Edge(vertex5, edge14);
    add_Edge(vertex5, edge15);
    add_Edge(vertex6, edge16);
    add_Edge(vertex6, edge17);
    add_Edge(vertex7, edge18);
    add_Edge(vertex7, edge19);
}
 
void BFS(Vertex* V)
{
    queue<Vertex*>Q;
    
    Edge* E = NULL;
 
    V -> visit = true;
    E = V -> edge_list;
    cout << " " << V -> index;
    Q.push(V);
 
    while(!Q.empty())
    {
        V = Q.front();
        Q.pop();
 
        E = V -> edge_list;
        
        while ( E != NULL)
        {
            V = E -> to;
            if ( V != NULL && V -> visit == false)
            {
                cout << " " << V -> index;
                V -> visit = true;
                Q.push(V);
            }
 
            E = E -> next;
        }
    }
}
 
void main()
{
    Graph* BFS_G = new Graph();
    Vertex* BFS_V = new Vertex();
 
    initialize(BFS_G);
 
    BFS_V = BFS_G -> Vertex_list;
 
    BFS(BFS_V);
    getch();
}

결과화면

출처

위키피디아

https://en.wikipedia.org/wiki/Breadth-first_search