행렬을 이용한 BFS

#2019-08-20
#include<stdio.h>

int n; // 정점의 최댓값 
int rear, front; // 앞쪽과 뒤쪽을 나티내는 변수 
int map[30][30]; // 인접 행렬  
int queue[30]; // 큐  
int 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;
	
	printf("정점의 총 개수와 시작 정점을 입력하세요.:");
	scanf("%d%d", &n, &start);
	
	while (1) {
		printf("연결할 두 정점을 입력하세요.(예 3 4):");
		scanf("%d%d", &v1, &v2);
		if (v1 == -1 && v2 == -1) break; // 입력 종료  
		map[v1][v2] = map[v2][v1] = 1; //정점 v1과 장점 v2가 연결되었다고 표시  
	}
	BFS(start); // BFS 시작  
	
	return 0;
}

/*

정점의 총 개수와 시작 정점을 입력하세요.:8 0
연결할 두 정점을 입력하세요.(예 3 4):0 1
연결할 두 정점을 입력하세요.(예 3 4):0 2
연결할 두 정점을 입력하세요.(예 3 4):1 0
연결할 두 정점을 입력하세요.(예 3 4):1 3
연결할 두 정점을 입력하세요.(예 3 4):1 4
연결할 두 정점을 입력하세요.(예 3 4):2 0
연결할 두 정점을 입력하세요.(예 3 4):2 5
연결할 두 정점을 입력하세요.(예 3 4):2 6
연결할 두 정점을 입력하세요.(예 3 4):3 2
연결할 두 정점을 입력하세요.(예 3 4):3 7
연결할 두 정점을 입력하세요.(예 3 4):4 1
연결할 두 정점을 입력하세요.(예 3 4):4 7
연결할 두 정점을 입력하세요.(예 3 4):5 2
연결할 두 정점을 입력하세요.(예 3 4):5 7
연결할 두 정점을 입력하세요.(예 3 4):6 2
연결할 두 정점을 입력하세요.(예 3 4):6 7
연결할 두 정점을 입력하세요.(예 3 4):7 3
연결할 두 정점을 입력하세요.(예 3 4):7 4
연결할 두 정점을 입력하세요.(예 3 4):7 5
연결할 두 정점을 입력하세요.(예 3 4):7 6
연결할 두 정점을 입력하세요.(예 3 4):-1 -1
0에서 시작
0에서 1로 이동
0에서 2로 이동
1에서 3로 이동
1에서 4로 이동
2에서 5로 이동
2에서 6로 이동
3에서 7로 이동

--------------------------------
Process exited after 84.58 seconds with return value 0
계속하려면 아무 키나 누르십시오 . . .

*/