[Data Structure] 그래프(Graph)

[Data Structure] 그래프(Graph)

1. 그래프

그래프는 아이템(사물 또는 추상적 개념)들과 이들 사이의 연결관걔를 표현한다.

그래프는 정점(Vertex)과 정점을 연결하는 간선(Edge)의 집합로 객체간의 관계를 표현할 수 있는 자료구조이다.

• $|V|$: 정점의 개수, $|E|$: 그래프에 포함된 간선의 개수
• $|V|$개의 정점을 가지는 그래프는 최대 간선의 개수는$|E|=|V|\times\frac{|V|−1}{2}$개의이다.

선형 자료구조나 트리 자료구조로 표현하기 어려운 $N:N$ 관계를 가지는 원소들을 표현하기 용이하다.

2. 그래프의 유형

1) 무향그래프(Undirected Graph)

서로 대칭적인 관계를 연결해서 나타낸 그래프

간선에 방향이 없는 그래프

정점 A와 정점 B를 연결하는 간선은 (A, B)와 같이 정점의 쌍으로 표현한다.

• (A, B)와 (B, A)는 같은 간선을 의미

2) 유향그래프(Directed Graph)

간선을 화살표로 표현, 방향성의 개념이 포함이된다.

간선에 방향이 있는 그래프

정점 A에서 정점 B로만 갈수 있는 간선은 <A, B>와 같이 표현한다.

• <A, B>와 <B, A>는 다름

3) 가중치그래프(Weighted Graph)

이동하는 데 드는 비용을 간선에 부여한 그래프

가중치는 두 정점 사이의 거리, 지나는 시간, 금액등이 될수 있으며 또한 음수인 경우도 존재한다.

두 정점 간의 이동방향이 다를경우 가중치가 다를 수 있음.

4) 사이클이 없는 방향 그래프(DAG, Directed Acyclic Graph)

어떠한 정점 v에서 시작하여 다시 v로 가는 경로가 없는 그래프

위상정렬이 있는 유향그래프

5) 완전 그래프

정점들에 대해 가능한 모든 간선들을 가진 그래프

6) 부분 그래프

원래 그래프에서 일부의 정점이나 간선을 제외한 그래프

3. 그래프 용어와 표현

1) 그래프(Graph)

G=(V, E)로 표현, V=정점의 집합, E=간선의 집합

2) 인접(Adjacency)

두 개의 정점에 간선이 존재(연결됨)하면 서로 인접해 있다고 한다.

2) 차수(Degree)

정점에 인접한 정점의 수

방향그래프에서는 차수를 진입차수(In-degree)와 진출차수(Out-degree)로 구분

3) 경로(Path)

시작 정점부터 도착 정점까지의 정점들을 나열하여 표현

• [a, c, b, e] : 정점 a로부터 도착점 e까지의 여러 경로들 중 하나

단순 경로(Simple Path)

• 경로 중에서 반복되는 정점이 없는 경우(경로상의 정점들이 모두 다른 경로)

사이클(Cycle)

• 단순 경로의 시작 정점과 종료 정점이 동일한 경우

4. 그래프 표현

그래프는 주로 2가지 방법을 이용하여 표현한다

• 인접행렬
• 인접리스트

메모리나 성능을 고려해서 결정해야한다.

1) 인접행렬

두 정점을 연결하는 간선의 유무를 행렬로 표현

• NN개의 정점(노드)을 가진 그래프를 $N×N$배열에 저장하여 표현
• 간선의 수와 무관하게 항상 $N^2$개의 메모리 공간이 필요하다.

배열의 인덱스는 정점을 의미

정점 i와 j 사이에 간선이 없으면 $a[i][j]=0$, 간선이 있으면 $a[i][j]=1$로 표현

• 가중치그래프는 1대신 가중치를 저장하고 인접하지 않은 정점의 비용은 무한대로 표시한다.

대각선의 요소는 무의미

단점

정점의 개수 $N$이 커지면 필요한 메모리 크기는 $N^2$에 비례하여 커짐

어떤 정점의 인접 정점을 찾을때마다 $N$개의 정점을 탐색해야한다.

정점의 개수에 비례하여 시간도 증가한다.

해결

그래프를 인접리스트로 표현하여 불필요한 메모리사용과 비용을 줄일 수 있음.

2) 인접리스트

각 정점에 대한 인접 정점들을 순차적으로 표현

하나의 정점에 인접한 모든 노드를 연결 리스트 형태로 저장

• 경로에 관한 정보가 아님.

가중치 정보를 표시하려면 노드에 가중치 필드를 추가하여 표현한다.

5. 그래프의 순회

모든 자료(정점)을 빠짐없이 탐색하는 것을 의미한다.

그래프에서는 2가지 방식으로 모든 정점을 탐색한다.

• 깊이우선탐색(DFS: Depth First Search)
• 너비우선탐색(BFS: Breadth First)

1) 깊이우선탐색(DFS)

가장 마지막 정점으로 돌아가 깊이 우선 탐색을 반복해야 하므로 후입선출 구조의 스택을 사용하거나 재귀 호출을 이용하여 구현한다.

방법

1. 시작 정점에서 방향을 선택해서 다음 정점으로 이동
2. 선택된 정점에서 앞 단계 작업을 반복 수행하면서 갈 수 있는 경로가 있는 곳 까지 탐색
   • 이미 방문한 정점은 재방문 하지 않는다.
3. 더이상 갈 곳이 없으면 가장 최근 갈림길의 정점으로 돌아와 다른 방향의 정점으로 탐색을 반복, 모든 정점을 방문한다.

code

import java.util.List;
public class DFS {

   static class Edge {
        int adjvertex;  // 선분의 다른쪽 정점
        public Edge(int v) { // 생성자
            adjvertex = v;
        }
    }

    int N;     // 그래프 정점의 수
    List<Edge>[] graph;
    private boolean[ ] visited;    // DFS 수행 중 방문한 정점을 true로 만든다.
    public DFS(List<Edge>[] adjList) { // 생성자
        N = adjList.length;
        graph = adjList;
        visited = new boolean [N];
        for (int i = 0; i < N; i++) visited[i] = false;  // 배열 초기화
        for (int i = 0; i < N; i++) if (!visited[i]) dfs(i);
    }
    private void dfs(int i) {
        visited[i] = true;        // 점점 i가 방문되어 visited[i]를 true로 만든다.
        System.out.print(i+" ");  // 정점 i가 방문되었음을 출력한다.
        for (Edge e: graph[i]) {  // 정점 i에 인접한 각 정점에 대해
            if (!visited[e.adjvertex]) { // 정점 i에 인접한 정점이 방문 안되었으면 재귀호출
                dfs(e.adjvertex);
            }
        }
    }
}

2) 너비우선탐색(BFS)

인접한 정점들에 대해 탐색 후 차례로 너비우선탐색을 진행해야 하므로 선입선출 형태의 자료구조인 큐를 활용한다.

방법

1. 시작 정점에서 인접한 정점들을 먼저 모두 차례로 방문한다.
2. 방문했던 정점을 다시 시작점으로 하여 계속 방문 수행함
   • 이미 방문한 정점은 재방문 하지 않는다.

code

import java.util.*;
public class BFS {

    static class  Edge {
        int adjvertex;
        public Edge(int v) {
            adjvertex = v;
        }
    }

    int N;  // 그래프 정점의 수
    List<Edge>[] graph;
    private boolean[ ] visited;     // BFS 수행 중 방문한 정점의 원소를 true로 만든다.
    public BFS(List<Edge>[] adjList) { // 생성자
        N = adjList.length;
        graph = adjList;
        visited = new boolean [N];
        for (int i = 0; i < N; i++) visited[i] = false;   // 배열 초기화
        for (int i = 0; i < N; i++) if (!visited[i]) bfs(i);
    }
    private void bfs(int i) {
        Queue<Integer> q = new LinkedList<Integer>();  // 큐 선언
        visited[i] = true;
        q.add(i); //큐에 시작 정점 s를 삽입        
        while (!q.isEmpty()) {
            int j = q.remove();           // 큐에세 정점 j를 가져옴 
            System.out.print(j+" ");
            for (Edge e: graph[j]) {     // 정점 j에 인접한 정점들 중 방문안된 정점 하나씩 방문
                if (!visited[e.adjvertex]) {
                    visited[e.adjvertex] = true;
                    q.add(e.adjvertex);  // 새로이 방문된 정점을 큐에 삽입
                }
            }
        }
    }
}

Reference

『IT CookBook, 자바로 배우는 쉬운 자료구조』, 이지영 집필, 한빛아카데미(2008)

『SW 문제해결 응용 - 구현 - 그래프의 기본과 탐색』