그래프

그래프

그래프는 정점과 간선으로 이루어진다.
정점(vertext)은 연결의 대상이 되는 개체 또는 위치를 의미하고, 간선(edge)는 이들 사이의 연결을 의미한다.

• 무방향 그래프(undirected graph)
  방향성이 없는 그래프

• 방향 그래프(directed graph), 다이그래프(digraph)
  간선에 방향정보가 포함된 그래프

무방향 그래프와 방향 그래프는 간선의 연결형태에 따라서 완전 그래프(complete graph)로 구분이 된다.

• 완전 그래프(complete graph)
  각각의 정점에서 다른 모든 정점을 연결한 그래프
  정점의 수가 동일한 완전 그래프라도, 방향 그래프의 간선의 수는 무방향 그래프의 간선의 수에 두 배가 된다.
  

• 가중치 그래프(weight graph)
  간선에 가중치 정보를 둔 그래프
  가중치는 두 정점 사이의 거리라던가 두 정점을 이동하는데 걸리는 시간과 같은 정보가 될 수 있따.

• 부분 그래프(sub graph)
  어떤 그래프의 일부 정점 및 간선으로 이루어진 그래프

그래프의 집합 표현

그래프 G의 정점 집합
V(G)로 표시함

그래프 G의 간선 집합
E(G)로 표시함

무방향 그래프에서 정점 A와 정점 B를 연결하는 간선을 (A, B)로 표시한다.
무방향 그래프의 간선에는 방향성이 없으므로 (A, B)와 (B, A)는 같은 간선을 나타낸다.

방향 그래프의 간선에서 정점 A가 정점 C를 가리키는 간선을 <A, C>로 표시한다.

• V(G1) = {A, B, C, D} E(G1) = {(A, B), (A, C), (A, D), (B, C), (C, D)}

• V(G2) = {A, B, C, D} E(G1) = {(A, C), (A, D), (B, C)}

• V(G3) = {A, B, C, D} E(G1) = {<A, B>, <A, C>, <D, A>}

• V(G4) = {A, B, C, D} E(G1) = {<A, C>, <B, C>, <D, A>}

그래프 자료구조의 ADT

void	GraphInit(UALGraph *pg, int nv);
- 그래프의 초기화를 진행한다.
- 두 번째 인자로 정점의 수를 전달한다.

void	GraphDestroy(UALGraph *pg);
- 그래프 초기화 과정에서 할당한 리소스를 반환한다.

void	AddEdge(UALGraph *pg, int fromV, int toV);
- 매개변수 fromV와 toV로 전달된 정점을 연결하는 간선을 그래프에 추가한다.

void	ShowGraphEdgeInfo(UALGraph *pg);
- 그래프의 간선정보를 출력한다.

• 정점에 이름을 어떻게 부여할까?
  정점의 이름을 상수화한다.

enum {A, B, C, D, E, F, G, H, I, J};

실제 프로그램에서는 의미있는 이름을 부여하는 것이 옳다.

enum {SEOUL, INCHEON, DAEGU, BUSAN};

그래프를 구현하는 두 가지 방법

• 인접 행렬(adjacent matrix) 기반 그래프
  정방 행렬을 이용
• 인접 리스트 기반 그래프
  연결 리스트를 활용

정방 행렬은 가로세로의 길이가 같은 행렬을 의미한다. 이러한 행렬은 2차원 배열로 표현한다.

• 무방향 그래프의 인접 행렬 표현
  
  위 그림에서 보이듯이 정점이 4개이면 가로세로의 길이가 4인 2차원 배열을 선언한다. 그리고 두 정점이 연결되어 있으면 1, 연결되어 있지 않으면 0으로 표시한다.
  간선에 방향성이 없기 때문에 하나의 간선에 대해서 두 개의 지점을 1로 표시해야 한다.
  예를 들어 [m][n] = 1 이면 [n][m] = 1 이어야 한다.

• 방향 그래프의 인접 행렬 표현
  

• 무방향 그래프의 인접 리스트 표현
  
  

• 방향 그래프의 인접 리스트 표현