인접 행렬 tip

인접 행렬로 그래프 다루기

그래프를 표현하는 방식 중 하나인 인접 행렬(Adjacency Matrix) 은 이차원 배열을 통해 노드 간 연결 여부를 표현한다.

int[][] graph = {
    {0, 1, 0, 1, 0, 0, 1, 0},
    {1, 0, 0, 1, 0, 0, 0, 0},
    {0, 0, 0, 1, 0, 0, 0, 0},
    {1, 1, 1, 0, 0, 0, 0, 1},
    {0, 0, 0, 0, 0, 1, 0, 0},
    {0, 0, 0, 0, 1, 0, 1, 1},
    {1, 0, 0, 0, 0, 1, 0, 0},
    {0, 0, 0, 1, 0, 1, 0, 0}
};

 

1. 인접 행렬 그대로 사용하기

인접 행렬에서는 graph[i][j] == 1이면 노드 i와 노드 j가 연결되어 있다는 뜻
따라서, 특정 노드에서 인접 노드를 탐색할 때는 해당 행을 순회하면 된다.

int curVertex = 3; // 현재 노드

for (int nextVertex = 0; nextVertex < graph[curVertex].length; nextVertex++) {
    if (graph[curVertex][nextVertex] == 1) {
        System.out.println("노드 " + curVertex + " → 다음 노드 " + nextVertex);
    }
}

출력 예시

노드 3 → 다음 노드 0
노드 3 → 다음 노드 1
노드 3 → 다음 노드 2
노드 3 → 다음 노드 7

 

2. 인접 리스트로 변환해서 사용하기

인접 행렬이 익숙하지 않다면, 인접 리스트로 변환하여 처리할 수 있다.
이는 메모리 효율과 직관성을 모두 고려한 방식으로, 특히 간선 수가 적은 희소 그래프에서 유용하다.

Map<Integer, List<Integer>> adjList = new HashMap<>();
int n = graph.length;

for (int i = 0; i < n; i++) {
    adjList.put(i, new ArrayList<>());
    for (int j = 0; j < n; j++) {
        if (graph[i][j] == 1) {
            adjList.get(i).add(j);
        }
    }
}