BFS

while 문 BFS

#include <iostream>
using namespace std;
int head, last = 1, queue[10], map[6][6] = {
    0, 1, 1, 0, 0, 0,
    0, 0, 0, 1, 1, 0,
    0, 0, 0, 0, 0, 1,
}, name[6] = {0, 1, 3, 2, 4, 5};
int main()
{
    int now;
    queue[head] = 0;
    while(head != last)
    {
        now = head++;
        for(int i=0; i<6; i++)
        {
            if(map[now][i] == 1)
            {
                queue[last++] = name[i];
            }
        }
    }
    cout << queue[0] << ' ';
    for(int i=1; i<10; i++)
    {
        if(queue[i] != 0)
            cout << queue[i] << ' ';
    }
    return 0;
}

bfs 전체 탐색하기

#include <iostream>
using namespace std;
int head, tail = 1, map[6][6] = {
    0, 1, 1, 1, 0, 0,
    0, 0, 0, 0, 1, 0,
    0, 0, 0, 0, 0, 1,
}, queue[10];
char name[7] = "ABCDEA";

int main()
{
    queue[0] = 0;
    while(head != tail)
    {
        int now = queue[head++];
        
        for(int i=0; i<6; i++)
        {
            if(map[now][i] == 1)
            {
                queue[tail++] = i;
            }
        }
        cout << name[now] << ' ';
    }
    return 0;
}

구조체 배열을 통해 bfs 레벨까지 저장하기

#include <iostream>
using namespace std;
struct Node{
    int n;
    int level;
};
Node queue[7] = {{6, 0}};
int head, tail = 1, map[7][7] = {
    0, 0, 0, 0, 0, 0, 0,
    0, 0, 1, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 1, 0,
    0, 0, 0, 0, 0, 0, 0,
    1, 0, 0, 0, 1, 0, 0,
    0, 1, 0, 1, 0, 0, 0
};

int main()
{
    while (head != tail) {
        Node now = queue[head++];
        cout << now.n << ' ';
        for(int i=0; i<7; i++)
        {
            if(map[now.n][i] == 1)
            {
                queue[tail++] = {i, now.level+1};
            }
        }
    }
    return 0;
}

bfs로 트리 탐색하면서 레벨과 값 출력하기

#include <iostream>
using namespace std;
int map[5][5] = {
    0, 1, 1, 1, 0,
    0, 0, 0, 0, 0,
    0, 0, 0, 0, 0,
    0, 0, 0, 0, 1,
    0, 0, 0, 0, 0
}, head, tail = 1;
char name[6] = "BQRSB";
struct Node{
    int n;
    int level;
};
Node queue[5] = {{0, 0}};

int main()
{
    while (head != tail) {
        Node now = queue[head++];
        cout << name[now.n] << '(' << now.level << ")\n" ;
        for(int i=0; i<5; i++)
        {
            if(map[now.n][i] == 1)
            {
                queue[tail++] = {i, now.level+1};
            }
        }
    }
    return 0;
}

#include <iostream>
using namespace std;
int map[6][6] = {
    0, 1, 0, 1, 0, 1,
    0, 0, 1, 0, 1, 1,
    1, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 1, 0,
}, head, tail = 1, used[6], name[6] = {5, 4, 6, 1, 5, 3};
struct Node{
    int n, level;
};
Node queue[6] = { {0, 0}};
int main()
{
    used[0] = 1;
    while(head != tail)
    {
        Node now = queue[head++];
        cout << name[now.n] << ' ' << now.level << '\n';
        for(int i=0; i<6; i++)
        {
            if(map[now.n][i] == 1 && used[i] != 1)
            {
                used[i] = 1;
                queue[tail++] = {i, now.level+1};
            }
        }
    }
    return 0;
}

bfs에서 최단경로 (가중치가 없다고 가정)는 길을 찾은 순간 종료하면 그것이 최단 경로이다. 

왜냐하면 레벨 순서대로 큐에 쌓이기 때문이다.

또한 모든 경로를 탐색하는 것은 DFS로 하는 것이 좋다. 이것을 BFS로 하려면 메모리 낭비가 심하다.

 

bfs로 자기 자신과 조상 노드 다 출력하기

#include <iostream>
using namespace std;
int map[5][5] = {
    0, 1, 1, 0, 0,
    0, 0, 0, 0, 0,
    0, 0, 0, 1, 1,
}, head, tail = 1;
char name[6] = "ABCDE";
struct Node
{
    int n, level, parent;
};
Node queue[5];
int main()
{
    queue[0] = {0, 0, -1};
    while(head != tail)
    {
        Node now = queue[head++];
        for(int i=0; i<5; i++)
        {
            if(map[now.n][i] == 0) continue;
            queue[tail++] = {i, now.level+1, now.n};
        }
    }
    int p = 0;
    char alp;
    cin >> alp;
    for(int i=0; i<5; i++)
    {
        if(alp == name[i])
            p = i;
    }
    while(1)
    {
        cout << name[queue[p].n] << ' ';
        if(queue[p].parent == -1 ) break;
        p = queue[p].parent;
    }
    return 0;
}