인접 리스트

• 연결 리스트를 여러개

• 0 {1,2,3}
• 1 {0}
• 2 {0,1}
• 3 {0}

===> adj라는 변수를 사용하게 될 예정

• 정점마다 adj가 있다.
• 1000번짜리 정점

예시

• 정점 10개
• visited : 방문

• 연결하려는 정점이 있고 방문하지 않았다면 go함수 작동
• 연결되는 정점이 방문되었다면 컨티뉴
  • 아니라면 there

인접행렬 vs 인접리스트

• 인접행렬 : 공간복잡도 v^2
• 인접리스트 : O(V+E)

(최악의)시간복잡도

인접행렬 - O(1)

인접리스트 - O(V)

그래프가 희소할때는 인접리스트 , 조밀할때는 인접행렬이 좋다.

희소하다 = Sparse하다.

• 0인 것이 많으면 낭비다.

• dense하면 인접행렬이 낫다.