[자료 구조] 그래프, 트리 (Graph, Tree)

그래프(Graph)의 정의와 종류

그래프 이미지

• 정점(V)과 간선(E)로 이루어진 자료구조
• 정점간의 연결관계를 표현

구성 요소

• 정점(Vertex) - '노드(Node)' 라고도 하며, 데이터를 담는 기본 단위
• 간선(Edge) - 노드 간의 연결을 나타내고, 방향성을 가지거나 가중치를 가질 수 있음

종류

1. 방향 그래프(Directed Graph) - 간선이 방향성을 가져 단방향 성질을 가짐
2. 무방향 그래프(Undirected Graph) - 간선에 방향성이 없어 양방향 성질을 가짐
3. 가중 그래프(Weighted Graph) - 간선에 가중치를 부여한 그래프, 거리나 비용을 계산할 때 사용
4. 비가중 그래프(Unweighted Graph) - 간선에 가중치가 없는 일반적인 그래프

그래프 표현 방법

1. 인접 리스트 활용 (Adjacency List)

• 그래프의 각 정점이 연결 된 노드 리스트를 저장
• 연결된 간선만을 저장하므로 복잡한(밀도가 높은) 그래프에서는 효율적이지 못함
• 간선 추가에 대해 O(1)의 시간복잡도를 가짐

package javalang;

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

public class AdjacencyListGraph {
    public static void main(String[] args) {

        // 인접 리스트(2차원 리스트로...)
        List<List<Integer>> graph = new ArrayList<>();

        for (int i = 0; i < 5; i++) {
            graph.add(new ArrayList<>());
        }

        addEdge(graph, 0, 1);
        addEdge(graph, 0, 2);
        addEdge(graph, 1, 3);
        addEdge(graph, 1, 4);
        addEdge(graph, 2, 4);

        printGraph(graph);
    }

    //연결관계 추가
    private static void addEdge(List<List<Integer>> graph, int u, int v) {
        graph.get(u).add(v);
        // 무방향 그래프일 경우 사용, 아닐경우 사용 XXX
        graph.get(v).add(u);
    }

    //출력
    private static void printGraph(List<List<Integer>> graph){
        for(int i= 0 ;i < graph.size(); i++){
            System.out.print("노드" + i + " 번째와 연결된 노드는: ");
            for(int neighbor : graph.get(i)){
                System.out.print(neighbor + " ");
            }
            System.out.println();
        }
    }
}

출력

2. 인접 행렬 활용 (Adjacency Matrix)

• 노드간의 연결을 2차원 배열로 표현
• 정점 쌍의 관계를 표현하여 밀도가 높은 그래프에 적합함
• 정점간의 연결 여부나 추가, 삭제에 대해 O(1)의 시간 복잡도를 가짐

public class AdjacencyMatrixGraph {
    public static void main(String[] args) {
        
        //인접 행렬 생성
        int[][] graph = new int[5][5];

        addEdge(graph, 0, 1);
        addEdge(graph, 0, 2);
        addEdge(graph, 1, 3);
        addEdge(graph, 1, 4);
        addEdge(graph, 2, 4);

        printGraph(graph);


    }
        //연결관계 추가
    private static void addEdge(int[][] graph, int u, int v) {
        graph[u][v] = 1;
        // 무방향 그래프일 경우 사용, 아닐경우 사용 XXX
        graph[v][u] = 1;
    }

    //출력
    private static void printGraph(int[][] graph){
        for(int i= 0 ;i < graph.length; i++){
            for(int j = 0; j < graph[i].length; j++){
                System.out.print(graph[i][j] + " ");
            }
            System.out.println();
        }
    }
}

시간 복잡도 비교

연산	인접 리스트(Adjacency List)	인접 행렬(Adjacency Matrix)
간선 추가	O(1)	O(1)
간선 삭제	O(V)	O(1)
간선 여부 확인	O(V)	O(1)
모든 정점 순회	O(V + E)	O(V²)
적합한 용도	희소 그래프일 때 (간선 수 적은) E ≪ V²	밀집 그래프일 때 (간선 수 많은) E ≈ V²

인접 리스트가 희소 그래프가 유리한 이유

• 인접 리스트는 정점마다 연결된 이웃 정점만 저장하기 때문에 간선의 수에 비례하여 공간을 사용함
• 따라서 간선의 수 E가 정점의 최대 간선 수인 V² 에 비해 적으므로, O(V + E)가 O(V²)의 증가량을 따라가지 못함
• 인접 행렬의 경우 모든 정점의 관계를 2차원 배열로 저장하므로, 간선 수에 상관 없이 V² 만큼의 공간을 사용