그래프 (1) 용어, 표현

graph: G = (V, E)

 

정점(vertex, node) - 어떤 대상물이나 개념

간선(edge) - 관계

 

subgraph

adjacent

path

cycle

simple path: 노드가 중복되지 않는 path

simple cycle: 시작점이자 끝점인 노드 외에 어떤 노드도 중복되지 않는 cycle(다른 중복되는 노드가 있다면 그 노드가 subcycle의 시작점이자 끝점이 됨. 즉 simple cycle은 subcycle이 없음)

connected cycle: 어떤 두 노드를 잡아도 그 사이에 path가 있는 그래프

complete cycle: 모든 노드 사이에 간선이 있는 그래프

directed graph(digraph)

undicrected graph

adjacency

multigraph: 노드 사이에 간선이 두개 이상 있는 그래프. 보통 그래프에서 제외되는 개념

loop: 노드 자기 자신으로 이어지는 간선이 있는 그래프. 보통 그래프에서 제외되는 개념

 

adjacency matrix vs adjacency list

adjacacy matrix는 특정 연결성을 알아내는데(즉 한 노드와 다른 노드가 연결되 있는지 알아내는데) O(1)의 시간이 걸리는 대신 공간 복잡도가 O(|V|^2)이다. 이는 matrix 자체를 만드는데 O(|V|^2)만큼의 시간 복잡도가 든다는 의미이기도 하다.

 

반면 adjacency list(배열 + 연결리스트)는 공간 복잡도가 O(|E|) 인 대신 연결성을 알아내는데 걸리는 시간 복잡도가 O(K)이다. 여기서 K는 한 슬롯(배열의 원소)이 가지는 연결 리스트의 길이이다. K는 평균적으로 2|E|/|V|이다.

 

이를 개선하기 위해 adjacency list를 배열+배열의 형태로 나타내는 방법이 있다. 이때 각 슬롯의 배열을 counting sort로 정렬하면 O(K)의시간 복잡도로 정렬이 가능하므로 binary search( O(log_2(K)) ) 의 이점을 가져가는 동시에 배열 자체를 만들 때 드는 시간 복잡도도 줄이지 않을 수 있다.

 

또 binary search보다 더 적은 시간에 연결성을 확인하는 자료구조로 나타내고 싶다면 각 슬롯에 해시 테이블을 연결하면 된다.(배열 + 해시 테이블)

 

 

✅ adjacency matrix에서 연결되지 않은 상태를 나타낼 때 0, inf, -inf 세 가지가 상황에 따라 선택된다.

 

✅counting sort

www.youtube.com/watch?v=7zuGmKfUt7s