열혈 자료구조 - 14.1 그래프의 이해와 종류

그래프의 역사

- 쾨니히스베르크의 다리 문제 : 모든 다리를 한 번씩만 건너서 처음 출발하는 장소로 돌아올 수 있는가 -> 불가능하다는 것을 밝혀낸 것이 그래프의 역사와 관련이 있음

- 지역을 정점, 다리를 간선이라고 말함

- 정점 별로 연결된 간선의 수가 짝수여야 한번씩만 지나서 돌아올 수 있음

- 그래프는 정점과 간선으로 표현하는 방법을 가르킴

그래프의 종류

- 무방향 그래프 : 방향성이 없는 그래프

    -> 우측과 같이 정점이 모두 연결된 그래프를 완전 그래프라고 함

- 방향 그래프 : 방향성이 있는 그래프

- 가중치 그래프 : 간선에 가중치를 담아서 표현

- 부분 그래프 : 일부 정점과 간선으로 구성된 그래프

 

그래프의 집합 표현

- 정점의 집합을 V(G), 간선의 집합을 E(G)로 표현

- 방향성이 없는 경우 괄호로 묶고, 방향성이 있는 경우 부등호로 묶고 간선의 시작 부분을 먼저 표현

 

그래프의 ADT

- 초기화 : 인자로 정점의 수를 전달

void GraphInit(UALGraph* pg, int nv);

- 소멸

void GraphDestory(UALGraph* pg);

- 간선 추가

void AddEdge(UALGraph* pg, int fromV, int toV);

- 간선 정보 출력

void ShowGraphEdgeInfo(UALGraph* pg);

- 정점 정보는 enum으로 상수화

enum {A,B,C,D,E};
enum {SEOUL, INCHEON, DAEGU, BUSAN};

 

그래프의 구현 방법

- 인접 행렬 기반

    -> 정점의 수만큼 2차원 배열을 만들어 연결 정보를 표현

    -> 방향성이 있을 경우 도착 정점에만 표현을 해줌

- 인접 리스트 기반

    -> 정점별로 연결 리스트를 형성하여 연결된 정점 정보를 표현

    -> 방향성이 있을 경우 도착 정점만 표현을 해줌