Kang Chang Ryong

10 분 소요

이번 시간에는 그래프에 대해 알아보도록 하겠습니다.


Graph - 그래프란?

그래프(Graph)는 정점(Vertex)의 집합 V와 간선(Edge)의 집합 E로 구성된 비선형 데이터 구조이다.

먼저 그래프와 트리의 차이점을 살펴보면 다음과 같다.

구분 그래프(Graph) 트리(Tree)
정의 객체 혹은 노드(Node)와 그것을 연결하는 간선(Edge)으로 모인 구조 그래프의 한 종류이고 방향성이 없으며 순환하지 않음
방향성 무방향 혹은 유방향으로 가능 무방향 그래프
순환성 순환 가능 자기 자신을 연결하는 간선(Self-Loop) 가능 순환(Cyclic), 비순환(Acyclic) 모두 가능 순환 불가능 자기 자신 연결 간선(Self-Loop) 불가능 비순환 그래프(Acyclic Graph)
루트 루트의 개념이 있거나 없을 수 있음 하나의 루트 노드 존재
모델 네트워크 모델 계층 모델
순회 넓이 우선 탐색(BFS) 깊이 우선 탐색(DFS) 전위(Pre) / 중위(In) / 후위(Post) 순회 방식
간선수 그래프에 따라 다르며 없을 수도 있음 N개의 노드(Node)라면 N-1개


image

vertex와 edge가 정확히 무엇을 의미할까? 바로 아래에서 추가적인 용어를 다뤄 보도록 하겠다.

그래프에서 사용하는 용어

  • vertex(정점): 노드(Node)라고도 하며 정점에는 데이터가 저장된다.
  • edge(간선): 링크(arcs)라고도 하며 선을 통해 노드간의 관계를 나타낸다.
  • adjacent vertex(인접 정점): 하나의 정점에서 edge에 의해 직접적으로 연결된 정점을 나타낸다.
  • simple-path(단순 경로): 경로 중 반복되는 정점이 없는 것, 같은 간선을 지나지 않는 경로를 뜻한다.
  • degree(차수): 무방향 그래프에서 하나의 정점에 인접한 정점의 수를 의미한다.
  • out-degree(진출 차수): 방향 그래프에서 사용되는 용어로 한 노드에서 외부로 향하는 간선의 수를 뜻한다.
  • in-degree(진입 차수): 방향 그래프에서 사용되는 용어로 외부 노드에서 들어오는 간선의 수를 뜻한다.


그래프(G)는 정점들의 집합 V와 간선들의 집합 E를 사용하여(V, E)로 나타낸다.

  • G = (V, E)
  • V = {1, 2, 3, 4, 5}
  • E = {(1,2), (1,5), (2,3), (2,4), (2,5), (3,4), (4,5)}


앞에서 배운 트리 또한 그래프의 일종이지만 그래프는 트리 구조 보다 훨씬 더 넓은 범위를 다루고 있다.


그렇다면 그래프는 어디 쓰일까?

image

  • 네비게이션 길찾기
    • 우리가 흔히 사용하는 네이게이션 길찾기 기능이 그래프의 탐색을 이용한 기능이라고 할 수 있다.
  • 게임 내 캐릭터 이동
    • image-20220206144951900
    • 자료구조 및 알고리즘 첫 수업(OT) 때 잠깐 설명했단 게임 내 캐릭터 이동도 그래프라고 볼 수 있다.
  • 지식 그래프
    • 지식 그래프도 그래프의 일종인데 지식 그래프란 무엇일까?
      • 전통적인 방식에서 검색은 역새김이라는 방식으로 아이유, 피카츄… 이런 식의 키워드 기반으로 데이터를 저장하는데, 이렇게 하게 되면 아이유 혹은 피카츄를 검색했을 때 키워드에 대한 정보를 빠르게 얻을 수는 있지만 ‘아이유의 소속사 대표’ 와 같은 연결관계가 있는 것의 데이터는 찾기가 어렵다는 단점이 있었다. 지식 그래프는 각 객체의 연관성을 edge로 연결시켜서 키워드와 연결관계에 놓인 데이터들도 쉽게 찾을 수 있게 해 준다.
      • 이러한 연관관계를 잘 관리할 수 있는 것이 그래프이기 때문에 그래프를 사용하는 것이다.
  • 쾨니히스베르크의 다리 문제
    • 쾨니히스베르크의 다리 문제도 역시 그래프와 관련된 것이다.
    • image
    • 다음과 같은 다리가 있다고 하면 A, B, C, D 중에서 임의의 한 곳에서 출발 했을 때 모든 다리를 한 번씩 건널 수 있는가에 대한 문제인데 왼쪽 그림은 오른쪽처럼 나타낼 수 있다. 그리고 이 문제에 대한 답은 ‘그런 경우는 없다’ 로 났다.
    • 관심있으신 분들은 한 번 보시길 바란다. -> 쾨니히스베르크의 다리 건너기 문제


그래프의 종류

image

그래프는 vertex와 edge로 구성되어 있기만 하면은 굉장히 다양한 방법으로 그려질 수 있다. 그리고 특징에 따라 여러 그래프를 특정 지을 수 있다.


방향 그래프(Directed Graph)

image

  • 방향성(유향) 간선 (Directed edge)
    • 방향을 가진 정점의 쌍 (u, v)으로 화살표로 표현하고 단방향을 가리킨다.
    • 첫 번째 정점 u는 출발점을 의미하고 두 번째 정점 v는 도착점을 의미한다.
    • 방향성 간선을 가진 그래프를 방향성 그래프(Directed Graph)라고 한다.


  • 무방향성(무향) 간선(Undirected edge)
    • 방향이 없는 정점의 쌍(u, v)으로 직선으로 표현한다.
    • 무방향성 간선(u, v)와 (v, u)는 같다.(양방향을 가리킴)
    • 무방향성 간선을 가진 그래프를 무방향성 그래프(Undirected Graph)라고 한다.


image

이 방향 그래프에서는 반드시 화살표 방향으로만 노드간의 이동을 할 수 있다.


가중치 그래프

image

  • 노드 혹은 객체의 연결에 가중치가 부여된 형태의 경우를 의미하며 ‘네트워크’라고 불리기도 한다.

edge에 가중치가 부여된 그래프로 가중치는 양수와 음수 모두 될 수 있다.

위의 그림에서 A 부터 B까지 갈 수있는 경로는 두 가지이다.

  • A -> B
  • A -> C -> B

만약 가중치가 없다면 가장 적은 횟수로 갈 수 있는 첫번째 방법이 당연히 더 효율적일 것이다.

하지만 가중치 그래프이기 때문에 가중치를 비교해 보면 첫번째 방법은 ‘7’의 비용이 소모되고 두번째 방법은 총 ‘3’의 비용이 소모되기 때문에 두번째 방법이 더 효율적인 방법이 될 수 있는 것이다.

이렇게 가중치 그래프에서 한 vertex에서 다른 vertex까지 가는데 최단 거리를 알아내는 알고리즘으로 다익스트라 알고리즘(Dijkstra Algorithm)과 벨만-포드 알고리즘(Bellman-Ford)알고리즘을 사용할 수 있는데 다음 시간에 다익스트라 알고리즘에 대해서 배워볼 것이다.


루프 loop

image

그래프에서 vertex는 자기 자신으로 이어질 수도 있는데, 한 vertex에서 자기 자신으로 이어지는 edge가 있을 때 이것을 loop(루프)라고 한다.


순환 그래프(Cyclic Graph)

image

한 vertex에서 edge를 타고 가다보면 다시 그 vertex로 돌아오게 되는 그래프를 순환 그래프라고 한다.

첫 번째 그림은 모든 vertex가 순환 구조를 이루고 있고, 두 번째 그림은 일부분에서 순환 구조가 구성되어 있음을 알 수 있다.

반면, 순환이 되지 않는 그래프(사이클이 없는)는 Acyclic Graph(비순환 그래프)라고 하며 그래서 우리가 앞에서 배운 트리 구조는 순환이 없고 방향만 존재하는 Directed Acyclic Graph가 되겠다.


신장트리(Spanning Tree)

image

기존 그래프에 모든 노드가 연결되어 있으면, 트리의 속성을 만족하는 그래프로 트리의 속성을 만족하기 때문에 사이클이 존재하면 안된다.


최소 신장트리(Minimun Spanning Tree, MST)

image

위의 신장트리(Spanning Tree) 중에서 edge의 가중치 합이 최소인 신장트리를 의미한다.


희소 그래프 (Sparse Graph) & 밀집 그래프 (Dense Graph)

  • 희소 그래프는 노드 수보다 간선 수가 적은 그래프를 말한다.
  • 밀집 그래프는 노드 수보다 간선 수가 큰 그래프이다.

image

완전 그래프(Complete Graph)

  • 그래프에 속한 모든 정점들이 상호 연결된 그래프
  • n개의 정점의 수가 있는 경우 간선의 수는(n - 1)*n/2개가 된다.

image


차수(Degree)란?

무방향 그래프에서는 단순히 차수(Degree)를 계산한다. 즉, 특정 vertex에 연결된 간선의 갯수를 차수라고 보는 것이다.

아래의 그림에서 2번 정점은 연결된 간선이 3개이기 때문에 차수가 3이다.

image


유방향 그래프에서는 내차수(In-Degree)와 외차수(Out-Degree)를 계산한다. 내차수는 현재 정점 방향으로 들어오는 간선의 갯수이며, 외차수는 현재 정점에서 다른 정점 방향으로 나가는 간선의 갯수이다.

아래의 그림에서 4번 노드는 내차수가 2이고 외차수가 1임을 알 수 있다.

image


그래프 알고리즘 방법

그래프는 일반적으로 두 가지 방식으로 표현한다.


  1. 인접 행렬

  • 그래프에 간선이 많이 존재하는 밀집 그래프(Dense Graph)의 경우 사용한다.
  • 2차원 배열에 저장하는 방법이다.
  • 노드 수보다 간선 수가 많은 dense graph이거나 빠르게 부속(incident)된 간선을 찾을 때 주로 사용한다.
  • 아래와 같은 그림에서 연결된 vertex는 숫자 ‘1’이 데이터로 들어가고 연결되지 않은 vertex는 숫자 ‘0’ 혹은 음수가 들어가게 된다.


image

image

위 그래프에서는 한 vertex가 자기 자신으로 들어가는 edge(즉, Loop)가 존재하는 vertex가 있지 않기 때문에 자기 자신과의 데이터 A-A, B-B, C-C, D-D 모두 0인 것을 볼 수 있다.

  • 각 정점이 인접하다면 1을 저장하고 그렇지 않다면 0을 저장하는 방식


방향성 그래프

image


무방향성 그래프

image


가중치 그래프

가중치 그래프를 인접행렬로 표현하면 다음과 같고 가중치가 0인 경우와 대비하기 위해서 ∞로 표시하기도 한다.

image


  • 인접행렬 장점
    1. 이차원 배열 안에 존재하는 모든 정점(vertex)들의 edge(간선) 정보를 담기 때문에 배열의 위치를 확인할 수 있다면 두 점에 대한 연결 정보를 조회할 때 O(1)의 시간 복잡도를 갖는다.
    2. 구현이 비교적 간단하게 진행된다.


  • 인접행렬 단점
    1. 모든 정점에 대해 edge 정보를 대입해 주어야 하므로 O(n2)의 시간 복잡도가 소요된다.
    2. 무조건 이차원 배열이 필요하기 때문에 사용되지 않는 쓰레기 공간이 생기게 되어 메모리 사용이 비효율적이다.


  1. 인접리스트

  • 그래프 내에 적은 숫자의 간선(Edge)만을 가지는 희소 그래프(Sparse Graph)의 경우 사용한다.
  • vertex의 갯수만큼 리스트를 사용한다. 그래서 자신을 기준으로 연결된 vertex를 리스트에 저장하게 되는 방식이다.

image

image

각 vertex별로 리스트가 생성이 되고 그 안의 객체로는 자기 자신과 연결된 vertex의 값이 들어가게 된다.


방향성 그래프

image


무방향성 그래프

image


가중치 그래프

image


  • 인접리스트의 장점
    1. vertex들의 연결 정보를 탐색할 때 O(n)의 시간만 가능하다. (n은 edge의 갯수입니다.)
    2. 연결리스트를 사용하여 필요한 만큼의 공간만을 사용하기 때문에 메모리상으로 인접행렬보다 효율적이다.


  • 인접리스트의 단점
    1. 특정 두 점이 연결되었는지 확인하기 위해서 인접행렬보다 많은 시간이 소요된다. (배열보다 탐색 속도가 느리기 때문)
    2. 구현이 인접행렬에 비해서는 다소 어렵다.


인접 리스트 vs. 인접 행렬

방식 특징 공간 복잡도 시간 복잡도
인접 리스트 특정 정점을 접근하기 위해 리스트를 모두 확인해야 한다. 각 정점의 List에 간선 수 만큼 저장하여 O(E) 리스트에 각 정점에 연결된 간선의 개수 만큼 저장되므로 O(E)
인접 행렬 특정 정점의 연결에 대해 배열로 한 번에 접근 가능하다. V개의 정점의 수만큼 2차원 배열을 만들기에 O(V2) 배열이 V x V형태가 되기 때문에 특정 정점의 0이 아닌 경우를 모두 찾아야 하기 때문에 O(V)


따라서 인접행렬과 인접리스트를 적절히 섞어가면서 사용하는 것이 가장 좋다.


그래프 구현

  • 인접행렬 방식

먼저 그래프를 구현하기에 앞서 interface를 살펴보자.

package graph;

import ...
    
public interface IGraph {
    
    void add(int from, int to);
    void add(int from, int to, Integer distance); //가중치 노드
    Integer getDistance(int from, int to);
    Map<Integer, Integer> getIndegrees(); //<노드, 차수의 수>
    Set<Integer> getVertexes();
    List<Integer> getNodes(int vertext):
}

위 코드가 다른 자료구조 구현과 조금 다른 점이 있다면 그래프 interface는 제네릭 타입으로 선언하지 않았다.

이는 그래프 자체의 구조에 대해 이해를 돕기 위해 integer 정수 타입의 자료만 받아 구현을 할 것이기 때문이다.


package graph;

import java.util.*;

public class AdjacencyMatrixGraph implements IGraph {
    
    ...
}


멤버변수

private Integer[][] matrix;
private Set<Integer> vertexs;
private Map<Integer, Integer> indegrees;

그래프의 연결 정보를 저장하기 위한 matrix(2차원 배열)와, 그래프의 vertex들의 정보를 저장하기 위한 vertexes(Set), 차수의 정보를 저장하는 indegrees(Map) 를 선언한다.

  • vertexes는 중복을 피해야 하기 때문에 Set 형이다.
  • indegrees에 대해 더 설명을 하자면
    • indegrees.get(3) = 5 는 ‘노드 3을 가르키는 노드의 갯수가 5개’라는 뜻이다.


생성자

public AdjacencyMatrixGraph(int numOfVertex) {
    this.vertexes = new HashSet<>();
    this.indegrees = new HasgMap<>();
    this.matrix = new Integer[numOfVertex][];
    for (int i = 0; i < numOfvertex; i++) {
        this.matrix[i] = new Integer[NumOfVertext];
    }
}

멤버 변수로 선언한 값들에 대한 초기화가 이루어진다.

  • 인접행렬 방식 그래프를 생성할 때는 vertex의 갯수를 인자로 받는다.
  • 갯수만큼의 행렬을 만들어 준다.


add

@Override
public void add(int from, int to, Integer distance) {
    this.vertexes.add(from);
    this.vertexes.add(to);
    int count = this.indegrees.getOrDefault(to, 0);
    indegrees.put(to, count + 1)
        
    matrix[from][to] = distance;
}

from과 to를 vertex(노드) 정보에 추가를 한다. 이는 각각 출발점과 도착점을 의미한다.

  • vertexes는 set 형식이기 때문에 중복된 데이터가 들어오면 저장을 진행하지 않는다.


이제 차수 정보를 추가한다.

  • Map 구조에 데이터가 이미 있을 수도 있고 없을 수도 있기 때문에 count 변수에 to 값을 넣거나 to 값이 없으면 0을 넣는 과정을 진행한다.(getOrDefault)
  • getOrDefault(a, b): 배열의 a 번째 index를 가져오거나 없는 경우 b를 가져온다.


indegrees에 key, value가 각각 to, (count + 1) 인 정보를 추가한다.

마지막으로 matrix의 vertex간의 연결정보를 저장하면서 마무리한다.

@Override
public void add(int from, int to) {
    this.vertexes.add(from);
    this.vertexes.add(to);
    int count = this.indegrees.getOrDefault(to, 0);
    indegrees.put(to, count + 1)
        
    matrix[from][to] = 1;
}

나머지 코드는 동일하고 distance를 받지 않는 경우이기 때문에 default값인 1을 넣어준다.

만약 양방향 그래프인 경우 from - to 에만 데이터를 넣는 것이 아니라 to- from에도 데이터를 넣어주어야 한다.

연결이 되지 않는 경우는 null을 넣어준다.


getNodes(int vertex)

@Override
public List<Integer> getNodes(int vertex) {
    List<Integer> result = new ArrayList<>();
    for (int i = 0, i < this.matrix[vertex].length; i++) {
        if (this.matrix[vertex][i] != null) {
            result.add(i);
        }
    }
    return result;
}

getNode()메소드는 인자로 입력 받은 값이 가리키고 있는 노드들을 가져오는 메소드이다.

matrix[vertex] [i]는 vertex가 from, i가 to가 되어 vertex가 가리키는 i가 null이 아니라면, 즉 다시말해서 가중치가 얼마가 되는 지는 모르지만 값이 존재하기만 하면 result 리스트에 추가를 해 준다.


그외의 get 메소드

@Override
public Integer getDistance(int from, int to) {
    return this.matrix[from][to];
}

@Override
public Map<Integer, Integer> getIndegrees() {
    return this.indegrees;
}

@Override
public Set<Integer> getVertexes() {
    return this.vertexes;
}

멤버 변수를 가져옴으로써 쉽게 구현 가능하다.


  • 인접리스트 방식

package graph;

import java.util.*;

public class AdjacencyListGraph implements IGraph {
    
    ...
}

인접리스트는 노드(연결리스트)를 사용하여 구현해 보도록 하겠다.


노드 inner class

private class Node {
    Integer from;
    Integer to;
    int weight;
    
    Node(int from, int to) {
        this.from = from;
        this.to = to;
        this.weight = 1;
    }
    
    Node(int from ,int to, int weight) {
        this.from = from;
        this.to = to;
        this.weight = weight;
    }
}

노드 클래스에는 출발 정보와 도착 정보, 가중치 정보가 들어 있어 이를 초기화 시킨다.


멤버 변수

private List<List<Node>> graph;
private Set<Integer> vertexes;
private Map<Integer, Integer> indegrees;

인접리스트 방식은 vertex의 수만큼 리스트를 만드는 방식인데 해당 리스트를 graph라는 변수로 선언하였고 나머지 vertexes와 indegrees변수는 인접행렬 구현 때 했던 것과 동일한 기능의 변수이다.


생성자

public AdjacencyListGraph(int numOfVertexe) {
    this.vertexes = new HashSet<>();
    this.indegrees = new HashMap<>();
    this.graph = new ArrayList<>(numOfVertex);
    for (int i = 0; i < numOfVertex; i++) {
        this.graph.add(new ArrayList<>());
    }
}

멤버변수로 선언한 변수들에 대한 초기화 과정을 진행한다.

add

@Override
public void add(int from, int to, Integer distance) {
    vertexes.add(from);
    vertexes.add(to);
    
    int count = indegrees.getOrDefault(to, 0);
    indegrees.put(to, count + 1);
    List<Node> neighbors = this.graph.get(from);
    neighbors.add(new Node(from, to, distance))
}

인접행렬과 비슷한 방식으로 진행이 된다.

단지 인접리스트는 그래프의 형식이 리스트의 리스트로 리스트가 리스트 형식으로 나열되어 있다.

바깥 리스트의 index의 번호가 노드의 번호가 된다.


예를 들어, 아래와 같은 상황에서

  • 0 -> [1, 2, 3]
  • 1 -> [2]
  • 2 -> [0, 1]
  • 3 -> []

0 번 노드는 1, 2, 3번 노드를 가리키고 있고 1 번 노드는 2번 노드를 가리키고 있고 2번 노드는 0번과 1번 을 가리키고 있으며 3번 노드는 아무 노드도 가리키고있지 않다는 것을 의미한다.

그래서 from의 노드를 get하여 neighbors에 출발정보와 도착정보, 거리가 들어있는 노드를 저장을 하면 연결 정보가 추가가 된다.


@Override
public void add(int from, int to) {
    vertexes.add(from);
    vertexes.add(to);
    
    int count = indegrees.getOrDefault(to, 0);
    indegrees.put(to, count + 1);
    List<Node> neighbors = this.graph.get(from);
    neighbors.add(new Node(from, to))
}

위의 과정과 같고 distance 변수만 빼 준다.


getNodes(int vertex)

이 메소드도 인접행렬의 방식과 유사하다.

@Override
public List<Integer> getNodes(int vertex) {
    List<Integer> nodes = new ArrayList<>();
    for (Node node: this.graph.get(vertex)) {
        nodes.add(node.to);
    }
    return nodes;
}

parameter(인자) vertex가 가리키고 있는 노드들의 정보를 리턴한다.


getDistance(int from, int to)

@Override
public Integer getDistance(int from, int to) {
    for (Node node : this.graph.get(from)) {
        if (node.to.equals(to)) {
            return node.weight;
        }
    }
    return null;
}

from이 가리키고 있는 노드 중에서 to 노드의 weight를 반환한다.


그 외의 get메소드

@Override
public Map<Integer, Integer> getIndegrees() {return this.indegrees;}

@Override
public Set<Integer> getVertexes() {return this.vertexes;}


Summary

사실상 그래프 알고리즘 문제에서 가장 중요한 것은 특정 노드에 연결된 모든 노드를 찾는 것이라고 한다.

따라서 공간도 적게 사용하면서 위 경우 탐색 시간도 빠른 인접 리스트가 훨씬 많이 사용된다.


시간 복잡도

  • 공간 복잡도

인접 행렬: O(V2)

인접 리스트: O(V + E)


  • 시간 복잡도
  1. 두 노드가 연결 되었는지 확인하는데 걸리는 시간

인접 행렬: O(1)

인접 리스트: O(V)

  1. 한 노드에 연결된 모든 노드들을 확인하는데 걸리는 시간

인접 행렬: O(V)

인접 리스트: O(E)


BFS의 설명은 이곳을 참조

DFS의 설명은 이곳을 참조

Dijkstra 알고리즘의 설명은 이곳을 참조

Topological 정렬의 설명은 이곳을 참조


위 알고리즘은 코딩테스트에서 자주 나오는 단골문제이므로 잘 알아두어야 한다.

댓글남기기

참고