[자료구조] Graph

그래프는 수학자 오일러(Euler)에 의해 창안되어 수학의 한 분야로서 수백 년 간 연구되어 왔지만, 컴퓨터 과학 분야에서 그래프 알고리즘을 다루기 시작한 것은 오래되지 않았다.

✏ 오일러 경로 (Eulerian Tour)

그래프에 존재하는 모든 간선을 한번만 통과하면서 처음 정점으로 되돌아오는 경로
→ 그래프의 모든 정점에 연결된 간선의 개수가 짝수일 때만 오일러 경로가 존재한다. (오일러의 정리)

실생활에서 다양한 예를 그래프로 표현할 수 있다(ex :지하철 노선도, 도심의 도로). 이런 식으로 활용할 수 있는 방법이 많기에 문제도 다양하게 출제를 할 수 있다. 그래프는 알고리즘에서 굉장히 많이 사용되며, 특히 그래프를 순회하는 방식인 DFS와 BFS를 잘 알아두어야 한다.


Graph

그래프

그래프는 정점과 간선으로 이루어진 자료구조로, 정확히는 정점(Vertex)간의 관계를 표현하는 조직도라고 볼 수 있다. 그런 면에서 트리는 그래프의 일종인 셈이다. 다만 트리와는 달리 그래프는 정점마다 간선이 없을수도 있고 있을수도 있으며 루트 노드, 부모와 자식이라는 개념이 존재하지 않는다. 또한 그래프는 네트워크 모델 즉, 객체와 이에 대한 관계를 나타내는 유연한 방식으로 이해할 수 있다.

💡 네트워크 모델
오브젝트와 이에 대한 관계를 나타내는 유연한 방식으로 이해할 수 있는 데이터베이스 모델 이다. 망 모형이라고도 한다.

Graph vs Tree
📌 Graph vs Tree


Graph의 구조

Untitled

  • 정점(vertice) : 노드(node)라고도 하며, 정점에는 데이터가 저장된다.
  • 간선(edge) : 링크(arcs)라고도 하며, 노드간의 관계를 나타낸다.
    • 인접 정점(adjacent vertex) : 간선에 의해 직접 연결된 정점
  • 경로(path) : 간선을 따라갈 수 있는 길을 말하며, 정점을 나열하여 표시한다.
    • 단순 경로(simple-path) : 경로 중 같은 간선을 지나가지 않는 경로
    • 경로의 길이 (length) : 경로를 구성하는 데 사용된 간선의 수
  • 차수(degree) : (무방향 그래프) 하나의 정점에 인접한 정점의 수
  • 진출 차수(out-degree) : (방향그래프) 한 노드 → 외부로 가는 간선의 수
  • 진입차수(in-degree) : (방향그래프) 외부 노드에서 들어오는 간선의 수
  • 사이클 (cycle) : 시작 정점과 종료 정점이 같은 단순 경로

💡 G = (V, E)
: 수학적으로 그래프를 표시하는 방법
V(G)는 그래프 G의 정점들의 집합을, E(G)는 그래프 G의 간선들의 집합을 의미한다.
https://blog.kakaocdn.net/dn/cAsGGY/btqSmBnwzDm/vzlZE0dyk1u4uswIvHZbjk/img.png
V(G1) = {0, 1, 2, 3}, E(G1) = {(0, 1), (0, 2), (0, 3), (1, 2), (2, 3)}
V(G2) = {0, 1, 2, 3}, E(G2) = {(0, 1), (0, 2)}
V(G3) = (0, 1, 2}, E(G3) = {<0, 1>, <1, 0>, <1, 2>}


Graph의 특징

  • 네트워크 모델이다.
  • 2개 이상의 경로가 가능하다. 즉, 노드들 사이에 무방향/방향에서 양방향 경로를 가질 수 있다.
  • self-loop 뿐 아니라 loop/circuit 모두 가능하다.
  • 루트 노드라는 개념이 없다.
  • 부모-자식 관계라는 개념이 없다.
  • 순회는 DFS나 BFS로 이루어진다.
  • 그래프는 순환(Cyclic) 혹은 비순환(Acyclic)이다.
  • 그래프는 크게 방향 그래프와 무방향 그래프가 있다.
  • 간선의 유무는 그래프에 따라 다르다.


Graph의 구현

그래프를 구현하는 방법에는 인접행렬 방식과 인접리스트 방식이 있다. 두개의 구현 방식은 상반된 장단점을 가지고 있으며, 대부분 인접리스트 형식이 많이 사용된다.

1. 인접행렬 방식

Adjacency Matrix

Untitled

Untitled

그래프의 정점을 2차원 배열로 만든 것이다. 정점의 개수가 n이라면 n*n 형태의 2차원 배열이 인접 행렬로 사용된다. 정점을 연결하는 노드에 다른 노드들이 인접 정점이라면 1, 아니면 0을 넣는다. (행, 열 : 정점 / 각각의 원소들 : 정점 간의 간선)

무방향 그래프는 (a), (b)에서 볼 수 있듯이 인접 행렬이 대칭적 구조를 가진다. (두 개의 정점에서 간선이 동시에 연결되어 있기 때문)

가중치 그래프의 경우 행렬에서 0과 1이 아니라 각 간선의 가중치 값이 저장된다. (이 경우 가중치가 0인 것과 간선이 없는 것이 구별돼야 함)

  • 장점
    • 2차원 배열에 모든 정점들의 간선 정보가 있기 때문에, 두 정점을 연결하는 간선을 조회할 때 O(1) 시간복잡도로 가능하다.

    • 정점(i)의 차수를 구할 때는 다음과 같이 인접행렬(M)의 i번째 행의 값을 모두 더하면 되므로 O(n)의 시간복잡도를 가진다.

      Untitled

    • 구현이 비교적 간단하다.
  • 단점
    • 간선의 수와 무관하게 항상 n² 크기의 2차원 배열이 필요하므로 메모리 공간이 낭비된다.
    • 그래프의 모든 간선의 수를 알아내려면 인접행렬 전체를 확인해야 하므로 O(n²)의 시간이 소요된다.


2. 인접리스트 방식

Adjacency List

Untitled

그래프의 각 정점에 인접한 정점들을 연결리스트(Linked List) 로 표현하는 방법이다. 즉 정점의 개수만큼 인접리스트가 존재하며, 각각의 인접리스트에는 인접한 정점 정보가 저장되는 것이다. 따라서 그래프는 각 인접리스트에 대한 헤드포인터를 배열로 갖는다.

무방향 그래프의 경우 간선이 추가되면 각각의 정점의 인접리스트에 반대편 정점의 노드를 추가해야 한다.

  • 장점
    • 존재하는 간선만 관리하면 되므로 메모리 사용 측면에서 보다 효율적이다.
    • 그래프의 모든 간선의 수를 알아내려면 각 정점의 헤더 노드부터 모든 인접리스트를 탐색해야 하므로 O(n+e)의 시간이 소요된다.
  • 단점
    • 두 정점을 연결하는 간선을 조회하거나 정점의 차수를 알기 위해서는 정점의 인접 리스트를 탐색해야 하므로 정점의 차수만큼의 시간 O(degree(v))이 필요하다. 즉, 배열보다 search 속도가 느려 인접행렬에 비해 시간이 오래 걸린다.
    • 구현이 비교적 어렵다.

https://blog.kakaocdn.net/dn/Nlh1G/btqKicb2Wub/sHWVSS6bn2FZdijEJVR2r1/img.png


인접 행렬 방식 vs 인접 리스트 방식

마치 어떻게 활용될지에 따라 ArrayList와 LinkedList를 고민하는 것처럼, 이 또한 상황에 따라 알맞은 방법을 선택해야 한다.

정점의 개수에 비해 간선의 개수가 매우 적은 희소 그래프(sparse graph)에서는 인접리스트가 유리할 수 있고, 모든 정점간에 간선이 존재하는 완전 그래프(Complete Graph)에서는 인접행렬이 유리할 수 있다.

만약 10억 개의 노드가 있고 각 노드가 2개씩의 간선만 있는 상황이다. 인접행렬로 구현한 그래프에서는 한 정점의 차수를 구할 때 10억번의 연산을 수행할 것이다. 반면, 인접리스트로 구현한 그래프에서는 2번의 연산만 수행하면 된다.

그래프에서 주로 어떤 연산이 수행되는지도 매우 중요하게 고려되어야 할 것이다.

Untitled


Graph의 종류

그래프는 구현되어진 특성에 따라 여러가지 종류로 나누어진다. 대표적인 그래프의 유형은 아래와 같다.

  • 무방향그래프 (Undirected Graph)

    Untitled

    두 정점을 연결하는 간선에 방향이 없는 그래프이며, 양 방향으로 이동이 가능하다. 위 그래프의 경우 (A, B)로 표현한다.

  • 방향 그래프 (Directed Graph)

    Untitled

    두 정점을 연결하는 간선에 방향이 존재하는 그래프이며, 간선의 방향으로만 이동할 수 있다. 위 그래프의 경우 <A, B>로 표현한다.

  • 가중치그래프 (Weighted Graph)

    Untitled

    간선에 비용(cost) 또는 가중치(weight)가 할당된 그래프이다. 네트워크(network)라고 불리기도 한다.

  • 완전그래프 (Complete Graph)

    Untitled

    모든 정점 간에 간선이 존재하는 그래프이다. 무방향 완전 그래프의 정점의 수가 n이라면, 전체 간선의 수는 n(n-1)/2 가 된다. 위 그래프의 경우 n=4이며 간선의 수는 (4*3)/2=6 이다.


Graph의 탐색

첫 정점에서부터 그래프에 존재하는 모든 정점들을 모두 한번씩 방문하는 것을 그래프 탐색이라고 합니다. 그래프 탐색의 방법은 깊이 우선 탐색(DFS) 방식과 너비 우선 탐색(BFS)방식이 있습니다.

https://blog.kakaocdn.net/dn/cFgEJ6/btqKmoJkq5a/pwm3O8T4rERuL4wSTrkgnK/img.gif

깊이 우선탐색(DFS)

깊이 우선탐색 DFS는 갈 수 있는 만큼 최대한 깊이 가고, 더 이상 갈 곳이 없다면 이전 정점으로 돌아가는 방식으로 그래프를 순회하는 방식입니다. 간단히 재귀호출을 사용하여 구현하거나 스택을 사용하여 구현합니다.

넓이 우선탐색(BFS)

넓이 우선탐색 BFS는 시작정점을 방문한 후 시작 정점에 인접한 모든 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선방문하는 방법입니다. 일반적으로 queue를 사용해서 지금 위치에서 갈 수 있는 것들을 모두 큐에 넣는 방식으로 구현합니다.


Connected Component

연결 성분

여러 개의 노드의 집합에서 간선으로 연결된 각각의 그래프를 의미한다.

Untitled

👉🏻 연결 성분을 찾는 방법
1) 그래프 상의 임의의 노드를 선택해 DFS 또는 BFS 탐색을 수행한다. (방문한 노드는 같은 성분으로 labeling한다.)
2) 남은 노드 중 방문하지 않은 노드를 선택하여 다시 1번을 수행한다.
3) 그래프의 모든 노드가 방문처리될 때까지 1, 2번을 반복한다. {: .notice}


Spanning Tree

신장 트리

그래프 내의 모든 정점이 연결되어 있으면서 사이클이 없는 트리를 의미한다. 신장 트리는 그래프의 n개의 정점을 정확하게 n-1개의 간선으로 연결하게 된다. 신장 트리를 구현하기 위해서는 DFS 또는 BFS 도중에 사용된 간선들만 남겨두면 된다.

즉, 이를 그림으로 표현하면 아래와 같다.

https://blog.kakaocdn.net/dn/bxCEfQ/btqSa96M8Ie/NmsKEidRSsctxhjwV2J1A0/img.png



참고자료