[면접 준비] 그래프와 트리 비교 설명하기

학습 키워드: graph, tree

 

2024-08-07 면접 카타 질문

그래프(Graph)와 트리(Tree)를 설명하고, 둘의 차이점을 설명해주세요:

 그래프는 정점(vertex) 노드가 간선(edge)으로 연결되어있는 데이터 구조입니다. 간선의 방향 유무에 따라 directed/undirected 그래프로 나뉘고, 간선의 가중치 유무에 따라 weighted/unweighted 그래프로 나뉩니다. 하나의 노드에서 다른 노드까지 가는 길이 하나 이상일 수 있는 순환 구조가 발생하기도 합니다.

 

 트리는 하나의 루트(root) 노드가 여러개의 자식(child) 노드를 가져 마치 나무가 가지를 뻗어나가는 형태를 띄는 일종의 그래프 구조입니다. 각 노드가 한 개의 부모 노드에서 파생되기 때문에 순환 구조가 발생하지 않습니다. 기본적으로 부모 노드의 정보를 저장하지 않기 때문에 방향 그래프지만, 만약 노드가 부모 노드의 정보를 가지고 있다면 무방향 그래프가 되기도 합니다.

 

 

--