자료구조 정리 #2 트리(Tree), 그래프(Graph), DFS, BFS

 

비선형구조

1. 트리 (Tree)

사이클(순환)이 없는 연결된 그래프입니다. 트리를 구성하는 노드 간에는 단순 경로가 존재하는 특징이 있습니다. 여기서 단순 경로란 지나왔던 접점을 다시 지나지 않는 경로 입니다.
우리가 주로 쓰는 간단한 예시로는 폴더 구조가 있습니다.

트리는 일반트리와 이진트리가 있습니다. 차이로는 이진트리는 2개 이상의 노드가 존재하지 않는 구조라 생각하면 쉽습니다. ( 이진트리 - 각 노드가 최대 두개의 자식을 갖는 트리 )

트리의 큰 특징으로는
1. 방향성 있음.
2. 각 노드는 어떤 자료형으로도 표현이 가능
3. 사이클이 존재 할 수 없다.(하나의 연결 그래프)
4. 트리는 이진 트리, 이진 탐색 트리, 균형트리 등이 있습니다.

출처 : https://daeguowl.tistory.com/111

 

출처 : https://daeguowl.tistory.com/111

 

2. 그래프 (Graph)

그래프란? 노드와 노드를 연결하는 간선을 하나로 모아놓은 자료구조 입니다.
추상적인 개념의 연결 관계를 표현하기 위해서 많이 사용합니다.
도시를 연결하는 도로망이나 웹 사이트간의 링크 관계에 사용하고 있습니다.

그래프의 특징으로
1. 네트워크 모델
2. 2개 이상의 경로가 가능
3. 부모 - 자식 관계라는 개념이 없음
4. 그래프는 크게 방향 그래프와 무방향 그래프가 있습니다.
5. 순회는 DFS나 BFS로 이루어 진다.
6. 그래프는 순환 or 비순환이다.

 

- 무방향 그래프

 

- 방향그래프

깊이 우선탐색(DFS)

깊이 우선탐색 DFS는 갈 수 있는 만큼 최대한 깊이 가고, 더 이상 갈 곳이 없다면 이전 정점으로 돌아가는 방식으로 그래프를 순회하는 방식입니다. 간단히 재귀호출을 사용하여 구현하거나 스택을 사용하여 구현합니다. 

 

넓이 우선탐색(BFS)

넓이 우선탐색 BFS는 시작정점을 방문한 후 시작 정점에 인접한 모든 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선방문하는 방법입니다. 일반적으로 QUEUE를 사용해서 지금 위치에서 갈 수 있는 것들을 모두 큐에 넣는 방식으로 구현합니다.