그래프 정의
- 그래프 G(V, E)는 어떤 자료나 개념을 표현하는 정점(vertex)들의 집합 V와 이들을 연결하는 간선(edge)들의 집합 E로 구성된 자료구조입니다.
-트리는 계층적으로 연결되는 일방향
그래프 특징
그래프 종류
- 방향 그래프vs무향 그래프 (코테에 가장 많이 등장)
일방향 vs 양방향 - 다중 그래프 vs단순 그래프
여러개의 간선 vs 하나의간선 - 가중치 그래프 => 다익스트라
그래프 활용
현실 세계의 사물이나 추상적인 개념 간의 연결 관계를 표현한다.
그래프는 현실의 문제를 해결하기 위한 도구로써 유용하게 이용된다 => 문제가 많이 나온다.
- 도시들을 연결하는 도로망: 도시(vertex), 도로망(edge)
- 지하철 연결 노선도: 정거장(vertex), 정거장을 연결한 선(edge)
- 컴퓨터 네트워크: 각 컴퓨터와 라우터(vertex), 라우터간의 연결 관계(edge)
- 소셜 네트워크 분석: 페이스북의 계정(vertex), follow 관계(edge)
그래프 표현 방법
- 인접 리스트 (adjacency list)
- 인접 행렬 (adjacency matrix)
- 암시적 그래프 (implicit graph)
1.인접행렬 (adjacency matrix)
그래프는 vertex와 edge의 연결 관계
- 특징
대각선 = 0
대칭
0인 간선 표현으로 메모리 낭비가 심하다
2. 인접리스트 (adjacency list)
활용도 높고 많이 사용
키값에 vertex 이름
연결되있는 리스트
3. 암시적 그래프 (implicit graph)
제일 많이 쓴다
예)미로찾기 문제
위와 같은 그래프로 생각해볼 수 있다.
