반응형
8. 정점과 간선 집합으로 표현한 그래프
그래프를 표현하는 방법은 다양합니다. 이차원 배열을 이용해서 인접 행렬로 표현하는 방법도 있고 정점과 간선의 집합으로 표현하는 방법도 있습니다.
이차원 배열을 이용해서 인접 행렬로 표현하는 방법은 정점의 개수가 n일 때 행과 열이 n인 이차원 배열을 만들고 두 개의 정점 사이의 거리를 배열의 항목 값으로 설정하는 형태로 작성합니다. 이 방법은 다른 책과 인터넷 검색 등을 통해 어렵지 않게 찾아볼 수 있을 것입니다. 하지만 그래프의 정점의 개수가 많으면 실제 정점과 정점 사이에 존재하지 않는 간선을 위한 부분이 전체의 많은 부분을 차지하여 메모리 효율과 수행 속도가 나빠질 수 있습니다.
이 책에서는 정점과 간선의 집합을 이용하여 그래프를 나타내는 방법을 사용할게요. 구현 비용은 인접 행렬을 이용하는 방법보다 어려울 수 있지만 유연성과 확장성 면 등에서 비교 우위에 있고 다른 책이나 인터넷 검색 등에서 인접 행렬로 구현한 것보다 쉽게 찾을 수 없기에 이 방법으로 소개할게요.
반응형
'언어 자료구조 알고리즘 > 디딤돌 자료구조 (C언어)' 카테고리의 다른 글
| [C언어 자료구조] 8.4 그래프 소스 코드 (0) | 2016.11.28 |
|---|---|
| [C언어 자료구조] 8.3 그래프 테스트 (0) | 2016.11.28 |
| [C언어 자료구조] 8.2 그래프 구현 (0) | 2016.11.28 |
| [C언어 자료구조] 8.1 그래프 설계 (0) | 2016.11.28 |
| [C언어 자료구조] 7.6 진입 차수, 진출 차수 소스 코드 (0) | 2016.11.28 |
| [C언어 자료구조] 7.5 진입 차수, 진출 차수 (0) | 2016.11.28 |
| [C언어 자료구조] 7.4 인접 행렬로 방향성 있는 그래프 소스 코드 (0) | 2016.11.28 |
| [C언어 자료구조] 7.3 인접 행렬로 방향성 있는그래프 (0) | 2016.11.28 |
| [C언어 자료구조] 7.2 인접 행렬로 방향성 없는그래프 소스 코드 (0) | 2016.11.28 |
| [C언어 자료구조] 7.1 인접 행렬로 방향성 없는그래프 (0) | 2016.11.28 |