10.BFS - C++
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