Typiler

동작방식

하나로 시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법입니다. 더 이상 방문하지 않은 정점이 없을 때까지 방문하지 않은 모든 정점들에 대해서도 너비 우선 검색을 적용합니다.

장점

• 출발노드에서 목표노드까지의 최단 길이 경로를 보장한다.

단점

• 경로가 매우 길 경우에는 탐색 가지가 급격히 증가함에 따라 보다 많은 기억 공간을 필요로 하게 된다.
• 해가 존재하지 않는다면 유한 그래프(finite graph)의 경우에는 모든 그래프를 탐색한 후에 실패로 끝난다.
• 무한 그래프(infinite graph)의 경우에는 결코 해를 찾지도 못하고, 끝내지도 못한다.

시간복잡도

DFS 시간복잡도와 동일함

- 인접리스트 : O(|V| + |E|) (정점의 개수:V, 간선의 개수:E)

- 인접행렬 : O(V^2) (정점의 개수:V)

참고사이트

https://ko.wikipedia.org/wiki/%EB%84%88%EB%B9%84_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89

기본코드

입력값

코드

package study.graph;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class BFS {

	static int[] used;
	static int[][] map;
	static int N, M;
	public static void main(String[] args) throws IOException{
		
		System.setIn(new FileInputStream("input\\bfs.txt"));
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		N = Integer.parseInt(br.readLine());
		M = Integer.parseInt(br.readLine());
		
		used = new int[N+1];
		map = new int[N+1][N+1]; // 인접행렬을 이용하기 위한 2차원 배열 생성
		
		StringTokenizer st = null;
		for(int m=0; m<M; m++) {
			st = new  StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			
			map[a][b] = 1;
			map[b][a] = 1; //양방향이기 때문에..
		}
		
		System.out.print("그래프 BFS 방문 순서 : " );
		bfs(1);
		
		bw.close();
		br.close();
	}
	
	static void bfs(int st) {
		Queue<Integer> q = new LinkedList<Integer>();
		q.add(st);
		used[st] = 1; //방문표시
		
		while(!q.isEmpty()) {
			int x = q.poll();
			System.out.print( x + " ");
			
			for(int i=1; i<=N; i++) {
				if(map[x][i] == 1 && used[i] == 0) {
					// 다음 노드와 연결되어 있고 아직 방문하지 않았으면 q에 넣음
					q.add(i);
					used[i] = 1;//방문 표시
				}
			}
		}
	}
}

인접 리스트는 그래프 이론에서 그래프를 표현하기 위한 방법 중 하나입니다. 그래프의 한 꼭짓점에서 연결되어 있는 꼭짓점들을 하나의 연결 리스트로 표현하는 방법입니다. 인접 행렬에 비하여 변이 희소한 그래프에 효율적 입니다.

동작방식

아래와 같은 그래프가 존재할때 인접행렬을 만들어 보겠습니다. 1노드에서 시작하여 2,3 노드로 연결됩니다. 그리고 3노드는 2,4 노드로 연결됩니다. 이는 단방향을 나타내고 있음을 알수 있습니다. 2차원 배열을 준비하고 배열의 Y축을 시작 좌표, 배열의 X축을 그래프가 향하는 노드라고 생각을하고 아래 그림과 같이 만들어 사용을 합니다.

참고사이트

https://ko.wikipedia.org/wiki/%EC%9D%B8%EC%A0%91_%EB%A6%AC%EC%8A%A4%ED%8A%B8

기본코드

위 그래프를 만드는 방법과 간단히 순환하는 순서를 나타내는 코드입니다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;

public class Test {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    static ArrayList<ArrayList<Integer>> alist = new ArrayList<ArrayList<Integer>>();

    static void run(int now)
    {
        System.out.print(now + " ");

        for (int i = 0; i<alist.get(now).size(); i++) {
            run(alist.get(now).get(i));
        }
    }

    public static void main(String[] args) throws IOException {        

        for (int i = 0; i < 5; i++) {
            alist.add(new ArrayList<>());
        }

        alist.get(1).add(2);
        alist.get(1).add(3);
        alist.get(3).add(2);
        alist.get(3).add(4);

        run(1);

        br.close();
        bw.close();        
    }
}

결과는 "1 2 3 2 4 "로 나타납니다.