[CS 발표_13] 그래프의 개념, 그래프 구현 방법

그래프란?

비선형 자료구조 중 하나로, 데이터를 포함하는 정점(vertex)과 정점을 잇는 간선(edge)으로 구성된 자료구조

그래프의 종류

• 무방향 그래프 : 간선에 방향성이 없는 그래프, 정점의 개수가 n일 때 최대 간선의 개수는 n * (n - 1) / 2
• 방향 그래프 : 간선에 방향성이 있는 그래프, 정점의 개수가 n일 때 최대 간선의 개수는 n * (n - 1)
• 부분 그래프 : 기존 그래프에서 일부 정점 또는 간선을 제외한 그래프
• 가중치 그래프 : 간선에 비용이나 가중치가 할당된 그래프
• 완전 그래프(= 연결 그래프) : 간선을 최대로 가진 그래프
• 유향 비순환 그래프 : 방향 그래프이면서 사이클이 없는 그래프

그래프 구현 방법

인접 행렬

2차원 배열을 이용하여 그래프를 구현하는 방법, 간선의 수가 많은 밀집 그래프에서 주로 사용된다.

• 장점
  • 두 정점 사이의 간선 존재 여부를 O(1)의 시간에 확인할 수 있다.
  • 새로운 간선을 추가하고 제거하는 것이 O(1)로 빠르다.
• 단점
  • 특정 노드에 인접한 노드를 찾을 때 모든 노드를 순회해야 한다.
  • 정점이 많은 그래프에서는 비효율적일 수 있다.
  • 노드를 추가하고 제거하는 것이 O(N^2)으로 느리다.

인접 행렬을 이용한 그래프 구현 예시

public class GraphMatrix {
    private int vertices;  // 노드의 수
    private int[][] adjacencyMatrix;  // 인접 행렬

    // 그래프 생성자
    public GraphMatrix(int vertices) {
        this.vertices = vertices;
        adjacencyMatrix = new int[vertices][vertices];
    }

    // 간선 추가 메서드
    public void addEdge(int source, int destination) {
        adjacencyMatrix[source][destination] = 1;
        // 무방향 그래프인 경우 다음 줄도 추가
        // adjacencyMatrix[destination][source] = 1;
    }

    // 그래프 출력 메서드
    public void printGraph() {
        System.out.println("Adjacency Matrix:");
        for (int i = 0; i < vertices; i++) {
            for (int j = 0; j < vertices; j++) {
                System.out.print(adjacencyMatrix[i][j] + " ");
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        int vertices = 5;  // 노드 수
        GraphMatrix graph = new GraphMatrix(vertices);

        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.printGraph();
    }
}

 

위 코드를 실행해보면 다음과 같이 나오게 된다.

인접 리스트

연결 리스트를 이용하여 그래프를 구현하는 방법,  간선의 수가 적은 희소 그래프에서 주로 사용된다.

• 장점
  • 공간 복잡도가 O(N + E)로, 희소 그래프에서 메모리 효율이 좋다.
  • 노드를 추가하고 제거하는 것이 빠르다.
  • 특정 노드에 인접한 노드를 찾을 때 인접 배열보다 쉽게 찾을 수 있다.
• 단점
  • 두 노드 간의 간선 존재 여부를 확인하는 데 O(N)의 시간이 걸릴 수 있다.

인접 리스트를 이용한 그래프 구현 예시

import java.util.LinkedList;

public class GraphList {
    private int vertices;  // 노드의 수
    private LinkedList<Integer>[] adjacencyList;  // 인접 리스트

    // 그래프 생성자
    public GraphList(int vertices) {
        this.vertices = vertices;
        adjacencyList = new LinkedList[vertices];
        for (int i = 0; i < vertices; i++) {
            adjacencyList[i] = new LinkedList<>();
        }
    }

    // 간선 추가 메서드
    public void addEdge(int source, int destination) {
        adjacencyList[source].add(destination);
        // 무방향 그래프인 경우 다음 줄도 추가
        // adjacencyList[destination].add(source);
    }

    // 그래프 출력 메서드
    public void printGraph() {
        for (int i = 0; i < vertices; i++) {
            System.out.print("Vertex " + i + ":");
            for (Integer edge : adjacencyList[i]) {
                System.out.print(" -> " + edge);
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        int vertices = 5;  // 노드 수
        GraphList graph = new GraphList(vertices);

        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.printGraph();
    }
}

 

위 코드를 실행해보면 다음과 같이 나오게 된다.

[자료구조] 그래프(Graph) 개념, 구현 (tistory.com)

자료구조 그래프(Graph) 구현방법 (tistory.com)

기술 면접 대비 CS 전공 핵심요약집 | 이수진 - 교보문고 (kyobobook.co.kr)