[Algorithm] BFS (너비우선탐색)

 

 

출처: https://990427.tistory.com/25

 

 

 

출처: https://www.codesdope.com/course/algorithms-bfs/

 

 

 

 

출처: https://www.codesdope.com/course/algorithms-bfs/

 

 

 

** C++

 

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

int number = 7;
int visited[7];
vector<int> arr[8];

void bfs(int start) {
	queue<int> q;
	q.push(start);
	visited[start] = true;
	while (!q.empty()) {
		int x = q.front();
		q.pop();
		printf("%d ", x);
		for (int i = 0; i < arr[x].size(); i++) {
			int y = arr[x][i]; // 인접한 노드 방문 
			if(!visited[y]) { // 방문한 상태가 아니라면 
				q.push(y); // 담아주고 
				visited[y] = true; // 방문처리 
			}
		}
	}
}

int main(void) {
	arr[1].push_back(2);
	arr[2].push_back(1);
	
	arr[1].push_back(3);
	arr[3].push_back(1);
	
	arr[2].push_back(3);
	arr[3].push_back(2);
	
	arr[2].push_back(4);
	arr[4].push_back(2);
	
	arr[2].push_back(5);
	arr[5].push_back(2);

	arr[4].push_back(5);
	arr[5].push_back(4);
	
	arr[3].push_back(6);
	arr[6].push_back(3);
	
	arr[3].push_back(7);
	arr[7].push_back(3);
	
	arr[6].push_back(7);
	arr[7].push_back(6);
	
	bfs(1); // 시작점 1 
	return 0; 
}

 

 

 

** Javascript

 

let visited = [];
let arr = new Array(8).fill([]);

function bfs(start) {
    let queue = [];
    queue.push(start);
    visited[start] = true;
    while (queue.length > 0) {
        let x = queue[0];
        queue.shift();
        console.log(x);
        for (let i = 0; i < arr[x].length; i++) {
            let y = arr[x][i];
            if(!visited[y]) {
                queue.push(y);
                visited[y] = true;
            }
        }
    }
}

arr[1].push(2);
arr[2].push(1);

arr[1].push(3);
arr[3].push(1);

arr[2].push(3);
arr[3].push(2);

arr[2].push(4);
arr[4].push(2);

arr[2].push(5);
arr[5].push(2);

arr[4].push(5);
arr[5].push(4);

arr[3].push(6);
arr[6].push(3);

arr[3].push(7);
arr[7].push(3);

arr[6].push(7);
arr[7].push(6);

bfs(1);

 

 

** Java (수정중)

 

참고: https://ldgeao99.tistory.com/387

 

import java.util.*;

public class Main
{
    private static  int number = 7;
    private static boolean[] visited;
    private static ArrayList<Integer>[] arr;
    private static void bfs(int start) {
        Queue<Integer> q = new LinkedList<Integer>();
        q.offer(start);
        visited[start] = true;
        while(!q.isEmpty()) {
            int x = q.poll();
            System.out.printf("%d ", x);
            for (int y : arr[x]) {
                if (visited[y] == false) {
                    visited[y] = true;
                    q.add(y);
                }
            }
        }
    }
    private static void dfs(int top) {
        if (visited[top]) {
            return;
        }
        visited[top] = true;
        System.out.printf("%d ", top);
        for (int y : arr[top]) {
            if (visited[y] == false) {
                dfs(y);
            }
        }
    }
	public static void main(String[] args) {
	    arr = (ArrayList<Integer>[]) new ArrayList[number+1];
        for (int i=1; i<=number; i++) {
            arr[i] = new ArrayList<Integer>();
        }
        
		arr[1].add(2);
		arr[2].add(1);
		
		arr[1].add(3);
		arr[3].add(1);
		
		arr[2].add(3);
		arr[3].add(2);
		
		arr[2].add(4);
		arr[4].add(2);
		
		arr[2].add(5);
		arr[5].add(2);
		
		arr[4].add(5);
		arr[5].add(4);
		
		arr[3].add(6);
		arr[6].add(3);
		
		arr[3].add(7);
		arr[7].add(3);
		
		arr[6].add(7);
		arr[7].add(6);
		
		bfs(1);
	}
}