그래프의 개념
그래프 용어 정리
- 동그라미 : 노드
- 화살표 : 간선
- 간선 위 숫자 : 가중
그래프의 특징과 종류
방향성, 가중치, 순환 특성에 따라 종류 구분
흐름을 표현하는 방향성
간선은 방향이 있는 것도(방향 그래프), 없는 것도 있다.(무방향 그래프)
흐름의 정도를 표현하는 가중치
시작과 끝의 연결 여부
순환 그래프, 비순환 그래프
그래프 구현
서울에서 부산으로 유동 인구 8,000명 발생.
그래프의 노드, 간선, 방향, 가중치로 연결해보기
- 데이터 담고 있는 노드 : 서울, 부산
- 노드 잇는 간선 : 서울과 부산 연결 유무
- 간선의 방향 : 서울 → 부산
- 간선의 가중치 : 8,000명
그래프의 구현 방식
1. 인접 행렬
2. 인접 리스트
인접 행렬 그래프 표현
: 배열을 활용하는 경우가 많음.
- 배열의 인덱스: 노드
- 배열의 값 : 가중치
- 인덱스의 세로 방향 : 출발 노드
- 인덱스의 가로 방향 : 도착 노드
즉,아래와 같은 의미이며
실제 코드에서는 값이 없을 경우(연결이 안되어있을 경우) -1로 저장
- 2차원 배열
| Index | 0 | 1 |
| 0 | 서울 → 서울 = -1 | 서울 → 부산 = 400 |
| 1 | 부산 → 서울 = -1 | 부산 → 부산 = -1 |
인접 리스트 그래프 표현
- 노드 개수만큼 배열 생성
- 배열의 인덱스는 각 시작 노드, 값은 다음 노드
♬ 자료 출처 - 책
코딩 테스트 합격자 되기 - 파이썬 편
이 포스팅의 모든 내용은 해당 책의 내용을 바탕으로 하고 있습니다.
감사합니다.
'프로그래밍 이야기 > 파이썬 코딩 테스트 스터디' 카테고리의 다른 글
| 파이썬 코딩테스트 스터디 8주차 #3 - 그래프 탐색 : 너비 우선 탐색 (0) | 2024.08.20 |
|---|---|
| 파이썬 코딩테스트 스터디 8주차 #2 - 그래프 탐색 : 깊이 우선 탐색 (0) | 2024.08.20 |
| 파이썬 코딩테스트 스터디 7주차 #5 - 전화번호 목록 (0) | 2024.08.11 |
| 파이썬 코딩테스트 스터디 7주차 #4 - 영어 끝말 잇기 (0) | 2024.08.11 |
| 파이썬 코딩테스트 스터디 7주차 #3 - 포켓몬 - 합격자가 되는 모의 테스트 (0) | 2024.08.09 |