TIL10: Data Structure - 3 [ Graph ]
Nodeadjacency listadjacency matrixbig o notationdirectededgeundirectedvertex간선노드무방향성방향성빅오 표기법인접 리스트인접 행렬정점
0
Immersive Course TIL
목록 보기
10/39
Graph(그래프)
- 특징: Vertex(정점 또는 노드(Node)), 그리고 노드와 노드를 연결하는 Edge(간선)으로 구성되는 자료 구조
- 종류
- 방향성: Undirected(무방향성), Directed(방향성)
- 구현방식: Adjacency Matrix(인접 행렬), Adjacency List(인접 리스트)
- 구현 구조
- 인접 리스트: 각 노드를 key, 그리고 간선들을 element로 가지는 Array를 value로 하는 Object 구조
- 인접 행렬: 각 노드들을 행과 열로 가지는 2차원 Array 구조
- <인접 리스트> Big O 표기
- 가져오기: O(V)
- 정점 추가하기: O(1)
- 정점 삭제하기: O(V+E)
- 간선 추가하기: O(1)
- 간선 삭제하기: O(E)
- <인접 행렬> Big O 표기
- 가져오기: O(1)
- 정점 추가하기: O(V**2)
- 정점 삭제하기: O(V**2)
- 간선 추가하기: O(1)
- 간선 삭제하기: O(1)
자료 출처: javatpoint.com
