인접 행렬과 인접 리스트가 무엇인가?

인접행렬과 인접 리스트란 그래프를 표현하기 위한 두 가지 주요 방법을 말합니다.

a : 그래프 b : 인접 리스트 c : 인접 행렬

인접 행렬이란

그래프 연결 상태를 2차원 배열을 활용하여 표현한 방법을 말합니다.
그래프의 노드 수를 n이라고 할 경우, n*n크기의 배열을 사용하여 노드들 간의 연결 여부를 나타냅니다. 행과 열의 인덱스는 그래프의 노드를 나타내며, 해당 위치의 값은 노드들 간의 연결 여부를 나타냅니다.

 

"간선(Edge)"과 "노드(Node)"는 그래프 이론에서 중요한 개념입니다.

1. 간선(Edge): 그래프의 간선은 노드들을 연결하는 선으로, 노드와 노드 사이의 관계를 나타냅니다. 간선은 방향성에 따라 "방향 그래프(Directed Graph)"와 무방향 그래프(Undirected Graph)"로 나뉩니다.

• 방향 그래프: 간선은 방향을 가지며, (u, v)와 같이 표현됩니다. 이는 노드 u에서 노드 v로의 방향성이 있는 간선을 의미합니다.
• 무방향 그래프: 간선은 방향이 없으며, {u, v}와 같이 표현됩니다. 이는 노드 u와 노드 v를 양방향으로 연결하는 간선을 의미합니다.

1. 노드(Node): 그래프의 노드는 데이터의 단위를 나타내며, 노드는 간선에 의해 연결됩니다. 노드는 그래프의 구성 요소로, 다른 노드와의 관계를 표현합니다. 노드는 종종 "정점(Vertex)"이라고도 부릅니다.

인접 행렬은 2차원 배열로 간선의 연결 상태를 표현하는 방법입니다.
다음 5개의 노드를 가진 인접 행렬을 나타낸 예시입니다.

인접 행렬

위의 행렬에서 (i, j) 위치의 값이 1이라면 노드 i와 노드 j 사이에 간선이 존재함을 나타내고, 값이 0이라면 간선이 없음을 나타냅니다.

인접 행렬 예시 코드

import java.util.Arrays;

public class Graph {
    private int numNodes;
    private int[][] adjMatrix;

    public Graph(int numNodes) {
        this.numNodes = numNodes;
        // numNodes x numNodes 크기의 2차원 배열을 생성하고 모든 값은 0으로 초기화
        adjMatrix = new int[numNodes][numNodes];
        for (int i = 0; i < numNodes; i++) {
            Arrays.fill(adjMatrix[i], 0);
        }
    }

    public void addEdge(int u, int v) {
        // 노드 u와 노드 v를 연결 (무방향 그래프이므로 양쪽에 모두 1을 표시)
        adjMatrix[u][v] = 1;
        adjMatrix[v][u] = 1;
    }

    public void printAdjMatrix() {
        // 인접 행렬 출력
        for (int i = 0; i < numNodes; i++) {
            for (int j = 0; j < numNodes; j++) {
                System.out.print(adjMatrix[i][j] + " ");
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        int numNodes = 5;
        Graph graph = new Graph(numNodes);

        // 간선 추가
        graph.addEdge(0, 1);
        graph.addEdge(0, 4);
        graph.addEdge(1, 2);
        graph.addEdge(1, 3);
        graph.addEdge(1, 4);
        graph.addEdge(2, 3);
        graph.addEdge(3, 4);

        graph.printAdjMatrix();
    }
}

인접 리스트란

각 노드마다 인접한 노드들의 목록을 연결 리스트 등의 자료구조로 표현하는 방법을 말합니다.
각

노드를 나타내는 배열이나 맵의 원소로서, 해당 노드와 인접 노드들을 연결 리스트 등으로 관리합니다.

인접리스트

 

인접리스트 예시 코드

import java.util.*;

class Node {

    private int index;
    private int distance;

    public Node(int index, int distance) {
        this.index = index;
        this.distance = distance;
    }

    public void show() {
        System.out.print("(" + this.index + "," + this.distance + ") ");
    }
}

public class 인접리스트 {

    // 행(Row)이 3개인 인접 리스트 표현
    public static ArrayList<ArrayList<Node>> graph = new ArrayList<ArrayList<Node>>();

    public static void main(String[] args) {
        // 그래프 초기화
        for (int i = 0; i < 3; i++) {
            graph.add(new ArrayList<Node>());
        }

        // 노드 0에 연결된 노드 정보 저장 (노드, 거리)
        graph.get(0).add(new Node(1, 7));
        graph.get(0).add(new Node(2, 5));

        // 노드 1에 연결된 노드 정보 저장 (노드, 거리)
        graph.get(1).add(new Node(0, 7));

        // 노드 2에 연결된 노드 정보 저장 (노드, 거리)
        graph.get(2).add(new Node(0, 5));

        // 그래프 출력
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < graph.get(i).size(); j++) {
                graph.get(i).get(j).show();
            }
            System.out.println();
        }
    }

}