트리, 인접행렬, 인접리스트 (그래프를 코드로 그리는법 feat.컴공선배)

그래프의 종류중에서 순환성 없는 무방향 그래프를 트리라고 함 (수학적, 이론상 트리)

트리의 개념

 

위 트리는 실제 전산학, 자료구조에서 많이 쓰이는 트리임(이론적 트리와 다름)

 

스택,큐 등등은 구현해주는 라이브러리가 대부분의 언어에서 있지만 그래프는 따로 없어 직접 구현해줘야함

 

1번째 방법 인접행렬

 

방향성이 있을 경우

행은 시작 index, 열은 도착 index

두 노드를 잇는 간선이 있을 경우에는 1 없으면 0

 

방향성이 없을 경우

무방향은 양방향과 같은 의미임

즉 간선이 연결되어 있으면 양쪽으로 출발과 도착이 가능하다는 의미

 

2번째 방법 인접리스트(연결리스트)

 

방향성이 있을 경우

행렬과의 차이

행렬은 연결이 없으면 0으로 자리를 차지했지만 리스트는 연결이 있는 부분만 공간을 차지함

엄밀히 따지면 연결리스트지만 파이썬에서는 그냥 리스트(배열)로 처리함

 

방향성이 없을 경우

 

결론

 

인접행렬은 공간(메모리)을 많이 차지하고 시간이 적게듬

인접리스트는 공간을 적게 차지하고 시간이 많이듬