[자료구조] 그래프(Graph) 자료구조 알아보기 & Java 예제 코드

그래프(Graph)란?

그래프(Graph)는 객체 또는 개체 간의 관계를 표현하는 자료구조다.

그래프는 노드(Node)와 노드 사이를 연결하는 간선(Edge)으로 구성된다.

 

• 노드(정점, Vertex) : 일반적으로 개별적인 개체나 개념
• 간선 : 노드 사이의 관계

 

그래프는 현실 세계의 다양한 상황을 모델링하고 문제를 해결하는 데에 사용된다.

 

출처 : https://www.geeksforgeeks.org/graph-data-structure-and-algorithms/

 

 

그래프 구현 방법

그래프는 여러 형태로 구현될 수 있다.

주요한 구현 방법에는 인접 행렬(Adjacency Matrix)과 인접 리스트(Adjacency List)가 있다.

두 가지 구현 방법 중 대부분 인접 리스트 방식을 많이 사용한다.

각각의 구현 방법에 대한 장단점을 알아보면 다음과 같다.

 

인접 행렬(Adjacency Matrix)

• 2차원 배열을 사용해 그래프를 표현한다.
• 배열의 요소는 노드 사이의 연결 여부를 나타낸다.
• 다른 노드와 인접 정점이라면 1, 아니면 0을 넣어준다.

 장점

1. 인접 행렬은 노드의 개수가 적을 때 사용하기 적합하며, 노드 사이의 연결 여부를 상수 시간(O(1))에 확인할 수 있다.
2. 간선의 수에 비례하는 시간 복잡도로 모든 간선을 순회할 수 있다. 따라서 그래프에서 모든 간선을 탐색하는 경우에 유리하다.

단점

1. 노드 사이의 연결 관계가 적을 때에도 모든 가능한 간선을 표현하기 때문에 공간 복잡도가 높다.
2. 희소 그래프(Sparse Graph)의 경우 인접 행렬은 불필요하게 많은 메모리를 사용하게 된다. 특히 노드의 개수가 많고 간선의 개수가 상대적으로 적은 경우에는 공간 낭비가 심하다.

 

인접 리스트(Adjacency List)

• 각 노드마다 인접한 노드들을 연결 리스트 형태로 저장한다.

장점

1. 공간 복잡도가 낮다. 인접 리스트는 각 노드마다 인접한 노드들을 연결 리스트 형태로 저장하므로 그래프의 크기에 선형적으로 비례하는 공간만 사용한다. 따라서 희소 그래프에 효율적이다.
2. 각 노드의 인접한 노드들을 순회하는 시간 복잡도는 인접한 간선의 개수에 비례한다. 따라서 인접 리스트는 간선의 수가 적을 때 효율적이다.

단점

1. 노드 사이의 연결 여부를 확인하는 데에는 인접 행렬보다 시간이 더 걸린다. 인접 리스트에서는 특정 노드와 인접한 노드들의 리스트를 탐색해야 하기 때문이다.
2. 모든 간선을 순회하는 데에는 인접 행렬보다 시간이 더 걸린다. 인접 리스트에서는 모든 노드를 순회하고 각 노드의 인접한 노드들을 순회해야 하므로 시간이 더 소요된다.
3. 인접 행렬은 간선의 개수가 많고 밀집 그래프(Dense Graph)에서 효율적이며, 인접 리스트는 간선의 개수가 적거나 희소 그래프(Sparse Graph)에서 효율적이다. 선택할 구현 방법은 그래프의 크기, 간선의 개수, 연산의 종류 등을 고려하여 결정해야 한다.

 

 

Graph 예시 코드(Java)

Java에서 그래프를 구현하기 위한 예시 코드로 인접 리스트를 사용한 방식으로 구현되었다.

import java.util.ArrayList;
import java.util.List;

// 그래프 클래스 정의
class Graph {
    private int numVertices; // 노드(정점)의 개수
    private List<List<Integer>> adjacencyList; // 인접 리스트

    // 그래프 생성자
    public Graph(int numVertices) {
        this.numVertices = numVertices;
        adjacencyList = new ArrayList<>(numVertices);

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

    // 간선 추가 메서드
    public void addEdge(int source, int destination) {
        adjacencyList.get(source).add(destination); // source와 destination 사이에 간선 추가
        adjacencyList.get(destination).add(source); // destination과 source 사이에 간선 추가 (양방향 그래프인 경우)
    }

    // 인접한 정점들 반환 메서드
    public List<Integer> getAdjacentVertices(int vertex) {
        return adjacencyList.get(vertex); // 주어진 정점에 인접한 정점들 반환
    }
}

// 메인 클래스
public class Main {
    public static void main(String[] args) {
        int numVertices = 5; // 노드(정점)의 개수
        Graph graph = new Graph(numVertices); // 그래프 객체 생성

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

        // 인접한 정점들 출력
        for (int i = 0; i < numVertices; i++) {
            System.out.print("Adjacent to " + i + ": ");
            List<Integer> adjacentVertices = graph.getAdjacentVertices(i);
            for (Integer vertex : adjacentVertices) {
                System.out.print(vertex + " ");
            }
            System.out.println();
            /* 출력
                Adjacent to 0: 1 4
                Adjacent to 1: 0 2 3 4
                Adjacent to 2: 1 3
                Adjacent to 3: 1 2 4
                Adjacent to 4: 0 1 3
            */
        }
    }
}