그래프 탐색

트리(그래프, 2차원 배열) 순회(탐색)은 모든 자료(노드, 정점)을 빠짐 없이 탐색하는 것을 의미한다.

깊이 우선 탐색(Depth First Search, DFS)

• 루트 노트(시작 정점, 출발 위치)에서 출발하여 한 방향으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색해 더 이상 갈 곳이 없게 되면, 가장 마지막에 만났던 갈림길 간선이 있는 노드(정점)로 되돌아와서 다른 방향의 노드(정점)으로 탐색을 계속 반복하여 결국 모든 노드(정점)을 방문하는 순회방법
• 가장 마지막에 만났던 갈림길의 노드(정점)로 되돌아가서 다시 깊이 우선 탐색을 반복해야 하므로 후입선출 자료구조인 스택 사용
• 재귀 함수는 시스템 스택을 이용하므로 이를 이용하여 간단하게 구현할 수도 있음.

문제 유형

• 경로 탐색 : 두  정점 사이의 경로를 찾거나, 그래프 내 모든 경로를 찾는 문제에서 사용됩니다.
• 연결 요소 찾기 : 그래프 내 서로 연결된 그룹(연결 요소)을 찾는 문제에서 사용됩니다.
• 사이클 찾기 : 그래프 내에 사이클이 존재하는지 확인하는 문제에서 사용됩니다.
• 백트래킹 : 특정 조건을 만족하는 모든 해를 찾는 문제(예: N-Queen 문제)에서 사용됩니다.
• 트리에서의 특정 정점 순회 문제 : 트리에서 특정 순서로 정점을 방문하는 문제에서 사용됩니다.(예: 전위, 중위, 후위 순회)

package day0328_그래프탐색;

public class 그래프01_DFS {
	static int N = 7;
	//인접행렬
	static int[][] adj = { 
			{ 0, 1, 1, 0, 0, 1, 0 }, 
			{ 1, 0, 0, 1, 0, 0, 1 }, 
			{ 1, 0, 0, 1, 0, 0, 0 },
			{ 0, 1, 1, 0, 0, 0, 1 },
			{ 0, 0, 0, 0, 0, 1, 1 },
			{ 1, 0, 0, 0, 1, 0, 0 }, 
			{ 0, 1, 0, 1, 1, 0, 0 } };
	
	static boolean[] visited = new boolean[N]; //박문철2할 배열
	
	public static void main(String[] args) {
		DFS(0);
	}
	
	static void DFS(int v) {
		// v에 대한 방문처리를 하겠다.
		visited[v] = true;
		System.out.println(v+1);
		//나와 연결되어 있으면서 (간선이 존재하면서) 아직 방문하지 않은 정점을 재귀호출
		for(int i = 0; i<N; i++) {
			//방문하지 않았고 / 간선이 존재하면
			if(!visited[i] && adj[v][i] == 1) {
				 DFS(i);
			}
		} 
	}
}
//
1
2
4
3
7
5
6

너비 우선 탐색(Breadth First Search, BFS)

• 탐색 루트 노드(시작 정점, 출발 위치)의 자식 노드(인접한 정점)들을 먼저 차례로 방문한 후에 방문했던 자식 노드들(인접한 정점)을 시작점으로 하여 다시 해당 노드의 자식 노드(인접한 정점)들을 차례로 방문하는 방식
• 자식 노드(인접한 정점)들에 대해 탐색을 한 후, 차례로 다시 너비 우선 탐색을 진행해야 하므로, 선입선출 형태의 자료구조인 큐를 활용함
• 인접한 노드들부터 차례대로 방문을 하므로 시작 정점과 끝 정점이 주어졌을 때 최단 길이를 구할 수 있음

문제 유형

• 최단 경로 찾기 : 두 정점 사이의 최단 경로를 찾는 문제에서 사용됩니다. 특히, 가중치가 없거나 동일한 가중치를 갖는 간선으로 구성된 그래프에서 효과적입니다.
• 최소 비용 문제 : 최소 비용으로 목표를 달성하는 문제에서 사용됩니다.
• 최소 이동 횟수 문제 : 그래프 내 정점들의 레벨(시작 정점으로부터의 거리)을 구하는 문제에서 사용됩니다.
• 연결 요소 찾기 : 그래프 내 서로 연결된 정점들의 그룹(연결 요소)을 찾는 문제에서 사용됩니다.(DFS로도 해결 가능)

package day0328_그래프탐색;

import java.util.LinkedList;
import java.util.Queue;

public class 그래프02_BFS {
	static int N = 7;
	//인접행렬
	static int[][] adj = { 
			{ 0, 1, 1, 0, 0, 1, 0 }, 
			{ 1, 0, 0, 1, 0, 0, 1 }, 
			{ 1, 0, 0, 1, 0, 0, 0 },
			{ 0, 1, 1, 0, 0, 0, 1 },
			{ 0, 0, 0, 0, 0, 1, 1 },
			{ 1, 0, 0, 0, 1, 0, 0 }, 
			{ 0, 1, 0, 1, 1, 0, 0 } };
	
	static boolean[] visited = new boolean[N]; //박문철2할 배열
	static Queue<Integer> queue = new LinkedList<>();
	
	public static void main(String[] args) {
		BFS(0);
	}
	
	static void BFS(int v) {
		//시작 정점을 큐에 넣는다. 
		queue.add(v);
		visited[v] = true; // 박문철2한다.		
		
		//큐가 공백이 될때까지 반복문 수행
		//큐가 공백이 아니라면 반복문 수행
		while(!queue.isEmpty()) {
			//정점을 하나 꺼내
			int curr = queue.poll();
			System.out.print(curr+"->");
			
			//나와 연결되어 있으면서 방문하지 않은 친구들을 Q에 넣는다.
			for(int i= 0 ; i<adj.length; i++) {
				if(!visited[i] && adj[curr][i] == 1) {
					queue.add(i);
					visited[i] = true;
				}
			}
		}	
	}
}
//
0->1->2->5->3->6->4->

문제 :

다음은 연결되어 있는 두 개의 정점 사이의 간선을 순서대로 나열 해 놓은 것이다. 모든 정점을 탐색하여 화면에 경로를 출력하시오.(시작 정점을 1로 시작하시오.)

정점의 수 : 7

간선의 수 : 8

1 2 1 3 2 4 2 5 4 6 5 6 6 7 3 7

//DFS
package day0328_그래프탐색;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class dfs연습3 {
    static int N, line; // 정점의 개수 N, 간선의 개수 line
    static List<List<Integer>> adjList; // 인접 리스트로 그래프를 표현할 변수
    static boolean[] visit; // 정점 방문 여부를 저장할 변수

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt(); // 정점의 개수 입력
        line = sc.nextInt(); // 간선의 개수 입력

        // 인접 리스트 초기화
        adjList = new ArrayList<>();
        for (int i = 0; i <= N; i++) {
            adjList.add(new ArrayList<>());
        }

        visit = new boolean[N + 1]; // 방문 여부 배열 초기화

        // 간선 정보 입력
        for (int i = 0; i < line; i++) {
            int y = sc.nextInt(); // 한 정점 입력
            int x = sc.nextInt(); // 다른 정점 입력

            // 인접 리스트에 간선 추가
            adjList.get(y).add(x);
            adjList.get(x).add(y);
        }

        dfs(1); // 정점 1에서 시작하는 DFS 실행
    }

    // DFS 알고리즘 구현
    private static void dfs(int v) {
        visit[v] = true; // 정점 v 방문 처리
        System.out.print(v + "->"); // 정점 v 출력

        // 인접 리스트를 사용하여 현재 정점과 연결된 정점들 확인
        for (int i : adjList.get(v)) {
            // 방문하지 않은 정점이라면
            if (!visit[i]) {
                dfs(i); // DFS 재귀 호출
            }
        }
    }
}

BFS
package day0328_그래프탐색;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;

public class bfs연습3 {
    static int N, line; // 정점의 개수 N, 간선의 개수 line
    static List<List<Integer>> adjList; // 인접 리스트로 그래프를 표현할 변수
    static boolean[] visit; // 정점 방문 여부를 저장할 변수

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt(); // 정점의 개수 입력
        line = sc.nextInt(); // 간선의 개수 입력

        // 인접 리스트 초기화
        adjList = new ArrayList<>();
        for (int i = 0; i <= N; i++) {
            adjList.add(new ArrayList<>());
        }

        visit = new boolean[N + 1]; // 방문 여부 배열 초기화

        // 간선 정보 입력
        for (int i = 0; i < line; i++) {
            int y = sc.nextInt(); // 한 정점 입력
            int x = sc.nextInt(); // 다른 정점 입력

            // 인접 리스트에 간선 추가
            adjList.get(y).add(x);
            adjList.get(x).add(y);
        }

        bfs(1); // 정점 1에서 시작하는 BFS 실행
    }

    // BFS 알고리즘 구현
    private static void bfs(int v) {
        Queue<Integer> q = new LinkedList<>(); // 방문할 정점을 저장할 큐 생성
        q.add(v); // 시작 정점 v를 큐에 추가
        visit[v] = true; // 시작 정점 방문 처리

        // 큐가 비어있지 않은 동안 계속해서 BFS 실행
        while (!q.isEmpty()) {
            int curr = q.poll(); // 큐에서 현재 정점을 꺼냄
            System.out.print(curr + "->"); // 현재 정점 출력

            // 인접 리스트를 사용하여 현재 정점과 연결된 정점들 확인
            for (int i : adjList.get(curr)) {
                // 방문하지 않은 정점이라면
                if (!visit[i]) {
                    q.add(i); // 큐에 추가
                    visit[i] = true; // 방문 처리
                }
            }
        }
    }
}