3.5 Graph & 3.6 Tree

CS - 3. Common Algorithms - 3.5 Graph & 3.6 Tree

Graph Algorithms

💡Graphs in data structures are non-linear data structures made up of a finite number of nodes or vertices and the edges that connect them. Graphs in data structures are used to address real-world problems in which it represents the problem area as a network like telephone networks, circuit networks, and social networks.

데이터 구조의 그래프는 한정된 수의 노드 또는 정점과 이를 연결하는 가장자리로 구성된 비선형 데이터 구조입니다. 데이터 구조의 그래프는 전화망, 회로망, 소셜 네트워크와 같이 문제 영역을 네트워크로 표현하는 실제 문제를 해결하는 데 사용됩니다.

 

Tree Algorithms

💡A tree is non-linear and a hierarchical data structure consisting of a collection of nodes such that each node of the tree stores a value and a list of references to other nodes (the “children”).

Here is the list of common tree algorithms:

 

트리는 비선형적이며 노드 모음으로 구성된 계층적 데이터 구조로, 트리의 각 노드가 값과 다른 노드에 대한 참조 목록("자식")을 저장합니다.

 

 

1.2 그래프 와 1.8 트리를 자료구조에서 다뤘습니다.

https://parkpakrsu.tistory.com/327

Data structures (with python) - 2. Graph - 2.1. Directed graph

https://parkpakrsu.tistory.com/336

Data structures (with python) - 8.Tree - 8.1 Binary Tree

둘다 node와 edge로 이뤄진 노드간의 관게를 나타내는 자료 구조입니다.

 

그래프와 트리는 모두 데이터를 표현하는 자료구조이지만, 그 성격과 특징에 있어서 몇 가지 중요한 차이점이 있습니다.

그래프(Graph): 그래프는 노드(Node)와 이들을 연결하는 간선(Edge)으로 구성됩니다. 

그래프는 노드 간의 관계를 나타내는 데 유용하며, 노드와 간선은 각각 객체와 객체 간의 관계를 나타냅니다. 그래프는 방향성이 있을 수도 (방향 그래프), 없을 수도 (무방향 그래프) 있으며, 순환(사이클) 구조를 가질 수도 있습니다. 즉, 그래프에서는 시작 노드에서 출발해 다시 같은 노드로 돌아올 수 있습니다.

트리(Tree): 트리는 그래프의 한 종류로, 노드와 간선으로 이루어져 있지만, 몇 가지 추가적인 제약 조건이 있습니다.

트리는 한 개의 루트 노드에서 시작되며, 루트 노드에서 다른 모든 노드로의 경로가 유일합니다. 이는 트리가 순환 구조를 가질 수 없음을 의미하며, 따라서 트리에서는 어떤 노드에서 시작해 다시 같은 노드로 돌아오는 경로가 존재하지 않습니다. 또한, 트리는 방향성이 있으며, 일반적으로 루트 노드에서 다른 노드로 '내려가는' 방향성을 가집니다.

이러한 차이점들로 인해, 그래프와 트리는 각각 다른 종류의 문제를 해결하는 데 적합합니다. 

그래프는 네트워크 구조를 모델링하거나 최단 경로 문제를 해결하는 데,

트리는 계층적인 데이터를 표현하거나 검색 작업을 빠르게 수행하는 데 유용합니다.

 

 

앞으로 다뤄볼 그래프 알고리즘과 트리 알고리즘의 종류는 이렇습니다.

 

Graph algorithm

- Breath First Search

- Depth First Search

- Bellman Ford's Algorithm

- Dijkstra's Algorithm

- A* Algorithm

 

Tree algorithm
- Pre-Order Traversal
- In-Order Traversal
- Post-Order Traversal
- Breadth First Search
- Depth First Search

 

확실히 트리는 검색작업을 빠르게 수행하는데 유용하다고 했는데, 트리 알고리즘의 내용은 순회와 탐색이 주를 이룹니다.