그래프 탐색(2) - BFS(너비우선탐색) 알고리즘

너비 우선 탐색(Breadth First Search : DFS)은 그래프의 특정 노드에서 시작하여 전체 노드를 탐색하는 알고리즘이다.

탐색을 할 때 시작 정점에서 인접한 노드를 먼저 탐색하여, 가까운 정점을 먼저 방문하고 멀리 떨어진 정점을 나중에 방문하는 방식을 가진다. level을 높여가면서 각각의 정점을 탐색해나가는 알고리즘이다.

알고리즘 구현 방식에는 큐를 사용한다.

정점의 수가 n이고, 간선의 수가 e인 그래프의 경우 시간복잡도

- 인접 행렬로 표현된 경우, 시간복잡도는 O(n^2)

- 인접 리스트로 표현된 경우, 시간복잡도는 O(n+e)

 

** 그래프의 크기가 작을 경우, BFS가 더 유리함

 

(알고리즘 구현) 재귀 함수 - 인접 행렬(이차원 배열)로 구현했을 때. 

 아래와 같은 그래프(트리)가 존재할 때, 행렬에서 간선이 존재하는 부분은 1로 변경해준다.

(** 트리도 그래프의 일종이다.)

import java.util.*;

public class Graph {
   public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
		
        System.out.println("정점의 개수를 입력하시오.");
        int V = s.nextInt();       // 정점의 개수 
        boolean[] check = new boolean[V];
		
        int graph[][] = new int[V][V];
        int v1 = 0, v2 = 0;
        while(true){
                System.out.println("연결된 정점을 입력하시오.");
                v1 = s.nextInt();
                v2 = s.nextInt();
			
                if(v1 != -1 || v2 != -1) {
                  if(v1>=0 && v2>=0 && v1<=V && v2<=V) {
                     graph[v1][v2] = 1;
                     graph[v2][v1] = 1;
                  }else
                     break;
                }
                else
                  break;
        }
        int start = 0; 	// 시작 정점
        bfs(graph, check, start);
   }
	
   public static void bfs(int[][] graph, boolean[] check, int v) {
		
        // 방문하지 않은 정점이라면 큐에 넣기
        Queue<Integer> queue = new LinkedList<>();
        queue.add(v);
        check[v] = true;
        System.out.print(v + " ");
		
        while(!queue.isEmpty()) {
                int now = queue.poll();
			
                for(int i=0; i<graph.length; i++) {
				
                  // 인접한 정점들 중에서 방문하지 않는 정점들 큐에 넣기
                  if(!check[i] && graph[now][i] == 1) {
                     System.out.print(i + " ");
                     queue.add(i);
                     check[i] = true;
                  }
                }
        }
   }
}

 

 

(알고리즘 구현) 재귀 함수 - 인접 리스트(LinkedList)로 구현했을 때. 

 아래와 같은 그래프(트리)가 존재할 때, 연결된 간선이 존재할 경우에 연결 리스트에 정점을 입력해준다.

package 프로그래머스;

import java.util.*;

public class Graph {
	   public static void main(String[] args) {
	       Scanner s = new Scanner(System.in);
			
	        System.out.println("정점의 개수를 입력하시오.");
	        int V = s.nextInt();       // 정점의 개수 
	        boolean[] check = new boolean[V];
			
	       LinkedList<Integer>[] graph = new LinkedList[V];
	       for(int i=0; i<V; i++)
	              graph[i] = new LinkedList<Integer>();
			
	       int v1 = 0, v2 = 0;
	       while(true) {
	              System.out.println("연결된 정점을 입력하시오.");
	            
	              v1 = s.nextInt();
	              v2 = s.nextInt();

	              if(v1 != -1 || v2 != -1) {
	                if(v1>=0 && v2>=0 && v1<=V && v2<=V) {
	                   graph[v1].add(v2);
	                   graph[v2].add(v1);
	                }else
	                   break;
	              }
	              else
	                break;
	       }
			
	       // 방문 순서 정렬
	       for(int i=0; i<V; i++)
	              Collections.sort(graph[i]);
			
	       int start = 0; 	// 시작 정점
	       bfs(graph, check, start);	
	   }
		
	   public static void bfs(LinkedList<Integer>[] graph, boolean[] check, int v) {
	       
	        // 방문하지 않은 정점이라면 큐에 넣기
	        Queue<Integer> queue = new LinkedList<>();
	        queue.add(v);
	        check[v] = true;
	        System.out.print(v + " ");
			
	        while(!queue.isEmpty()) {
	                int now = queue.poll();
				
	                Iterator<Integer> it = graph[now].listIterator();
	                while(it.hasNext()) {
	                	int w = it.next();
	                	if(!check[w]) {
	                		check[w] = true;
	                		queue.add(w);
	            	        System.out.print(w + " ");
	                	}
	                }
	        }
	   }
}