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

인접행렬과 인접리스트에 대해 시각적으로 이해할 수 있는 예시와 더 구체적인 설정을 추가하겠습니다.

 

1. 인접행렬 (Adjacency Matrix)

 

문제 설정

 

노드 4개로 구성된 무방향 그래프를 생각해 봅시다.

노드와 간선 정보는 다음과 같습니다:

 

• 노드:  0, 1, 2, 3 

• 간선:

• 0  —  1 

• 1  —  2 

• 2  —  3 

 

시각적 예시

 

그래프를 그림으로 표현하면:

0 — 1 — 2 — 3

 

인접행렬로 표현

 

이 그래프의 인접행렬은 다음과 같습니다:

	0	1	2	3
0	0	1	0	0
1	1	0	1	0
2	0	1	0	1
3	0	0	1	0

 

Java 코드 구현

public class AdjacencyMatrixExample {
    public static void main(String[] args) {
        int n = 4; // 노드 개수
        int[][] adjMatrix = new int[n][n];

        // 간선 추가
        adjMatrix[0][1] = 1;
        adjMatrix[1][0] = 1;

        adjMatrix[1][2] = 1;
        adjMatrix[2][1] = 1;

        adjMatrix[2][3] = 1;
        adjMatrix[3][2] = 1;

        // 행렬 출력
        System.out.println("Adjacency Matrix:");
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                System.out.print(adjMatrix[i][j] + " ");
            }
            System.out.println();
        }
    }
}

 

출력

Adjacency Matrix:
0 1 0 0 
1 0 1 0 
0 1 0 1 
0 0 1 0

 

2. 인접리스트 (Adjacency List)

 

문제 설정

 

같은 그래프를 인접리스트로 표현해 봅시다.

 

시각적 예시

 

인접리스트는 각 노드마다 연결된 노드들을 리스트 형태로 나타냅니다:

 

• 노드  0 : [1]

• 노드  1 : [0, 2]

• 노드  2 : [1, 3]

• 노드  3 : [2]

 

Java 코드 구현

import java.util.ArrayList;

public class AdjacencyListExample {
    public static void main(String[] args) {
        int n = 4; // 노드 개수
        ArrayList<ArrayList<Integer>> adjList = new ArrayList<>();

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

        // 간선 추가
        adjList.get(0).add(1);
        adjList.get(1).add(0);

        adjList.get(1).add(2);
        adjList.get(2).add(1);

        adjList.get(2).add(3);
        adjList.get(3).add(2);

        // 리스트 출력
        System.out.println("Adjacency List:");
        for (int i = 0; i < n; i++) {
            System.out.print(i + ": ");
            for (int j : adjList.get(i)) {
                System.out.print(j + " ");
            }
            System.out.println();
        }
    }
}

 

출력

Adjacency List:
0: 1 
1: 0 2 
2: 1 3 
3: 2

 

 

3. DFS (Depth First Search)

 

문제 설정

 

위 그래프에서 **깊이 우선 탐색(DFS)**으로 탐색을 진행합니다.

시작 노드:  0 

탐색 순서: 연결된 노드를 재귀적으로 방문합니다.

 

DFS 동작 과정

 

1. 시작 노드  0  방문:  [0] 

2. 0 에서  1 로 이동:  [0, 1] 

3. 1 에서  2 로 이동:  [0, 1, 2] 

4. 2 에서  3 로 이동:  [0, 1, 2, 3] 

 

Java 코드 구현(인접리스트)

import java.util.ArrayList;

public class DFSExample {
    static boolean[] visited;
    static ArrayList<ArrayList<Integer>> adjList = new ArrayList<>();

    public static void main(String[] args) {
        int n = 4; // 노드 개수

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

        // 간선 추가
        adjList.get(0).add(1);
        adjList.get(1).add(0);

        adjList.get(1).add(2);
        adjList.get(2).add(1);

        adjList.get(2).add(3);
        adjList.get(3).add(2);

        // 방문 배열 초기화
        visited = new boolean[n];

        // DFS 호출
        System.out.println("DFS Traversal:");
        dfs(0); // 시작 노드
    }

    static void dfs(int node) {
        visited[node] = true;
        System.out.print(node + " "); // 방문 노드 출력

        // 연결된 노드 방문
        for (int nextNode : adjList.get(node)) {
            if (!visited[nextNode]) {
                dfs(nextNode);
            }
        }
    }
}

 

출력

DFS Traversal:
0 1 2 3

 

요약

 

• 인접행렬: 그래프의 연결 정보를 2차원 배열로 표현. 메모리 사용량이 크지만, 빠른 간선 확인 가능.

• 인접리스트: 그래프의 연결 정보를 리스트로 표현. 메모리 효율이 높고 희소 그래프에서 적합.

• DFS: 깊이 우선 탐색으로 그래프의 모든 노드를 탐색하며, 재귀나 스택으로 구현.(주로 인접리스트를 통해 구현)