자료구조 - 그래프의 표현

소개글

자료구조론 그래프 표현법 입니다.

목차

그래프 표현의 개념
인접 행렬 표현법

인접 리스트 표현법(1)
인접 리스트 표현법(2)

인접 다중 리스트(1)
인접 다중 리스트(2)
인접 다중 리스트(3)

<Quiz(1)>
<Quiz(2)>
<Quiz(3)>

본문내용

그래프의 표현
그래프 표현의 개념
그래프는 수행하는 기능이나 응용 방법에 따라
다양한 방법을 이용하여 메모리 내에 표현할 수 있는데,
대표적으로 3가지 방법이 있다.
* 인접 행렬 (Adjacency Matrix) * 인접 리스트 (Adjacency List) * 인접 다중 리스트 (Adjacency Multi-List)?




인접 행렬 표현법
- 정점 집합 V(G)={ V1, V2… Vn}인 그래프 G=(V(G),E(G))의
인접 행렬(adjacency matrix)은 그래프를 구성하는 각 정점들 간의
인접 여부를 n×n의 2차원 배열로 표현한 것이다.
2차원 배열 A(i, j)에서 연결선 (Vi, Vj)가
E(G)에 속하면 A(i, j)=1이 되고, E(G)에 속하지 않으면 A(i, j)=0 이 된다.

.
.
인접 리스트 표현법(1)
- 이 표현법은 인접 행렬의 n개 행들을 n개의 연결 리스트로 표현한다.
즉, 그래프 G의 각 정점마다 1개의 연결 리스트가 존재하는데,
리스트 i에 있는 노드들은 정점 i로부터 인접되어 있는 정점들을 연결리스트로 나타낸다.

참고 자료

없음