검색결과 리스트
글
<인접 행렬(adjacent matrix)>
행렬에 대한 2차원 배열을 사용하는 순차 자료구조 방법이다. 그래프의 두 정점을 연결한 간선의 유무를 행렬로 저장한다.
- n개의 정점을 가진 그래프 : n x n 정방행렬
- 행렬의 행번호와 열번호 : 그래프의 정점
- 행렬 값 : 두 정점이 인접되어있으면 1, 인접되어있지 않으면 0
무방향 그래프의 인접 행렬 : 행 i의 합 = 열 i의 합 = 정점 i의 차수
방향 그래프의 인접 행렬 : 행 i의 합 = 정점 i의 진출차수, 열 i의 합 = 정점 i의 진입차수
ex - 1)
G1
ex - 2)
G2
ex - 3)
G3
ex - 4)
[인접 행렬 표현의 단점]
- n개의 정점을 가지는 그래프를 항상 n x n개의 메모리 사용
- 정점의 개수에 비해서 간선의 개수가 적은 희소 그래프에 대한 인접 행렬은 희소 행렬이 되므로 메모리의 낭비 발생
Copyrightⓒ2014 By 한빛아카데미(주)
'Programming > Data Structure' 카테고리의 다른 글
| 정렬(sort) (0) | 2015.12.04 |
|---|---|
| 깊이 우선 탐색(depth first search : DFS) (0) | 2015.12.03 |
| 그래프(Graph) (0) | 2015.12.03 |
| 이진 탐색 트리(Binary Search Tree) (0) | 2015.12.03 |
| 이진트리 (0) | 2015.12.03 |
RECENT COMMENT