그래프

그래프

그래프는 노드와 그 노드를 연결하는 간선을 하나로 모아 놓은 자료구조입니다.

그래프 G는 G=(V,E)로 정의한다.

여기서 V는 공백이 아닌 노드(node) 또는 정점(vertex)의 유한 집합으로 이것만을 표현할 때는 V(G)라 표기하고, E는 상이한 두 정점을 잇는 간선(edge)의 유한 집합으로 이것만을 표현할 때는 E(G)라고 표기한다.

그래프는 무방향 그래프(undirected)와 유방향 그래프(directed)로 구분한다.

 

무방향 그래프(undirected graph)는 간선을 표현하는 두 정점의 쌍에 순서 즉 방향이 없는 그래프이다.

따라서 두 정점 V0과 V1을 잇는 간선 (V0, V1) 과 (V1,V0)은 똑같은 간선을 나타낸다. 보통 그래프라고 하면 이 무방향 그래프를 의미한다.

 

유방향 그래프(directed graph) 또는 방향 그래프는 다이그래프(digraph)라고도 하는데 모든 간선을 순서가 있는 두 정점의 쌍으로 표현하는 즉, 간선이 방향을 가진 그래프이다.

다이그래프에서는 하나의 간선 Vj -> Vk를 <Vj,Vk>로 표현하는데 Vj를 꼬리(tail), Vk(head)를 머리(head)라 한다. 따라서 <Vj,Vk>와 <Vk,Vj>는 서로 다르다.

방향 그래프에서는 이 간선을 아크(arc)라고도 한다.

 

다중 그래프 : 두 정정 사이에 복수의 간선이 존재할 수 있는 그래프

 

단순 그래프 : 두 정점 사이에 최대 하나의 간선이 있을 수 있는 그래프(이 포스팅에서는 단순그래프만 취급하겠습니다.)

 

완전 그래프 : 간선을 최대한으로 가진 그래프를 말한다.

n개의 정점을 가진 무방향 그래프의 최대 간선 수는 n(n-1)/2 이다. 그러나 n개의 정점을 가진 방향 그래프의 최대 간선 수는 n(n-1)이 된다.

(Vj,Vk)가 무방향 그래프G의 간선이라 할때 Vj와 Vk는 서로 인접(adjacent)하고 있다고 하고 간선 (Vj,Vk)는 정점 Vj 와 Vk에 부속(incident) 된다고 한다.

 

그래프 G가 방향 그래프라 하면 이 방향 경로(directed path)에 속한 <u,v1> , <v1,v2> ... <Vk, v> 는 그래프 G의 아크들이다.

경로 길이(path length)는 경로를 구성하는 간선의 수가 된다.

 

단순 경로(simple path)는 모두 상이한 간선들로 구성된 경로이다.

 

사이클(Cycle)은 첫 번째 정점과 마지막 정점이 동일한 단순 경로를 말한다.

 

방향 그래프에서 사이클이 없는 그래프를 DAG(directed acyclic graph)라고 한다.

 

방향 그래프 G에서 V(G)에 있는 서로 다른 모든 정점의 쌍u와 v에 대해 u에서 v까지의 방향 경로와 v에서 u까지의 방항경로가 있을때 강한 연결(Strongly connected)이라고 한다.  만일 이 때 u에서 v까지나 v에서 u까지 어느 하나의 경로만 있다면 약한 연결(weakly connected)이다.

강한 연결 그래프와 약한 연결 그래프

 

차수

• 정점의 차수(degree of a node)는 그 정점에 부속된 간선의 수를 말한다.
• 진입 차수(indegree)는 만일 그래프G가 방향 그래프라면 정점 V의 진입 차수는 정점 V를 머리로 하는 아크의 수
• 진출 차수(outdegree)는 만일 그래프G가 방향 그래프라면 정점 V의 진출 차수는 정점 V를 꼬리로 하는 아크의 수를 말한다.

 

그래프 표현

그래프는 여러 가지로 표현 할 수 있지만 3가지 방법 인접 행렬(adjacency matrix), 인접 리스트(adjacency list), 인접 다중 리스트 (adjacency multilist)을 알아보겠습니다.

 

인접 행렬

그래프 G = (V,E) 를 n >= 1개의 정점을 가진 그래프 일때, 그래프 G에 대한 인접 행렬 a는 크기가 NxN인 2차원 배열 a[N,N]으로서 다음과 같이 정의된다.

 

 

 

 

그래프G1,G2,G3를 인접 행렬로 표현

무방향 그래프에 대한 인접행렬은 간선의 특성상 대칭이 된다.

왜냐하면 간선 (i,j) ∈ E(G) 이면 반드시 간선 (j,i) ∈ E(G) 이기 때문이다.

 

이 인접 행렬을 가지고 어떤 두 정점 i와 j 사이의 간선(i,j)가 있는가는 쉽게 알 수 있다.

 

인접 리스트

인접 리스트로 그래프를 표현하는 방법은 n개의 정점 각각에 대해 인접한 정점들을 리스트로 만드는 것이다.

그러기 위해서는 이 리스트의 노드 구조를 vertex(정점)과 link 필드로 구성해야 한다.

그래야만 어떤 정점 i에 대한 인접 리스트에 정점 i와 인접한 정점들을 나타내는 노드들을 포함시키게 할 수 있다.

그래프 G1,G2에 대한 인접 리스트

각 정점의 리스트는 헤더 노드를 가지고 있고 리스트 헤더들은 배열을 이용하여 노드 번호의 오른차순으로 정렬되어 있다. 이렇게 하면 특정 정점에 대한 인접 리스트를 빠르게 접근할 수 있다.

n개의 정점과 e개의 간선을 가진 무방향 그래프의 경우 , 이 표현은 n개의 헤더 노드와 2e개의 리스트 노드가 필요하게 된다. 각 리스트 노드는 포인터 필드를 가지고 있다.

 

 

인접 다중 리스트

무방향 그래프의 인접 리스트 표현에서 각 간선(i,j)는 실제로 두 개의 노드가 포함 하게 된다. 

즉, 하나는 정점 i에 대한 인접 리스트의 노드이고, 또 하나는 정점 j에 대한 인접 리스트이 노드이다.

따라서 어떤 특별한 응용에 있어서는 특정 간선에 대한 두 번째 노드 접근을 할 때 그 간선을 이미 접근했었다는 것을 인지하기 위해 미리 마크를 해두는 것이 필요할 때가 있다.

이런 경우에 인접 리스트를 다중 리스트로 유지하면 쉽게 처리할 수 있다.

 

다중 리스트란 노드들을 여러 리스트들이 공용하는 리스트를 말한다.

이 다중 리스트에서는 각 간선 하나에 대해 하나의 노드가 만들어지고, 이 노드는 두 리스트 즉, 이간선이 부속된 두 정점 각각에 대한 인접 리스트에 의해 공용되는 것이다.

 

 

다중 리스트에서 간선 (i,j)를 표현하는 노드 구조

 

여기서 M은 마크 비트로써 이 간선이 이미 검사 되었는지 여부를 표시하는데 사용된다.

 

그래프 G1에 대한 인접 다중 리스트

 

그래프 순회

그래프에서 수행하는 연산 중 가장 중요한 것은 주어진 어떤 정점을 출발하여 체계적으로 그래프의 모든 정점들을 순회하는 것이다.

 

깊이 우선 탐색(DFS : Depth First Search)

무방향 그래프 G = (V,E)와 시작 정점 i에서 깊이 우선 탐색은 다음과 같이 수행 된다.

1. 정점 i를 방문한다.

2. 정점 i에 인접한 정점 중에서 아직 방문하지 않은 정점이 있으면 이 정점들을 모두 스택(Stack)에 저장한다.

3. 스택에서 정점을 삭제하여 새로운 i를 설정하고 다시 1단계 부터 수행한다.

4. 스택이 공백이 되면 연산을 종료한다.

이 연산을 구현하기 위해서는 정점들의 방문 여부를 표시해 두는 것이 필요하다.

이것은 배열 visited[n]을 이용하여 다음과 같이 표현 한다.

visited[i] = true(방문하였음) | false(방문하지 않았음)

 

루트 노드(혹은 다른 임의의 노드)에서 시작하여 다음 분기(branch)로 넘어가기 전에 분기를 완벽하게 탐색하는 방법

• 넓게 탐색하기 전에 깊게 탐색하는 것이다.
• 사용하는 경우 : 모든 노드를 방문하고자 하는경우에 이 방법을 선택한다.

너비 우선 탐색(BFS : Breadth First Search)

그래프 G=(V,E)에서 정점 i에서부터 시작하는 너비 우선 탐색(Breadth First Search)은 기본적으로 주어진 정점 i를 시작으로 그래프를 레벨별로 탐색하는 방법으로 다음과 같이 수행한다.

1. 정점 i를 방문한다.

2. 정점 i에 인접한 정점 중에서 아직 방문하지 않은 정점이 있다면 이 정점들을 모두 큐(Queue)에 저장한다.

3. 큐에서 정점을 삭제하여 새로운 i를 설정하고 다시 단계 1을 수행한다.

4. 큐가 공백이 되면 연산을 종료한다.

루트 노드(혹은 다른 임의의 노드)에서 시작하여 인접한 노드를 먼저 탐색하는 방법

• 깊게 탐색하기전에 넓게 탐색하는 것이다.
• 사용하는 경우 : 두 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 선택한다.

 

 

참고

 

자료구조와 c (도서)

 

gmlwjd9405.github.io/2018/08/13/data-structure-graph.html