[그래프]기본

기본 구성

점(Vertex)과 간선(Edge)으로 구성 됨 ( Point와 Line이 더 편한 영어표현이나, 알고리즘 책에서 더 많이 쓰는 단어표현이 Vertex, Edge)

그래프의 정의

 G(V,E)

표현 방법

3가지 표현 방법: 리스트, 행렬, 위치

1)리스트

  vector<list<int>> adj; //혹은 vector<vector<int>> adj;

희소(sparse) 그래프에 적절 : 연결된 Edge가 있는 경우만 list로 표현하기에 메모리 사용량 적음. but 연결여부 파악에는 시간 소모됨

2)행렬

 vector<vector<bool>> adj; 

밀집(dense) 그래프에 적절: 메모리는 O(V²)만큰 소모되지만, 두 Vertex간 연결여부를 O(1) 타임에 알 수 있음.

4)위치

  int p[100][100]

-끝-