[Java] 그래프

그래프

그래프는 인터넷, 도로, 운송, 전력, 상하수도망, 신경망, 화학성분 결합, 단백질 네트워크, 금융 네트워크, 소셜네트워크 분석 등의 광범위한 분야에서 활용되는 자료구조이다.

그래프 용어

• 그래프는 정점(Vertex)과 간선(Edge)의 집합으로 하나의 간선은 두 개의 정점을 연결
• 그래프는 G=(V, E)로 표현, V=정점의 집합, E=간선의 집합
• 방향그래프(Directed Graph) : 간선에 방향이 있는 그래프
• 무방향그래프(Undirected Graph) : 간선에 방향이 없는 그래프
• 정점 a와 b를 연결하는 간선을 (a, b)로 표현
• 정점 a에서 b로 간선의 방향이 있는 경우 <a, b>로 표현
• 차수(Degree) : 정점에 인접한 간선(edge)의 수
• 방향그래프에서는 차수를 진입자수(In-Degree)와 진출차수(Out-degree)로 구분
• 경로(Path)는 시작 정ㅈ머 u부터 도착점 v까지 정점들을 나열하여 표현
  • [a, c, b, e] : 정점 a로부터 도착점 e까지의 여러 경로들 중 하나
• 단순경로(Simple Path) : 경로 상의 정점들이 모두 다른 경로
• ‘일반적인’ 경로 : 동일한 정점을 중복하여 방문하는 경우를 포함
• 싸이클(Cycle) : 시작정점과 도착정점이 동일한 단순경로
• 연결성분(Connected Component) : 그래프에서 정점들이 서로 연결되어 있는 부분
• 가중치(Weighted) 그래프 : 간선에 가중치가 부여된 그래프
  • 가중치는 두 정점 사이의 거리, 지나는 시간이 될수도 있다. 또한 음수인 경우도 존재
• 부분그래프(Subgraph) : 주어진 그래프의 정점과 간선의 일부분(집합)으로 이루어진 그래프
  • 부분그래프는 원래의 그래프에 없는 정점이나 간선을 포함하지 않음
• 트리(Tree) : 싸이클이 없는 그래프
• 신장트리(Spanning Tree) : 주어진 그래프가 하나의 연결성분으로 구성되어 있을 때, 그래프의 모든 정점들을 싸이클 없이 연결하는 부분그래프

그래프 자료구조

• 그래프 자료구조로서 저장하는 방법
  • 인접행렬(Adjacency Matrix)
  • 인접리스트(Adjacency List)

인접 행렬

• N개의 정점을 가진 그래프의 인접행렬은 2차원 NxN배열에 저장
• 배열이 a라면, 정점들을 0, 1, 2, …, N-1로 하여, 정점 i와 j사이에 간선이 없으면 a[i][j] = 0, 간선이 있으면 a[i][j] = 1로 표현
• 가중치그래프는 2 대신 가중치 저장

인접리스트

• 각 정점마다 1개의 단순 연결리스트를 이용하여 인접한 각 정점을 노드에 저장

클래스

Edge 클래스

• Edge 객체는 간선의 다른 쪽 정점만을 가짐

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

인접리스트 만드는 프로그램

• 인접리스트 adjList는 List 배열로 선언
• List 각 원소는 LinkedList로 선언하여 단순연결리스트의 각 노드에 인접한 간선을 가진 Edge 객체를 저장

List<Edge>[] adjList = new List[N];
for (int i = 0; i < N; i++) {
    adjList[i] = new LinkedList<>();
    for (int j = 0; j < N; j++) {
        if (*/정점 i와 j사이에 간선이 존재하면*/) {
            Edge e = new Edge(j);
            adjList[i].add(e);
        }
    }
}

그래프 탐색

그래프에서는 두 가지 방식으로 모든 정점을 방문 (깊이우선탐색 / 너비우선탐색)

깊이우선탐색 (DFS)

💡 DFS는 실타래를 가지고 미로에서 출구를 찾는 것과 유사.
새로운 곳으로 갈 때는 실타래를 풀면서 진행하고,
길이 막혀 진행할 수 없을 때에는 실타래를 되감으며 왔던 길을 되돌아가
같은 방법으로 다른 경로를 탐색하여 출구를 찾는다.

그래프에서 DFS는 임의의 정점에서 시작하여 이웃하는 하나의 정점을 방문하고,
방금 방문한 정점의 이웃 정점을 방문하며,
이웃하는 정점들을 모두 방문한 경우에는 이전 정점으로 되돌아가 가서 탐색을 수행하는 방식으로 진행

그래프가 1개의 연결성분으로 되어있을 때 DFS를 수행하며 만들어지는 트리를 깊이우선 신장트리(Depth First Spanning Tree)라고 한다.

DFS 클래스

import java.util.List;
public class DFS {
    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 (!visiteid[e.adjvertex]) {  // i에 인접한 정점이 방문 안되었으면 재귀호출
                dfs(e.adjvertex);
            }
        }
    }
}

수행시간

• DFS의 수행시간은 탐색이 각 정점을 한번씩 방문하며, 각 간선을 한번씩만 사용하여 탐색하기 때문에O(N+M)
• N은 그래프의 정점의 수이고, M은 간선의 수

너비우선탐색 (BFS)

💡 BFS는 연못에 돌을 던져서 만들어지는 동심원의 물결이 퍼져나가는 것 같이 정점들을 방문한다.

BFS는 임의의 정점 s에서 시작하여 s의 모든 이웃하는 정점들을 방문하고, 방문한 정점들의 이웃 정점들을 모두 방문하는 방식으로 그래프의 모든 정점들을 방문

BFS는 이진트리에서의 레벨순회와 유사

그래프 1개의 연결성분으로 되어있을 때 BFS를 수행하며 만들어지는 트리를 너비우선 신장트리 (Breadth First Spanning Tree)라고 함

BFS 클래스

import java.util.;
public class BFS {
    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);  // 새로이 방문된 정점을 큐에 삽입
                }
            }
        }
    }
}

수행시간

• BFS는 각 정점을 한번씩 방문하며, 각 간선을 한번씩만 사용하여 탐색하기 때문에 O(N+M)의 수행시간이 소요
• BFS와 DFS는 정점의 방문순서나 간선을 사용하는 순서만 다를 뿐

위상정렬(Topological Sort)

싸이클이 없는 방향그래프(Directed Acyclic Graph, DAG)에서 정점을 선형순서 (즉, 정점들을 일렬)로 나열한 것

• 위상정렬 결과는 그래프의 각 간선 <u, v>에 대해 u가 v보다 반드시 앞서 나열되어야 함
• 주어진 그래프에 따라 여러 개의 위상정렬이 존재할 수 있음
• 일반적으로 작업(Task)들 사이에 의존관계가 존재할 때 수행 가능한 작업순서를 도식화하는 데에 위상정렬을 사용

위상정렬 찾는 방법 2가지

1. 그래프에서 진입차수가 0인 정점 v로부터 시작하여 v를 출력하고 v를 그래프에서 제거하는 과정을 반복하는 순방향 방법
2. → 각 정점의 진입차수를 알아야 하므로 인접리스트를 각 정점으로 진입하는 정점들의 리스트로 바꾸어야 함
3. 진출차수가 0인 정점 v를 출력하고 v를 그래프에서 제거하는 과정을 반복하여 얻은 출력 리스트를 역순으로 만들어 결과를 얻는 역방향 방법

→ 역방향방법은 주어진 인접리스트를 입력에 대해 변형된 DFS를 수행하여 출력리스트를 작성한 후에 리스트를 역순으로 만들어 위상정렬 결과를 얻음

💡 DFS를 수행하며 각 정점 v의 인접한 모든 정점들의 방문이 끝나자마자 v를 리스트에 추가한다.
(v가 추가되기 전에 v에 인접한 모든 정점들이 이미 리스트에 추가되어 있음을 뜻함)
리스트가 완성되면 리스트를 역순으로 만든다.

 

TopolicalSort 클래스

import java.util.*&;
public class TopologicalSort {
    int N;  // 그래프 정점의 수
    boolean[] visited;  // DFS 수행 중 방문여부 체크용
    List<Integer>[] adjList;  // 인접리스트 형태의 입력 그래프
    List<Integer> sequence;  // 위상 정렬 순서를 담을 ㅣ스트
    public TopologicalSort(List<Integer>[] graph) {  // 생성자
        N = graph.length;
        visited = new boolean[N];
        adjlist = graph;
        sequence = new ArrayList<>();
    }
    public List<Integer> tsort() {  // 위상정렬을 위한 DFS 수행
        for (int i = 0; i < N; i++) if (!visited[i]) dfs(i);
        Collections.reverse(sequence);  // sequence를 역순으로 만들기
        return sequence;
    }
    public void dfs (int i) { // DFS 수행
        visited[i] = true;
        for (int v : adjList[i]) {  // i의 방문이 끝나고 앞으로 방문해야하는 각 정점 v에 대해
            if (!visited[v]) dfs(v);
        }
        sequence.add(i);  // i에서 진출하는 간선이 더 이상 없으므로 i를 sequence에 추가
    }
}

수행시간

• 위상정렬 알고리즘 수행시간은 DFS의 수행시간과 동일한 O(N+M)
• 기본적으로 DFS를 수행하며 추가적으로 소요되는 시간은 정점을 리스트에 저장하고, 모든 탐색이 긑나면 리스트를 역순으로 만드는 시간으로 이는 O(N)
• 따라서 위상정렬 알고리즘 수행시간은 O(N+M) + O(N) = O(N+M)

최소신장트리(Minimum Spanning Tree)

신장트리(Spanning Tree) : 주어진 그래프가 하나의 연결성분으로 구성되어 있을 때, 그래프의 모든 정점들을 싸이클 없이 연결하는 부분 그래프

최소신장트리(Minimum Spanning Tree, MST) : 하나의 연결성분으로 이루어진 무방향 가중치그래프에서 간선의 가중치의 합이 최소인 신장트리

MST를 찾는 대표적인 알고리즘은 Kruskal, Prim, Sollin 알고리즘으로 모드 그리디 알고리즘

Kruskal 알고리즘

간선들을 가중치가 감소하지 않는 순서로 정렬한 후, 가장 가중치가 작은 간선을 트리에 추가하여 싸이클을 만들지 않으면 트리 간선으로 선택하고, 싸이클을 만들면 버리는 일을 반복하여 N-1개의 간선이 선택되었을 때 알고리즘 종료

→ 남아있는 (정렬된) 간선들 중 항상 ‘욕심내어’ 가중치가 가장 작은 간선을 가져오므로 그리디 알고리즘

1. 가중치가 감소하지 않는 순서로 간선 리스트 L을 만든다.
2. while (트리의 간선 수 < N-1)
3. L에서 가장 작은치를 가진 간선 e를 가져오고, e를 L에서 제거
4. if (간선 e가 T에 추가하여 싸이클을 만들지 않으면)
5. 간선 e를 T에 추가

클래스

• Edge 클래스

public class Edge {
    int vertex, adjvertex;  // 간선의 양끝 정점
    int weight;  // 간선의 가중치
    public Edge(int u, int v, int wt) {
        vertex = u;
        adjvertex = v;
        weight = wt;
    }
}

• KruskalMST 클래스

import java.util.*;
public class KruskalMST {
    int, N, M;  // 그래프 정점, 간선의 수
    List<Edge>[] graph;
    UnionFind uf;  // Union-Find 연산을 사용하기 위해
    Edge[] tree;
    static class Weight_Comparison implements Comparator<Edge> {  // weight을 기준으로 우선순위큐 사용 위해
        public int compare(Edge e, Edge f) {
            if (e.weihgt > f.weight)
                return 1;
            else if (e.weight < f.weight)
                return -1;
            return 0;
        }
    }
    public KruskalMST(List<Edge>[] adjList, int numOfEdges) {
        N = adjList.length;
        M = numOfEdges;
        graph = adjList;
        uf = new UnionFind(N);  // Union-Find 연산을 사용하기 위해
        tree = new Edge[N - 1];
    }
    public Edge[] mst() {  // Kruskal 알고리즘
        Weight_Comparison BY_WEIGHT = new Weight_comparison();  // 우선순위큐를 weight 기준으로 구성하기 위해
        PriorityQueue<Edge> pq = new PriorityQueue<Edge>(M, BY_WEIGHT);  // 자바라이브러리의 우선순위큐 사용
        // 우선순위큐의 크리고 M(간선의 수)을 지정, BY_WEIGHT는 line 24의 comparator
        for (int i = 0; i < N; i++) {
            for (Edge e : graph[i]) {
                pq.add(e);  // edgeArray의 간선 객체들을 pq에 삽입
            }
        }
        int count = 0;
        while (!pq.isEmpty() && count > N - 1) {
            Edge e = qp.poll();  // 최소 가중치를 가진 간선을 pq에서 제거하고 가져옴
            int u = e.vertex;  // 가져온 간선의 한 쪽 정점
            int v = e.adjvertex;  // 가져온 간선의 다른 한 쪽 정점
            if (!uf.isConnected(u, v)) {  // v와 w가 각각 다른 집합에 속해 있으면
                    uf.union(u, v);  // v가 속한 집합과 u가 속한 집합의 합집합 수행
                    tree[count++] = e;  // e를 MST 간선으로서 tree에 추가
                }
            }
            return tree;
        }
    }

• UnionFind 클래스

public class UnionFind {
    protected int[] p;  // 배열 크기는 정점의 수 N이고 p[i]는 i의 부모 원소를 저장한다.
    protected int[] rank;

    public UnionFind(int N) {
        p = new int[N];
        rank = new int[N];
        for (int i = 0; i < N; i++ {
            p[i] = i;  // 초기에 N개의 트리가 각각 i 자기 자신이 부모이기 때문에
            rank[i] = 0;  // 초기에 N개의 트리 각각의 rank를 0으로 초기화
        }
    }
    // i가 속한 집합의 루트 노드를 재귀적으로 찾고 최종적으로 경로상의 각 원소의 부모를 루트 노드로 만든다.
    protected int find(int i) { // 경로 압축
        if (i != p[i])
            p[i] = find(p[i]);  // 리턴하며 경로상의 각 노드의 부모가 루트가 되도록 만든다.
        return p[i];
    }
    // i와 j가 같은 트리에 있는지 검사
    public boolean idConnected(int i, int j) {
        return find(i) == find(j);
    }
    public void union(int i, int j) { // Union 연산
        int iroot = find(i);
        int jroot = find(j);
        if (iroot == jroot) return;  // 루트 노드가 동일하면 더이상의 수행없이 그대로 리턴
        // rank가 높은 루트 노드가 승자로 union을 수행한다.
        if (rank[iroot] ? rank[jroot]) {
            p[jroot] = iroot;  // iroot가 승자
        else if (rank[iroot > rank[jroot])
            p[iroot] = jroot;  // jroot가 승자
        else {
            p[jroot] = iroot;  // 둘 중 하나 임의로 승자
            rank[iroot]++;  // iroot의 rank 1wmdrk
        }
    }
}

최단경로(Shortest Paths) 알고리즘

Dijkstra 알고리즘

최단경로(Shortest Path) 찾기는 주어진 가중치 그래프에서 출발점으로부터 도착점까지의 최단경로를 찾는 문제로

Dijkstra 알고리즘은 출발점으로부터 각 정점까지의 최단거리 및 경로를 계산

// 배열 D를 \infin로 초기화 시킨다. 단, D[S] = 0 이다.
for (k = 0; k < N; k++) {
  //방문 안된 각 정점 i에 대해 D[i]가 최소인 정점 minVertex를 찾고, 방문한다.
    for (minVertex에 인접한 각 정점 w에 대해서) {
        if (/*w가 방문 안된 정점이면*/) {
            if (D[minVertex] + 간선(minVertex, w)의 가중치  < D[w]) {
                D[w] = D[minVertex] + 간선 (minVertex, w)의 가중치  // 간선완화
                previous[w] = minVertex
            }
        }
    }
}

• 간선완화(Edge Relaxation)는 minVertex가 선택된 후에, s로부터 minVertex를 경유하여 정점 w가지 경로의 길이가 현재의 D[w]보다 더 짧아지면 짧은 길이로 D[w]를 갱신하는 것을 의미

💡 greedy하게 정점을 선택하여 방문하고, 선택한 정점의 방문 안된 인접한 정점들 에 대한 간선완화를 수행한다.
한번 방문된 정점의 D원소 값은 변하지 않는다.

클래스

public class DijkstraSP {
    public int N;  // 그래프 정점의 수
    List<Edge>[] graph;
    public int[] previous;  // 최단경로상 이전 정점을 기록하기 위해
    public DijkstraSP(List<Edge>[] adjList) {
        N = adjList.length;
        previous = new int[N];
        graph = adjList;
    }
    public int[] shortestPath (int s) {
        boolean[] visited = new booelan[N];
        int[] D = new int[N];
        for (int i = 0; i < N; i++) {  // 초기화
            visited[i] = false;
            previous[i] -1;
            D[i] = Integer.MAX_VALUE;
        }
        previous[s] = 0;  // 시작점 S의 관련 정보 초기화
        D[s] = 0;
        for (int k = 0; i < N; k++) {
            int minVertex = -1;
            int min = Integer.Max_Value;
            for (int j = 0; j < N; j++) {
                if ((!viisted[j]) && (D[j] < min)) {
                    min = D[j];
                    minVertex = j;
                }
            }
            visited[minVertex] = true;
            for (Edge e: graph[minVertex]) {  // minVertex에 인접한 각 정점에 대해
                if (!visited[e.adjvertex]) {  // 아직 방문 안된 정점에 대해
                    int currentDist = D[e.adjvertex];
                    int newDist = D[minvertex] + e.weihgt;
                    if (newDist < currentDist) {
                        D[e.adjvertex] = newDist;  // 간선 완화
                        previous[e.adjvertex] = minVertex;  // 최종 최단 경로를 '역방향으로' 추출
                    }
                }
            }
        }
        return D;
    }
}

수행시간

• Dijkstra 알고리즘은 N번의 반복을 거쳐 minVertex를 찾고 minVertex에 인접하면서 방문되지 않은 정점들에 대해 간선 완화를 시도
• 이후 배열 D에서 minVertex를 탐색하는데 O(N)의 시간이 소요되고, minVertex에 인접한 정점들을 검사하여 D의 원소들을 갱신하므로 추가로 O(N) 시간이 소요
• 따라서 총 수행시간은 $N\times(O(N) + O(N)) = O(N^2)$

Bellman-Ford 알고리즘

Dijkstra 알고리즘은 음수가중치를 가진 그래프에서 최단 경로를 찾지 못함

Bellman-Ford 알고리즘은 음수 가중치 그래프에서도 문제 없이 최단 경로를 찾을 수 있음

단 입력그래프에 싸이클 상의 간선들의 가중치 합이 0보다 작은 음수싸이클(Negative Cycle)이 없어야 함
만약 어떤 경로에 음수싸이클이 존재한다면, 음수싸이클을 반복할 수록 경로의 길이가 더 짧아지는 모순이 발생하기 때문이다.

💡 입력그래프에 음수싸이클이 없으므로 출발점에서 각 정점까지 최단 경로상에 있는 간선의 수는 N-1개이다.
따라서 각 정점에 대해 간선완화를 N-1번 수행하면 더 이상 간선완화로 인한 갱신이 있을 수 없다.

// 배열 D를 ∞로 초기화 환다. 단, D[s] = 0, s는 출발점
for (k = 0; k < N - 1; k++) {
    // 각 (i, j)에 대하여
    if (D[j] > (D[i] + (i, j)의 가중치)) {
        D[j] = D[i] + (i, j)의 가중치 // 간선 완화
        previous[j] = i;
    }
} 

클래스

public class BellmanFord {
    public static final int INT= Interger.MAX_VALUE;
    private int D[];
    private int previout[];  // 경로 추출 위해
    priviate int N;

    public BellmanFord(int numOfVertics) {  // 생성자
        N = numOfVertices;
        D = new int[N];  // 최단거리 저장
        previous = new int[N];  // 최단경로 추출 위해
    }
    public void shortestPath(int s, int adjMatrix[][]) {
        for (int i = 0; i < N; i++) {
            D[i] = INF;  // 초기화
        }
        for (int k = 0; k < N-1; k++) { // 총 N-1번 반복
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (adjMatrix[i][j] != INF) {
                        if (D[j] > D[i] + adjMatrix[i][j]) {
                            D[j] = D[i] + adjMatrix[i][j];
                            previous[j] = i; // i 덕분에 j까지 거리 단축
                        }
                    }
                }
            }
        }
    }
    public void printPaths(int s) {
        // 생략
    }
}

수행시간

• Bellman-Ford 알고리즘은 그래프의 인접행렬을 사용하여 N-1번의 반복을 통해 각 간선 <i, j>에 대해 D[j]를 계산하므로 총 수행시간은 $(N-1) \times O(N) = O(N^3)$
• 인접리스트를 사용하면 $(N-1) \times O(M) = O(NM)$의 수행시간이 소요

[출처] 경기대학교 | 소프트웨어중심대학산업