자료구조- 인접행렬, 인접리스트

둘다 배우는이유 ? 장단점이 있기때문 

왜 여러가지 자료를 배울까..

 

--학생들 대답 --

인접리스트

특정 정점과 간선을 추가하는데 불리할까? 

=> 링크드리스트로 구현할필요는 없음.. 1차원배열로 동적으로 생성가능 . 추가시 불리하지 않고, 맨앞에 추가할수있기때문에 시간복잡도도 동일함

 

간선이 많은경우.. 시간이 오랠걸릴 가능성이 있음 ?

=>  인접행렬도 비슷함.. 

---

 

 

자료구조란

어떤 연산을 제공하는 자료를 담고있으면서 

질문을 던질때마다 

그질문에 대한 대답을 해주는 친구

 

던지는 질문 == 연산 

 

여러개의 자료구조를 배우는이유

각 자료구조마다 똑같은 연산이어도 누구는 빠르게 하고 누구는 느리게 하기때문 

 

 

정점의 개수 V (10만) , 간선의 개수  E (50만)

	인접행렬	인접리스트
공간복잡도	가로세로    V²    (100억)	간선추가할때마다 2개씩 추가  1개 간선마다 메모리 2개    2 x E  ( 100만)
u - v 사이 정점 존재하는지? 질문을 던진다	상수 시간 걸림 u행 v열값 읽어오면 됨   O(1)	u 번 정점리스트에 가서  v 원소가 존재하는지 일일이 순회  O(V)
u랑 연결된 모든 정점을 다 찾고싶다	u 행 하나씩 순회하며 1값의 위치를 찾는다  O(V)	u 번 정점 리스트를 읽기만 하면됨  실제로 정점 u 와 연결된 개수만큼이 정확하게 걸림 O(deg(u)) : u 의 차수  차수: 그 정점과 연결된 정점의 개수
결론	1. u행 v 열 값을 읽어오는 계산이 많으면 인접행렬로 그래프를 저장한다!	1. u 와 연결된 정점을 찾아오는 행위를 많이 하는 문제 인접리스트로 그래프를 저장한다.