[자료구조] 인접행렬과 인접그래프 (with Java)

그래프

그래프는 정점(Vertex)과 간선(Edge)으로 구성된 자료구조이다. 정점은 데이터를 나타내고, 간선은 데이터 간의 관계를 의미한다. 

• 정점(Vertex): 데이터 자체를 의미
• 간선(Edge): 정점 간의 관계를 나타내며, 방향성이 있을 수 있다. 

 

대표적인 그래프의 종류들이다. 

• 무방향 그래프(Undirected Graph): 간선에 방향이 없는 그래프
• 방향 그래프(Directed Graph): 간선에 방향이 있는 그래프
• 가중치 그래프(Weighted Graph): 간선에 가중치가 있는 그래프

출처 - https://born2bedeveloper.tistory.com/42

 

그래프의 구현은 인접행렬과 인접그래프가 있으며, 각각 알아보자.

 

인접 행렬

인접 행렬은 2차원 배열을 사용하여 그래프의 정점들 간의 연결 관계를 표현한 것이다. 

행렬의 `(i, j)` 위치에 간선의 유무를 나타낸다. 

• 무방향 그래프: 간선이 존재하면 `(i, j), (j, i)` 모두에 1, 없으면 0을 표기한다.
• 방향 그래프: 간선이 존재하고 방향이 `i`에서 `j` 방향의 간선이 존재하면 1, 없으며 0을 표기한다.
• 가중치그래프: 간선이 존재하면 간선의 가중치, 없으면 0 표기한다.

장점으로는 구현이 쉽고, O(1) 시간 복잡도로 간선의 존재가 확인 가능하다. 단점으로는 배열의 크기가 고정되어 있고, 고정된 크기만큼 값을 모두 넣어줌으로 O(N^2)의 높은 공간 복잡도를 필요하다. 

 

인접 행렬의 구현

인접행렬의 크기는 `정점의 수`를 기준으로 배열의 크기가 결정된다.  경우에 따라 인덱스와 그래프 표현은 맞추기 위해 `N+1`형태로 선언하기도 한다.

 

아래의 코드는 무방향그래프를 인접행렬로 표현한 구현코드이다. 

class GraphAdjMatrix {
    private int vertices; // 정점의 수
    private int[][] adjMatrix; // 인접행렬

    // 주어진 정점의 수 기준 2차원 배열 생성
    public GraphAdjMatrix(int vertices) {
        this.vertices = vertices;
        adjMatrix = new int[vertices][vertices];
    }

    // 간선 추가
    public void addEdge(int src, int dest) {
        adjMatrix[src][dest] = 1;
        adjMatrix[dest][src] = 1;
    }

    // 간선 제거
    public void removeEdge(int src, int dest) {
        adjMatrix[src][dest] = 0;
        adjMatrix[dest][src] = 0;
    }

    // 간선 확인
    public boolean isEdge(int src, int dest) {
        return adjMatrix[src][dest] != 0;
    }
}

 

다음은 구현코드의 실행코드이다. 

public class Main {
    public static void main(String[] args) {
        // 정점 수 5개의 그래프 생성
        GraphAdjMatrix graph = new GraphAdjMatrix(5);

        // 간선 추가
        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);

        System.out.println("그래프 인접 행렬:");
        printGraph(graph);

        // 간선 존재 여부 확인
        System.out.println("Edge between 0 and 1: " + graph.isEdge(0, 1));
        System.out.println("Edge between 2 and 4: " + graph.isEdge(2, 4));

        // 간선 제거
        graph.removeEdge(1, 4);
        System.out.println("\n간선 제거 후 인접 행렬:");
        printGraph(graph);

        // 간선 존재 여부 확인
        System.out.println("Edge between 1 and 4: " + graph.isEdge(1, 4));
    }

    // 그래프의 인접 행렬을 출력하는 메서드
    private static void printGraph(GraphAdjMatrix graph) {
        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < 5; j++) {
                System.out.print((graph.isEdge(i, j) ? 1 : 0) + " ");
            }
            System.out.println();
        }
    }
}

 

다음과 같은 결과가 나온다. 

그래프 인접 행렬:
0 1 0 0 1 
1 0 1 1 1 
0 1 0 1 0 
0 1 1 0 1 
1 1 0 1 0 
Edge between 0 and 1: true
Edge between 2 and 4: false

간선 제거 후 인접 행렬:
0 1 0 0 1 
1 0 1 1 0 
0 1 0 1 0 
0 1 1 0 1 
1 0 0 1 0 
Edge between 1 and 4: false

 

인접 그래프 

인접 리스트는 그래프를 표현하는 방법 중 하나로, 각 정점이 자신과 연결된 정점들의 목록을 저장하는 방식이다.

• 각 정점은 하나의 리스트로 저장된다.
• 리스트에는 그 정점과 직접 연결된 다른 정점들이 저장된다.

 

구조 예시를 보면 다음과 같다. 

- 그래프

0 --- 1
|     |
4 --- 3 --- 2

 

- 인접 리스트 표현

0 -> [1, 4]
1 -> [0, 3]
2 -> [3]
3 -> [1, 2, 4]
4 -> [0, 3]

 

인접리스트의 경우 인접행렬처럼 선언된 배열만큼 값을 채우지 않고 필요한 값만 가지고 있으므로 공간 효율성이 좋다. 특정 정점의 인접 정점을 빠르게 찾을 수 있다. 

 

단점으로는, 두 정점 간의 간선 존재 확인을 위해 최악의 경우 O(V)(V는 정점의 개수)만큼의 시간 복잡도가 걸리게 된다.

 

인접 리스트 구현 

`ArrayList`와 `LinkedList`를 이용한 무방향 그래프를 인접리스트로 구현한 코드이다. 여기선 내부 리스트를 LinkedList를 사용했는데 `ArrayList`를 사용해도 무방하다.

import java.util.*;

class GraphAdjList {
    private int vertices; // 정점 개수
    private List<List<Integer>> adjList; // 인접 리스트

    // 그래프 초기화
    public GraphAdjList(int vertices) {
        this.vertices = vertices;
        adjList = new ArrayList<>(vertices);

        // 각 정점의 인접 리스트 초기화
        for (int i = 0; i < vertices; i++) {
            adjList.add(new LinkedList<>());
        }
    }

    // 간선 추가
    public void addEdge(int src, int dest) {
        adjList.get(src).add(dest); // src -> dest
        adjList.get(dest).add(src); // dest -> src (무방향 그래프)
    }

    // 간선 제거
    public void removeEdge(int src, int dest) {
        adjList.get(src).remove(Integer.valueOf(dest)); // src -> dest 제거
        adjList.get(dest).remove(Integer.valueOf(src)); // dest -> src 제거
    }

    // 두 정점 간 간선 존재 여부 확인
    public boolean isEdge(int src, int dest) {
        return adjList.get(src).contains(dest);
    }

    // 그래프 출력
    public void printGraph() {
        for (int i = 0; i < vertices; i++) {
            System.out.print("정점 " + i + " -> ");
            for (int neighbor : adjList.get(i)) {
                System.out.print(neighbor + " ");
            }
            System.out.println();
        }
    }
}

public class Main {
    public static void main(String[] args) {
        GraphAdjList graph = new GraphAdjList(5);

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

        // 그래프 출력
        System.out.println("그래프 인접 리스트:");
        graph.printGraph();

        // 간선 존재 여부 확인
        System.out.println("\nEdge between 0 and 1: " + graph.isEdge(0, 1)); // true
        System.out.println("Edge between 2 and 4: " + graph.isEdge(2, 4)); // false

        // 간선 제거
        graph.removeEdge(3, 4);
        System.out.println("\n간선 제거 후 그래프:");
        graph.printGraph();
    }
}

 

 

장단비교

	인접 행렬	인접 리스트
시간 복잡도	O(N^2)     정점 N * N만큼 필요	O(N)      N : 간선의 개수
두 정점의 연결 여부	graph[x][y] 의 값으로 한번에 확인	graph<x> 의 원소에서 y가 나올때까지 탐색
인접 노드 파악 여부	N * N만큼 반복문을 돌아 확인한다.	각 리스트에 담겨있는 원소를 확인한다.

 

 

출처

https://born2bedeveloper.tistory.com/42

[JAVA] 그래프 구현하기 (인접 행렬, 인접 리스트)