[DFS] 인접 행렬, 인접 리스트

세가지 그래프

방향 그래프

무방향 그래프

가중치 그래프

 

인접 행렬

문제 유형

1) 방향그래프가 주어지고 1번에서 N번으로 가는 모든 경로의 가지 수를 구하시오.

필요 자료구조

- 중복 탐색을 방지하기 위한 check 배열, check 배열은 n+1 크기를 갖는다(1 ~ n)

- 간선 설정을 위한 graph 2차원 배열(행, 열 모두 n+1 크기)

- n개의 정점과, m개의 간선 수 설정

- 문제를 해결하기 위한 DFS 메서드 구현 로직

 

핵심 로직

public void DFS(int val){
	if(val = n) answer++;
    else{
    	for(int i = 1; i <= n; i++){
        	if(graph[v][i] == 1 && ch[i] == 0){
            	ch[i] = 1;
                DFS(i+1);
                ch[i] = 0; // 백트래킹
            }
        }
    }
}

 

인접리스트

문제 유형

1) 방향그래프가 주어지고 1번에서 N번으로 가는 모든 경로의 가지 수를 구하시오.

 

장점 ) 인접 행렬보다 시간복잡도가 낮다.

 

필요 자료구조

- 중복 탐색을 방지하기 위한 check 배열

- 간선 설정을 위한 graph ArrayList 초기화

ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayLst>();

for(int i = 0; i <= n; i++){ // 정점 수 만큼 초기화
	graph.add(new ArrayList<Integer>);
}

for(int i = 0; i < m; i++){ // 간선 들 초기화
  	int a = in.nextInt();
	int b = in.nextInt();

    graph.get(a).add(b);
}

- n개의 정점과, m개의 간선 수 설정

- 문제를 해결하기 위한 DFS 메서드 구현 로직

public void DFS(int val){
        if(val == n) answer++;
        else{
            for(int nx : graph.get(val)){
                if(ch[nx] == 0) {
                    ch[nx] = 1;
                    DFS(nx);
                    ch[nx] = 0;
                }
            }
        }
    }