그래프📈
인접행렬과 인접리스트
(a)그래프 (b)인접리스트 (c) 인접행렬
- 인접행렬은 간선 수정에는 용이하지만, 정점 수정에는 넘넘 안 좋음...
- 인접그래프는 정점 수정에 용이하지만, 정점 연결 관계 확인을 위한 시간복잡도가 O(n)임 (인접행렬의 경우 O(1))
트리🌳
depth와 height
depth는 말그대로 깊이 위에서부터 얼마나 깊어졌는지.
height는 말그대로 높이 밑에서부터 얼마만큼의 높이에 있는지.
height: 베이스 라인이 아래에 있음
depth: 베이스 라인이 위에 있음
level: 베이스 라인이 위에 있음(depth + 1)
그래프와 트리의 차이
기본적으로는 트리가 그래프의 특수한 케이스라고 할 수 있을 것...
그래프: 네트워크모델 (부모-자식 관계 없음 / 루트노드 없음 / 다양한 경로 가능)
트리: 계층모델 (오직 하나의 경로 / 모든 자식 노드는 하나의 부모노드만 가짐 / 사이클 아니고 상하방향성 / 간선은 정점개수-1)
BST🌱
DFS와 BFS
여러가지 순회방법
부정확한 정보나 잘못된 정보는 댓글로 알려주시면 빠르게 수정토록 하겠습니다, 감사합니다!