[DFS] 인접행렬

김성수·2023년 5월 26일

알고리즘

목록 보기

21/28

들어가면서

그래프 문제를 풀 때 인접행렬이 사용될 수 있다.
인접행렬이 무엇이고, 어떨 때 사용할 수 있는지 정리해보려한다.

인접행렬이란?

인접행렬은 그래프의 노드간의 간선 정보를 2차원 배열로 담는 방식을 의미한다.

쉽게 말해서 A, B, C라는 노드가 존재할 때,

A -> B
A -> C
C -> B

위와 같은 간선 정보가 존재한다면

아래와 같이 초기화 될 수 있다.

g[A][B] = 1
g[A][C] = 1
g[C][B] = 1

반면에 , 간선 정보가 없는 경우 아래와 같이 0으로 초기화 된다

g[B][A] = 0
g[B][C] = 0
g[C][A] = 0

위 방식은 방향 그래프일 경우이고 무방향의 경우 왕복이 가능하다.

따라서,

g[A][B] = 1
g[A][C] = 1
g[C][B] = 1
g[B][A] = 1
g[B][C] = 1
g[C][A] = 1

위처럼 A - B로 갔을 때 B - A로 갈 수 있고, C - A로 갔을 때, A - C로 갈 수 있다.

인접행렬 방식은 노드의 수는 많지만, 간선의 수가 적을 때 좋지 않다.

예를 들어, 노드의 수가 만개인데, 간선의 수가 5개라면 만개의 노드를 모두 탐색해야 하기 때문에

불필요한 연산이 발생한다.

인접행렬 사용 예시

문제 : 방향 그래프가 주어졌을 때 1번에서 모든 정점으로 가는 경우의 수를 구하시오

아래는 코드

//인접행렬 초기화
int[][] graph = new int[n+1][n+1]; // n = 노드 수

for(int i = 0; i < m; i++){ // m = 간선 수
	int a = in.nextInt();
    int b = in.nextInt();
    graph[a][b] = 1;
}


// 모든 경로의 수 구하기(DFS)
public void DFS(int v){ // v = 시작 정점
	if(v == n) answer++; // answer = 경우의 수
    else{
    	for(int i = 1; i <= n; i++){
        	if(graph[v][i] == 1 && ch[i] == 0){
            	ch[i] = 1;
                DFS(i);
                ch[i] = 0;
            }
        }
}