9. 그래프 - 그래프 탐색(DFS/BFS)

개념

• 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정
• 대표적인 그래프 탐색 알고리즘 DFS/BFS

 

재귀함수(Recursive Function)

• 자기 자신을 다시 호출하는 함수
  • 스택 구조로 함수들이 쌓임
  • 스택 구조로 함수가 쌓이기 떄문에 스택 자료구조 대신 재귀함수를 이용하는 경우가 있음
  • 모든 재귀함수는 반복문을 이용하여 동일한 기능 구현 가능
• 재귀 함수는 반드시 종료 조건을 설정 해야함

 

DFS(Depth-First Search)

깊이 우선 탐색

그래프가 있을때 방문 기준을 문제 조건을 잘 보고 설정 해야함

1. 탐색 노드를 스택에 삽입하고 방문 처리 진행
2. 방문 기준으로 다음 인접 노드를 스택에 넣고 방문 처리 진행
3. 위 과정 계속 

 

 

 

코드

주의!) 노드 연결시 양방향 그래프이면 서로 연결을 해줘야함

boolean[] visited = new boolean[9]; //탐색 노드 확인

//그래프 연결은 2차원 배열로 표현
ArryList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();


public static void dfs(int x) {
    visited[x] = true; //현재 노드 방문 처리
    System.out.print(x + " ");
    
    //현재 노드와 연결된 노드 탐색
    for (int i=0; i < graph.get(x).size(); i++){
    	int y = graph.get(x).get(i);
        if(!visited[y]) dfs(y);
    }
    
}


public static void main(String[] args) {
    // 그래프 초기화
    for (int i = 0; i < 9; i++) {
        graph.add(new ArrayList<Integer>());
    }

    // 노드 1에 연결된 노드 정보 저장 
    graph.get(1).add(2);
    graph.get(1).add(3);
    graph.get(1).add(8);

    // 노드 2에 연결된 노드 정보 저장 
    graph.get(2).add(1);
    graph.get(2).add(7);

    // 노드 3에 연결된 노드 정보 저장 
    graph.get(3).add(1);
    graph.get(3).add(4);
    graph.get(3).add(5);

    // 노드 4에 연결된 노드 정보 저장 
    graph.get(4).add(3);
    graph.get(4).add(5);

    // 노드 5에 연결된 노드 정보 저장 
    graph.get(5).add(3);
    graph.get(5).add(4);

    // 노드 6에 연결된 노드 정보 저장 
    graph.get(6).add(7);

    // 노드 7에 연결된 노드 정보 저장 
    graph.get(7).add(2);
    graph.get(7).add(6);
    graph.get(7).add(8);

    // 노드 8에 연결된 노드 정보 저장 
    graph.get(8).add(1);
    graph.get(8).add(7);

    dfs(1);
}

 

BFS(Breadth-First Search)

너비 우선 탐색

간선의 비용이 모두 동일할 때 최단거리 탐색할 때 활용

1.  시작 노드를 큐에 삽입하고 방문 처리를 진행
2. 큐에서 노드를 꺼낸 후, 해당 노드의 인접 노드 중 방문하지 않은 노드를 모두 큐에 삽입하여 방문 처리 진행
3. 반복

boolean[] visited = new boolean[9]; //탐색 노드 확인

//그래프 연결은 2차원 배열로 표현
ArryList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();


public static void bfs(int start) {
    Queue<Integer> q = new LinkedList<>();
    q.offer(start);
    
    visited[start] = true;
    
    while(!q.isEmpty()){
    	
        int x = q.poll();
        System.out.print(x + " ");
        
        for(int i=0; i<graph.get(x).size(); i++){
        	int y = graph.get(x).get(i);
            if(!vistied[y]) {
            	q.offer(y);
                visited[y] = true;
            }
        
        }
    
    }
}