그래프의 정의

각각의 단위 정보를 링크로 연결하여 구조화시킨 자료 구조를 그래프라 한다.


이 그림은 각 도시를 표현하는 단위 노드들을 링크로 연결한 것이다. 링크는 두개의 노드를 연결하여 링크의 양끝 노드가 서로 특정한 관계를 가지고 있음을 나타낸다. 여기서의 링크는 두 도시를 연결하는 도로가 있음을 표현해준다.
그래프에서 노드는 "vertex", 링크는 "edge"라 한다.
하나의 그래프는 다음과 같이 vertex와 edge의 집합으로 정의할 수 있다.
G=(V,E) , V= vertex집합 , E= edge집합

용어 설명

  1. 무향 그래프 (undirected graph)
  2. 유향 그래프 (directed graph)
  3. 완전 그래프 (complete graph)
  4. 인접성 (Adjacency)
  5. 경로 (path)와 순환 (cycle)
  6. 연결성 (connectivity)


edge에 방향성이 없어서 연결된 vertex들의 순서가 정해지지 않은 그래프를 말한다.
무향 그래프의 edge는 vertex쌍을 괄호로 묶어 표현한다.
(예) E={(A,B),(A,C),(A,D),(B,C),(B,D),(C,D)}
무향 그래프는 실선으로 edge를 표현한다.


<무향 그래프의 예>

유향 그래프(directed graph)

edge에 방향성이 있어서 연결된 vertex들의 순서가 정해진 그래프를 말한다.
유향 그래프의 edge는 vertex쌍을 각괄호로 묶어 표현한다.
(예) E={(A, B), (B, D), (D, C), (C, A)}
유향 그래프는 화살표로 edge의 방향을 표시한다.


<유향 그래프의 예>

완전 그래프(complete graph)

모든 vertex쌍을 연결하는 edge가 존재하는 그래프를 말한다.
완전 그래프는 같은 수의 vertex를 가지는 그래프들 중에서 가장 많은 edge를 가진다.
완전 그래프의 edge수 = n(n-1) /2 , n = vertex수


<완전 그래프의 예>

인접성(adjacency)

무향 그래프의 인접성
두개의 vertex가 edge로 연결되어 있으면 "인접해 있다"라고 한다.

유향 그래프의 인접성
두개의 vertex가 edge로 연결되어 있을때,edge의 방향에 따라 "~로 인접해있다", "~로부터 인접해 있다"라고 한다.


A는 B로 인접해 있다.
B는 A로부터 인접해 있다.

경로(path)와 순환(cycle)

그래프 내에서 특정 vertex Vi로부터 Vj까지 edge의 sequence를 경로라 한다.
무향 그래프의 경로(무향 경로): A-F-E-G-D

유향 그래프의 경로(유향 경로): A-B-E-F-G-D

경로의 길이 = 경로 내의 총 edge수
단순 경로 : 그래프 내의 모든 vertex를 지나는 경로: A-B-E-F-G-D-C

순환(cycle) : 시작점과 끝점이 연결된 경로: A-F-G-D-C-B

연결성(connectivity)

무향 그래프에서 모든 vertex쌍에 대해 경로가 존재하면 그 그래프는 "연결되었다"라고 한다.
서브그래프(subgraph)
그래프 G와 G'이 있을때 G'의 모든 vertex가 G의 vertex집합에 포함되고 G'의 모든 edge가 G의 edge집합에 포함되면 G'을 G의 서브그래프라 한다.

연결 성분(connected component)
한 그래프내에서 최대로 연결되어 있는 서브 그래프를 연결 성분이라 한다.

위 그림의 그래프는 연결되지 않은 그래프로서 2개의 연결성분 H1과 H2를 가진다.

차수(degree)
무향그래프에서의 차수
한 vertex에 연결된 edge의 수
유향그래프에서의 차수
인입치수(in-degree) : 한 vertex로 들어오는 edge의 수
인출치수(out-degree) : 한 vertex로부터 나가는 edge의 수

그래프의 표현 방법

인접 행렬(adjacency matrix)

각 vertex들간의 연결을 행렬로 표현한 것이다. 인접 행렬 M은 n x n 정방행렬로서 n은 그래프내의 vertex수이다. 행렬의 (i,j)원소 Aij가 1이면 vertex Vi와 Vj가 인접해 있는 것이고, Aij가 0이면 Vi와 Vj는 인접하지 않은 것이다.

인접 행렬의 문제점
인접 행렬로는 n(n-1)개의 edge를 표현할 수 있다. 그러나 실제로 그래프내의 edge수는 이보다 훨씬 적기 때문에 대부분의 행렬원소는 0의 값을 가진다. 따라서 완전 그래프처럼 edge가 많은 경우를 제외하고는 상당량의 기억장소가 낭비되는 문제가 있다. 이러한 문제를 해결하기 위해 인접 리스트를 사용한다.

인접 리스트(adjacency list)

각각의 vertex에 대해 인접한 vertex들을 연결 리스트로 표현한 것이 인접 리스트이다. 인접 리스트에는 n개의 연결 리스트가 존재하는 데 여기서 n은 그래프내의 vertex수이다. 어떤 리스트내에 vertex의 노드가 들어있으면 그 vertex들은 연결된 것이고, 들어있지 않으면 연결되지 않은 것이다.

인접 리스트의 장점
인접 리스트는 연결된 vertex들만 리스트로 관리하기 때문에 인접 행렬을 사용하는 경우처럼 비연결 vertex를 표현하기 위해 기억장소를 낭비하지 않는다.
인접 리스트의 단점
인접 리스트는 하나의 연결을 표시하기 위해 vertexi 정보뿐 아니라 링크 정보까지 사용되므로 edge의 수가 상대적으로 많은 경우 인접행렬을 사용할 때보다 기억장소 낭비가 심해질 수있다.

그래프 탐색

깊이 우선 탐색 (depth first search:DFS)

  1. 특정 vertex를 시점으로 선택한다.
  2. 선택된 vertex에 "방문"표시를 한다.
  3. 선택된 vertex에 연결된 여러 vertex들을 검사한다.
  4. 검사한 vertex들 중에 아직 방문하지 않은 vertex가 있으면 그 vertex를 새롭게 선택하고 원래 vertex는 스택에 넣는다.
  5. 검사한 vertex들 중에 방문하지 않은 vertex가 하나도 없으면 최종적으로 삽입된 vertex를 꺼내서 새롭게 선택한다.
  6. stack이 빌 때까지 2-5의 과정을 반복한다.

1-6의 과정이 끝나면 모든 vertex들을 한번씩 방문하게 된다.

너비 우선 탐색 (breadth first search)

  1. 특정 vertex를 시작점으로 선택한다.
  2. 선택된 vertex에 "방문" 표시를 한다.
  3. 선택된 vertex에 연결된 여러 vertex들을 검사하여 미방문 vertex들을 큐에 넣는다.
  4. 큐의 front에서 하나의 vertex를 꺼내어 새롭게 선택한다.
  5. 큐가 빌 때까지 2-4의 과정을 반복한다.

1-5의 과정을 끝내면 모든 vertex들을 한번씩 방문하게 된다.

최소비용 스패닝 트리 (minimum cost spanning tree)

스패닝 트리의 정의
최소비용 스패닝 트리의 성질
최소비용 스패닝 트리의 구성방법
Kruskal의 방법
Prim의 방법
sollin의 방법

스패닝 트리의 정의

특정 그래프 G의 서브그래프 중에서 G의 모든 vertex를 연결하는 트리를 스패닝 트리라 한다.

깊이 우선 탐색의 결과로 스패닝 트리가 만들어지는데 이것을 깊이 우선 스패닝 트리(depth first spannig tree)라 한다. 너비 우선 탐색의 결과로 스패닝 트리가 만들어지는데 이것을 너비 우선 스패닝 트리(breadth first spanning tree)라 한다.

스패닝 트리의 성질

스패닝 트리는 그래프의 모든 vertex는 포함하면서 연결되어 있는 최소 서브 그래프(minimal subgraph)이다.

최소비용 스패닝 트리의 성질

스패닝 트리의 각 edge에 가중치를 부여했을때 가중치의 총합의 가장 적은 스패닝 트리를 최소 비용 스패닝 트리라 한다. 최소비용 스패닝 트리는 다음과 같은 성질을 가진다.

  1. 그래프 내에 원래 있던 edge들만을 포함한다.
  2. vertex의 수가 n일때 n-1개의 edge만을 포함한다.
  3. 순환 (cycle)이 있어서는 안된다.

최소 비용 스패닝 트리 구성방법

kruskal의 방법
prim의 방법
sollin의 방법

kruskal의 방법

  1. 현재 edge들의 list에서 가중치가 가장 적은 edge를 선택한다.
  2. 선택된 edge로 두 vertex를 연결했을때 순환(cycle)이 생기면 edge를 버리고 그렇지 않으면 스패닝 트리에 삽입한다.
  3. 선택된 edge는 edge list에서 제거한다.
  4. edge list에 더이상의 edge가 남아 있지 않을때까지 1-3을 반복한다.

prim의 방법

  1. 현재 edge들의 list에서 가중치가 가장 적은 edge를 선택한다.
  2. 선택된 edge로 두 vertex를 연결했을때 순환(cycle)이 생기면 edge를 버리고 그렇지 않으면 스패닝 트리에 삽입한다.
  3. 기존의 spanning트리를 이루는 edge의 한 끝 vertex에 연결된 edge들을 검사한다.
  4. 검사한 edge들 중에서 아직 tree에 들어있지 않으면서 가중치가 가장 적은 edge를 선택한다.
  5. 선택된 edge는 edge list에서 제거한다.
  6. edge list에 더이상의 edge가 남지 않을 때까지 2-5를 반복한다.

sollin의 방법

  1. 각 vertex에 연결된 edge들 중에 최소 가중치를 가지는 edge들을 선택한다.
  2. 선택된 edge들 중 중복된 edge들을 제거한다.
  3. 나머지 edge들 중에서 최소 가중치 edge를 선택한다.
  4. 선택한 edge가 cycle을 이루면 그 edge를 버린다.
  5. 선택한 edge가 cycle을 이루지 않으면 트리에 삽입한다.