14-2. 그래프 표현법, 추상자료형

02. 추상자료형

그래프의 추상자료형

- 그래프 객체의 정의:정점과 간선의 유한 집합

연산 :

① GraphCreat() ::= 그래프 생성

② Destroy(Graph) ::= 그래프 기억장소 반납

③ GraphCopy_Tree(Graph) ::= 그래프 복사

④ InsertVertex() ::= 그래프에 정점 삽입

    InsertEdge() ::= 그래프에 간선 추가

⑤ DeleteVertex() ::= 정점 삭제

    DeleteEdge()::=간선 삭제

⑥ Search() ::= 정점 탐색

⑦ IsAdjacent() ::= 인접 정점 여부 확인

⑧ ExistPath() ::= 경로가 존재하는지 확인

⑨ PathLength() ::= 경로 길이 계산

⑩ BFS() ::= 너비 우선 탐색

⑪ DFS() ::= 깊이 우선 탐색

 

 

03. 그래프 표현법

그래프의 두 가지 표현방법

- 인접 행렬

- 인접 리스트

 

 

인접 행렬에 의한 그래프 표현

- G = ( V, E)가 n개의 정점을 가진 그래프라고 가정함

- 그래프 G 는 n × n 행렬로 표현되고 다은과 같이 행렬값을 가짐

- 가중 그래프의 인접 행렬 표현

- 간선 { v_i, v_j } ( 방향 그래프라면 (v_i, v_j))의 가중치가 w_ij 일때, 인접행렬 요소 a_ij 는 아래와 같음

 

 

인접 리스트에 의한 그래프 표현

- 정점의 개수가 n인 그래프에 대하여,인접 행렬의 n행을 n개의 연결 리스트로 나타내는 방법

- 리스트 i 의 각 노드들은 정점  에 인접되어 있는 정점들을 나타냄

- 각 리스트 들은 헤드 노드를 가지며,헤드 노드들은 자신의 인접 정점을 순차적으로 가리키고 있음

 

 

 

 

정리하기

- 정점 집합 V와 간선 집합 E에 대하여 그래프는 G=(V,E)입니다. 즉, 대상(V)과 그 대상들의 관계(E)를 나타내는 수단입니다.

- 방향 그래프는 간선의 방향이 유의미한 그래프로 예를 들어 부자 관계를 그래프로 나타내면 간선은 유의미 합니다.

- 무방향 그래프는 간선의 방향이 무의미한 그래프로 예를 들어 두 지점 사이에 도로가 있는 지 아닌지를 그래프로 나타내면 간선은 무의미합니다. 단, 도로가 일방통행로라면 간선의 방향은 의미를 갖고 그 그래프는 방향 그래프로 나타내야 합니다.

- 두 정점쌍이 간선을 여러 개 가질 수 있는 그래프를 다중 그래프라 합니다. 예를 들어 두 지점사이에 여러 교통수단이 있다면 다중 그래프로 나타 낼 수 있습니다.

- 두 정점을 잇는 간선이 중요도나 비용 등을 나타내는 가중 값을 갖는 그래프를 가중 그래프라고 합니다. 예를 들어 두 지점 사이를 연결 하는 도로의 거리가 중요한 의미를 갖는 문제라면 그 그래프는 가중 그래프로 표현해야 합니다.

- 두 정점을 잇는 간선 열을 경로라 합니다. 그리고 경로에 있는 간선의 수를 그 경로의 경로 길이로 정의합니다.

- 한 정점에서 출발하여 자신으로 연결하는 간선을 루프라고 합니다. 예를 들어 입력에 따라 상태가 변하는 시스템을 그래프로 나타내는 경우 어떤 입력에 대해서는 상태가 변하지 않는다면 루프로 표현할 수 있습니다.

- 시작점과 끝점이 같은 경로를 사이클이라 합니다. 그리고 하나 이상의 사이클을 갖는 그래프를 사이클이 있는 그래프 혹은 사이클 그래프라 하고 사이클이 없는 그래프를 무 사이클 그래프 혹은 트리라고 합니다.

- 두 정점이 간선으로 연결되었을 때 두 정정이 인접한다고 표현합니다. 두 정점이 잇는 경로가 있다는 것과 반드시 구분해야 합니다.

- 그래프의 표현방법의 하나로 정점 사이의 인접성을 행렬로 나타낸 것을 인접행렬 표현법이라 하고 정점 사이의 인접성을 연결 리스트로 나타낸 것을 인접 리스트 표현법이라 합니다. 그래프가 정점 개수에 비하여 간선 개수가 적으면 연결 리스트로 나타내야 기억 장소를 효율적으로 사용할 수 있습니다.