10.BFS - C++

less than 1 minute read

10.BFS - C++



#include <iostream>
#include <stdio.h>

int n; // 정점의 최댓값
int rear, front; // 이전노드와 다음노드의 변수
int map[30][30], queue[30], visit[30]; // 인접행렬, 큐, 방문 배열

void BFS(int v)
{
    int i;
    visit[v] = 1; // 정점 v 방문을 표시
    printf("%d에서 시작\n",v);
    queue[rear++] = v; // 큐에 v를 삽입하고 이전노드를 1 증가시킴
    while(front < rear) // 다음노드와 이전노드가 같거나 작으면 루프탈출
    {
        // 큐의 첫번째 있는 데이터를 제외하고 제외된 값을 가져오며, 다음노드를 1증가
        v = queue[front++];
        for (i=1; i<=n;i++)
        {
            // 정점 v와 정점 i 가 만나고, 정점 i 를 방문하지 않은 상태인 경우
            if (map[v][i] == 1 && !visit[i])
            {
                visit[i] = 1; // 정점 i 방문 표시
                printf("%d에서 %d로 이동\n",v,i);
                queue[rear++] = i; // 큐에 i를 삽입하고 이전노드를 1 증가시킴
                
            }
        }
    }
}


int main(){
    int start; // 시작 정점을 나타내는 변수
    int v1,v2;
    scanf("%d%d",&n,&start);
    while(1)
    {
        scanf("%d%d",&v1,&v2);
        if (v1 == -1 && v2 == -1) break;
    }
    BFS(start);
    return 0;
}




Leave a comment