그래프

그래프란?

그래프는 다음과 같이 연결되어있는 원소간의 관계를 표현한 자료구조이다. 이 그래프라는 것은 연결할 객체를 나타내는 정점(vertex)와 객체를 연결하는 간선(edge)의 집합으로 구성된다. 즉, 그래프 G를 G(V,E)로 정의하고, 여기서 V는 정점의 집합, E는 간선들의 집합을 의미한다.

그래프의 종류에는

그래프에는 크게 무방향 그래프(undirected graph)와 방향 그래프(directed graph)가 있는데,

1. 무방향 그래프는 두 정점을 연결하는 간선에 방향이 없는 그래프이다. 정점 V1, V2를 표현시에 (V1, V2)처럼 표현할 수 있고, 이는 (V2, V1)과 같은 간선을 나타낸다.
2. 방향 그래프는 간선에 방향이 있는 그래프이다. 정점 V1, V2를 연결하는 간선을 <V1, V2>로 표현하는데, 이때 V1을 꼬리, V2를 머리라고 한다. 그리고 <V1, V2>와 <V2, V1>는 서로 다른 간선이다.

그래서 그래프는 방향성이 있는 directed 그래프와 방향성이 없는 undirected 그래프로 나뉠 수 있다. 즉, 다음과 같이 나뉠 수 있다는 것인데, 이때 사실 트리도 그래프의 한 형태이다. 트리는 루트가 있고, 들어오는 곳이 한 지점이고, cycle이 없는 아래로만 흐르는 방향성 그래프이다. 하지만 그래프는 이러한 제약이 없는 것이 그래프이다. 트리도 사실 방향 화살표를 그려야하는데 트리는 항상 위에서 아래로 흘러서 그냥 생략한 것이다.

 

그리고 방향 그래프에는 자기 자신을 가리키는 self edge인 경우도 있다.

 

그 외에도 그래프에는 정말 다양한 종류가 있다. 하나하나 차근차근 알아보자. 먼저 완전 그래프(Complete Graph)는 한 정점에서 다른 모든 정점과 연결되어 최대 간선 수를 갖는 그래프이다. 따라서 정점이 n개인 완전 그래프에서 무방향 그래프의 최대 간선 수는 n(n-1)/2이고, 방향 그래프의 최대 간선 수는 n(n-1)이다.

 

또 부분 그래프(Subgraph)가 있는데, 이는 기존의 그래프에서 일부 정점이나 간선을 제외하여 만든 그래프이다.

 

가중 그래프(Weight Graph)도 있는데, 이는 정점을 연결하는 간선에 가중치(weight)를 할당한 그래프이다.

 

그리고 유향 비순환 그래프(DAG, Directed Acyclic Graph)가 있는데, 다음과 같이 방향 그래프에서 사이클이 없는 그래프라는 뜻이다.

 

또 연결 그래프(Connected Graph)와 단절(Disconnected Graph)가 있는데, 차이는 떨어져 있는 정점이 있냐 없냐의 차이가 있다.

 

 

그래프는 내부에 노드들이 cycle을 만드는 경우가 있고, 아닌 경우가 있는데, 하나 이상의 cycle이 있는 경우를 cyclic 그래프라고 하고, circle이 하나도 없는 경우를 Acyclic 그래프라고 한다.

 

또한 그래프를 표현하는 방법에는 2가지 방법이 있다. 하나는 Adjacency Matrix가 있고, 하나는 Adjacency List가 있다. 

이 때, Adjacency Matrix는 인접 행렬로 서로 연결되어있는 관계는 배열을 1로 채우고, 아닌 경우는 0으로 채운다.

그리고 Adjacency List는 배열방에 모든 노드들을 채워놓고, 각 배열 방에 있는 해당 노드와 인접한 노드들을 LinkedList로 채워넣는 것이다.

 

여기서 edge의 개수가 m개라고 할 때, 노드들은 관계를 나타내는 것이기 때문에 인접 리스트에 연결된 노드 개수는 2m개가 된다.

 

그래프 용어 정리

• vertex : 실세계에서의 어떤 대상을 표현하는 객체. 문헌에 따라서 vertex를 node라고 표현하기도 한다. vertex = node
• edge(간선) : vertex 간의 관계. 두 vertex간에 관계가 존재하는 경우, edge가 존재한다. 문헌에 따라서는 edge를 arc라고 표현하기도 한다.
  • edge에 방향 화살표를 추가하면 그래프에 방향성이 생기게 된다. 그렇게 노드 간의 관계는 에지와 화살표의 방향으로 정해지는데,  이때 arc를 방향성 에지라고 생각하면 된다.
• 그래프에서 두 정점 V1과 V2가 연결되어 간선 (V1, V2)가 있을때, 두 정점 V1과 V2를 인접(adjacency)하다고 하면, 간선 (V1, V2)는 정점 V1과 V2에 부속(incident)되어있다고 한다.
• degree(차수) : 정점에 부속되어 있는 간선의 수
  • 진입차수(in-degree) : 정점을 머리로 하는 간선의 수
  • 진출차수(out-degree) : 정점을 꼬리로 하는 간선의 수
• adjacent : 두 vertex 간에 edge가 존재함을 의미한다.
• path : 정점 V1에서 V2까지 간선으로 연결된 정점을 순서대로 나열한 리스트
  • Simple path(단순 경로) : 모두 다른 정점으로 구성된 경로
• length of path(경로 길이) : path를 구성하는 edge의 수
• connected : 두 vertex 간에 path가 존재함을 의미한다. 즉, 두 vertex 간에 직접적인 연결 뿐만 아니라 간접적인 연결이 존재하는 경우에 대해서도 포함된다.
• connected components : 상호 연결된 subgraph
• cycle : 단순 경로 중에서 경로의 시작 정점과 마지막 정점이 같은 경로

 

edge 표기법

(v1, v2)는 방향성이 없는 undirected graph이다. 이게 일반적으로 우리가 말하는 graph에 해당한다. <v1, v2>는 방향성이 존재하는 directed graph이다. 이를 digraph라고 표기하기도 한다. 물론 실세계의 data를 표현할 때는 방향성의 개념이 존재하기 때문에 directed graph의 개념이 존재한다. 그래프는 V, E의 집합이다. 따라서 G(V, E)로 표현하기도 한다.

 

그래프의 구현 방법

앞서 잠시 말했는데 그래프의 구현 방법에는 크게 인접 행렬로 구현하는 방법과 인접 리스트로 구현하는 방법이 있다.

그럼 각각의 특장점에 대해 한번 심도있게 알아보자.

 

인접 행렬이란 그래프의 정점을 2차원 배열로 만든 것이다. 즉, 노드의 개수가 n개라면 n*n 형태의 2차원 배열로 그래프의 연결 관계를 표현한다. 인접 행렬에서 행과 열은 노드를 의미하며, 각각의 원소들은 노드 간의 간선을 나타낸다. 정점간에 직접 연결되어 있다면 1, 아니라면 0을 저장한다. 

 

여기서 가중치가 없는 무방향 그래프와 가중치가 있는 유방향 그래프를 행렬로 구현하는 방법을 나뉠 수 있다.

가중치가 없는 무방향 그래프의 경우, 연결되어 있는 경우에는 행렬에서 1의 값을 가지고, 연결되지 않은 경우에는 0의 값을 가진다. 그래서 2개의 노드에서 간선이 동시에 연결되어 있기때문에 인접 행렬이 대칭 구조를 가진다.

반면에 가중치가 잇는 유방향 그래프는 행렬에서 각 간선의 가중치 값이 저장된다. 이 경우 가중치가 0인 것과 간선이 없는 것이 구별돼야 한다.

따라서 위와 같은 그래프가 있다면 인접 행렬은 다음과 같이 작성할 수 있는 것이다.

 

장점

• 2차원 배열에 모든 정점의 간선 정보가 담겨있기 때문에 두 정점에 대한 연결을 조회할 때는 O(1)의 시간 복잡도를 가진다.
• 인접 리스트에 비해 구현이 쉽다.

단점

• 모든 정점에 대해 간선 정보를 입력해야 하므로 인접 행렬을 생성 및 그래프의 모든 간선의 수를 알아내려면 O(n^2)의 시간 복잡도가 소요된다.
• 항상 n^2 크기의 2차원 배열이 필요하므로 필요 이상의 메모리 공간이 낭비된다.

 

그렇다면 이번엔 인접 리스트에 대해 알아보자. 인접 리스트는 아래왁 같이 그래프의 각 노드에 인접한 노드들을 연결 리스트(Linked List)로 표현한 것이다. 즉, 노드의 개수만큼 인접 리스트가 존재하며, 각각의 인접 리스트에는 인접한 노드 정보가 저장된다. 그래프는 각 인접 리스트에 대한 헤드 포인터를 배열로 갖는다. 여기서 헤드 포인터란 연결 리스트의 맨 처음 노드를 가리키는 포인터이다. 연결리스트는 다음과 같이 주로 정점의 리스트 배열을 만들어서 관계를 설정한다. 

 

다음과 같이 인접 리스트 역시 가중치가 없는 무방향 그래프와 가중치가 있는 유방향 그래프가 있는데, 전자는 가중치 표현없이 인접한 노드 정보가 저장된다. 반면에 후자는 종점[노드번호 | 간선의 가중치] 정보가 저장된다.

이러한 인접 리스트의 장단점은 다음과 같다.

• 장점: 존재하는 간선만 관리하므로 보다 메모리 사용이 효율적이다.
• 단점: 두 노드를 연결하는 간선을 조회하거나 노드의 차수를 알기위해서는 노드의 인접 리스트를 탐색해야 하므로 노드의 차수(degree(v))만큼의 시간이 필요하다.

이를 표로 정리하면 다음과 같다.

 

인용

https://juyoungit.tistory.com/568

Graph에 대한 개념정리 - 1

https://leejinseop.tistory.com/43

[자료구조] 그래프(Graph)의 개념 설명

https://velog.io/@falling_star3/%EA%B7%B8%EB%9E%98%ED%94%84Graph-%EC%9D%B8%EC%A0%91%ED%96%89%EB%A0%AC%EA%B3%BC-%EC%9D%B8%EC%A0%91%EB%A6%AC%EC%8A%A4%ED%8A%B8

[자료구조] 그래프(Graph): 인접행렬과 인접리스트