728x90
Graph
-
[CS] Graph, TreeComputer Science/CS 2022. 11. 28. 18:44
트리 ⊂ 그래프 그래프 노드(하나의 점)와 노드 간을 연결하는 간선으로 구성된 자료 구조이다. 순환 혹은 비순환 구조를 이룬다. 그래프의 구현 방법은 2가지 방식이 있습니다. - 인접 행렬(adjacency matrix) : 2차원 배열을 사용하는 방식 - 인접 리스트(adjacency list) : 리스트를 사용하는 방식 두 방식의 메모리와 속도 차이는 다음과 같습니다. V : 노드의 개수, E : 간선의 개수 일 때, 인접 행렬은 O(v^2), 인접 리스트는 O(E) 만큼의 메모리 공간이 요구됩니다. 인접 행렬은 O(1), 인접 리스트는 O(V)만큼의 시간이 소요됩니다. 트리 그래프와 같이 노드와 노드 간을 연결하는 간선으로 구성된 자료 구조이다. 트리는 두 개의 노드 사이에 반드시 1개의 경로만을 ..