그래프 graph

그래프란?

: 정점(vertex)를 간선(edge, link)로 연결한 형태의 자료구조이다.

트리도 그래프의 일종이지만 그래프는 사이클을 형성할 수 있고 이웃한 정점끼리 상하 관계를 갖지 않는다.

1. 그래프의 종류

(1) 연결/비연결 그래프

• 연결 그래프 : 그래프 상에 있는 임의의 두 정점 사이의 경로가 반드시 존재하는 그래프
• 비연결 그래프 : 어떤 정점 사이에서도 경로가 없는 그래프

(+) 완전 그래프(Complete graph)
모든 정점에 간선이 있고, 한 정점에서 다른 정점과 모두 연결되어 있는 그래프

(2) 방향/무방향 그래프

• 방향 그래프 : 방향이 있는 그래프
• 무방향 그래프 : 방향이 없는 그래프

(3) 가중치 그래프
: 간선에 가중치가 부여된 그래프
간선에 부여된 값인 가중치는 비용(cost)라고도 불리며 음수가 될 수도 있다.

(4) 서브 그래프 (=부분 그래프)
: 특정 그래프의 정점과 간선의 일부분으로 이루어진 그래프

2. 그래프 표현

(1) 인접 행렬 기반

N X N 크기의 행렬로 그래프를 표현하는 방식으로 <행, 열> 값은 <출발 정점, 도착 정점>을 의미한다.

연결된 상태는 1,
연결되지 않은 상태는 0 으로 표기한다.

가중치 그래프인 경우 가중치 값으로 표기한다.

• 장점:
  • 그래프의 연결 관계를 간단하게 표현할 수 있다.
  • 특정 두 정점 사이의 연결 여부를 빠르게 확인할 수 있다.
• 단점:
  • 정점의 수가 많아지면 메모리 낭비가 심해질 수 있다.
• 시간 복잡도: O(N²)
  
  각 노드마다 모든 노드(N개)에 대해 연결 여부를 확인해야 하기 때문이다.

사진 출처
방향 그래프

사진 출처
무방향 그래프

• 대각선 요소를 기준으로 연결 관계가 대칭을 이룬다.

구현 예시 (자바)

public class Graph {
    public static void main(String[] args) {
        int[][] edges = new int[][] {
            {1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 5}, {4, 5}
        };

        int N = 5;
        int[][] matrix = new int[N + 1][N + 1];

        // 간선 정보로 인접 행렬 채우기 (무방향 그래프)
        for (int[] edge : edges) {
            matrix[edge[0]][edge[1]] = 1;
            matrix[edge[1]][edge[0]] = 1; // 무방향이므로 양방향으로 연결
        }

        // 인접 행렬 출력
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                System.out.print(matrix[i][j] + " ");
            }
            System.out.println();
        }
    }
}

// 출력 결과
0 1 1 1 0
1 0 1 0 1
1 1 0 0 0
1 0 0 0 1
0 1 0 1 0

(2) 인접 리스트 기반

그래프의 특정 정점과 연결된 정점들을 연결 리스트로 표현하는 방식이다.

• 장점:
  • 메모리 효율성: 간선이 적은 그래프에서 인접 행렬보다 메모리 효율적이다.
  • 동적 크기 조정: 정점과 간선의 수가 변동할 때 유리하다.
  • 간선 탐색 효율성: 각 정점의 이웃 정점만 저장하므로, 연결된 정점들을 빠르게 확인할 수 있다.
• 단점:
  • 두 정점 사이의 연결 여부를 확인하는 데 시간이 걸릴 수 있다.
• 시간 복잡도: O(N + E)
  모든 노드(N개)와 간선(E개)을 한 번씩 탐색해야 하기 때문이다.

사진 출처
방향 그래프

사진 출처
무방향 그래프

사진 출처
가중치 그래프

구현 예시 (자바)

public class Graph {
    public static void main(String[] args) {
        int[][] edges = new int[][] {
            {1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 5}, {4, 5}
        };

        int N = 5; 
        List<List<Integer>> adjList = new ArrayList<>();

        // 정점의 수 만큼 리스트 초기화
        for (int i = 0; i <= N; i++) {
            adjList.add(new ArrayList<>());
        }

        // 간선 정보로 인접 리스트 채우기 (무방향 그래프)
        for (int[] edge : edges) {
            adjList.get(edge[0]).add(edge[1]);
            adjList.get(edge[1]).add(edge[0]); // 무방향이므로 양방향으로 연결
        }

        // 인접 리스트 출력
        for (int i = 1; i <= N; i++) {
            System.out.print(i + ": ");
            for (int neighbor : adjList.get(i)) {
                System.out.print(neighbor + " ");
            }
            System.out.println();
        }
    }
}

// 출력 결과
1: 2 3 4 
2: 1 3 5 
3: 1 2 
4: 1 5 
5: 2 4 

3. DFS & BFS

(1) 깊이우선탐색 (DFS, depth-first search)

사진 출처

그래프에서 더 이상 방문 가능한 정점이 없을 때까지 최대한 깊이 탐색하기를 반복하는 탐색 방법이다.

DFS 구현 방식은 크게 재귀 호출을 이용하는 방법과 스택을 이용하는 방법으로 나눌 수 있다.

배열을 사용하여 특정 정점의 방문 여부를 기록할 수 있으며,
뒤로 돌아가기 기능을 위해서 스택 또는 재귀호출을 사용한다.

인접 리스트를 이용한 재귀 구현 예시 (자바)

public class Graph {
    static ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
    static boolean[] visited;

    public static void main(String[] args) {
        int N = 5; // 정점 개수
        int[][] edges = {
            {1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 5}, {4, 5}
        };

        visited = new boolean[N + 1];

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

        // 간선 정보 추가 (무방향 그래프)
        for (int[] edge : edges) {
            graph.get(edge[0]).add(edge[1]);
            graph.get(edge[1]).add(edge[0]);
        }

        // DFS 시작 (예: 1번 정점부터 탐색)
        DFS(1);
    }

    public static void DFS(int node) {
        visited[node] = true; // 현재 노드 방문 처리
        System.out.print(node + " "); // 현재 노드 출력

        // 현재 노드에 연결된 다른 노드들을 탐색
        for (int next : graph.get(node)) {
            if (!visited[next]) {
                DFS(next); // 방문하지 않은 노드라면 재귀 호출
            }
        }
    }
}

인접 리스트를 이용한 스택 구현 예시 (자바)

    public static void DFS(int start) {
        Stack<Integer> stack = new Stack<>();
        stack.push(start);

        while (!stack.isEmpty()) {
            int node = stack.pop();

            if (!visited[node]) {
                visited[node] = true;
                System.out.print(node + " ");

                // 연결된 노드들을 스택에 넣는다.
                // 스택은 LIFO(후입선출)이기 때문에, 방문 순서를 제어하고 싶으면 리스트를 정렬하거나 역순으로 넣어야 한다.
                for (int next : graph.get(node)) {
                    if (!visited[next]) {
                        stack.push(next);
                    }
}}}}}

(2) 너비우선탐색 (BFS, breath-first search)

사진 출처

최대한 넓게 탐색하기를 반복하는 방식으로 인접한 모든 정점들을 방문하여 탐색하는 방식이다.

Queue(큐)를 이용해서 구현하며, 먼저 들어온 정점을 먼저 처리(FIFO)한다.

구현 예시 (자바)

public static void BFS(int start) {
    Queue<Integer> queue = new LinkedList<>();
    queue.offer(start);
    visited[start] = true;

    while (!queue.isEmpty()) {
        int node = queue.poll();
        System.out.print(node + " ");

        for (int next : graph.get(node)) {
            if (!visited[next]) {
                visited[next] = true;
                queue.offer(next);
            }
        }
    }
}

4. 최단 경로 알고리즘

한 정점에서 목적지 정점까지 이르는 가중치의 합이 최소가 되는 경로를 결정하는 알고리즘이다.

알고리즘	특징	시간 복잡도
다익스트라 (Dijkstra)	음의 가중치가 없는 경우, 최단 경로	O((V + E) log V)
벨만-포드 (Bellman-Ford)	음의 가중치가 있는 그래프에 적합	O(V * E)
플로이드-워셜 (Floyd-Warshall)	모든 쌍의 최단 경로	O(V^3)

최단 경로 알고리즘으로 가장 대표적인 알고리즘은 다익스트라 알고리즘이다.

다익스트라 알고리즘

간선의 가중치가 음이 아닌 수라는 가정하에 사용 가능한 알고리즘으로, 특정 정점에서 다른 모든 정점까지의 최단 거리를 구해주는 알고리즘이다.

1. 시작 노드를 기준으로 최단 거리를 저장하는 배열을 만든다. (보통 distance 배열)
   
2. 시작 노드의 거리를 0으로 초기화하고, 나머지는 무한대(∞)로 초기화한다.
   
3. 현재 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드를 선택한다.
   
4. 선택된 노드를 통해 인접한 노드들의 최단 거리 갱신한다.
   
5. 모든 노드를 방문할 때까지 3~4 반복한다.
   

사진 출처

• 시간 복잡도 :
  • 배열 사용 시 O(N²)
  • 우선순위 큐 사용 시 O((V + E) log V)

public class Dijkstra {

    static final int INF = Integer.MAX_VALUE;  // 무한대 설정

    public static void main(String[] args) {
        int N = 5;  // 노드의 수
        List<List<int[]>> graph = new ArrayList<>();
        
        // 그래프 초기화 (각 노드에 인접 노드 추가)
        for (int i = 0; i <= N; i++) {
            graph.add(new ArrayList<>());
        }

        // (목적지, 비용) 형태로 간선 추가
        graph.get(1).add(new int[]{2, 2});
        graph.get(1).add(new int[]{3, 5});
        graph.get(2).add(new int[]{3, 1});
        graph.get(2).add(new int[]{4, 2});
        graph.get(3).add(new int[]{4, 3});
        graph.get(4).add(new int[]{5, 1});
        graph.get(5).add(new int[]{1, 7});

        // 다익스트라 알고리즘 실행
        dijkstra(1, graph, N);
    }

    public static void dijkstra(int start, List<List<int[]>> graph, int N) {
        int[] distance = new int[N + 1];
        Arrays.fill(distance, INF);  // 거리 배열 초기화
        distance[start] = 0;

        // 우선순위 큐를 사용하여 최단 거리 노드 탐색
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
        pq.add(new int[]{0, start});  // (거리, 노드)

        while (!pq.isEmpty()) {
            int[] current = pq.poll();
            int dist = current[0];
            int node = current[1];

            // 이미 더 짧은 경로로 방문한 적 있으면 무시
            if (distance[node] < dist) {
                continue;
            }

            // 인접 노드들 확인
            for (int[] neighbor : graph.get(node)) {
                int nextNode = neighbor[0];
                int edgeCost = neighbor[1];
                int newDist = dist + edgeCost;

                if (newDist < distance[nextNode]) {
                    distance[nextNode] = newDist;
                    pq.add(new int[]{newDist, nextNode});
                }
            }
        }

        // 결과 출력
        for (int i = 1; i <= N; i++) {
            if (distance[i] == INF) {
                System.out.println(i + " 노드는 도달 불가");
            } else {
                System.out.println(i + " 노드까지의 최단 거리: " + distance[i]);
            }
        }
    }
}

1 노드까지의 최단 거리: 0
2 노드까지의 최단 거리: 2
3 노드까지의 최단 거리: 3
4 노드까지의 최단 거리: 4
5 노드까지의 최단 거리: 5

25.04.28 스터디 내용으로 변경하였습니다.