1020 TIL

그래프(Graph):

• 그래프는 정점(vertex)과 간선(edge)의 집합으로 구성된 수학적 구조입니다.
• 정점은 객체 또는 개체를 나타내고, 간선은 정점 간의 관계를 나타냅니다.
• 그래프는 방향 그래프(Directed Graph) 또는 무방향 그래프(Undirected Graph)로 나뉠 수 있으며, 간선에 방향이 있는 경우 방향 그래프, 없는 경우 무방향 그래프라고 합니다.

1. 방향 그래프 (Directed Graph):
   • 방향 그래프는 간선에 방향이 있는 그래프로, 간선은 한 정점에서 다른 정점으로 향하는 방향을 가집니다.
2. 무방향 그래프 (Undirected Graph):
   • 무방향 그래프는 간선에 방향이 없는 그래프로, 간선은 두 정점을 양방향으로 연결합니다.

1. Vertex (정점):
   • 정점은 그래프에서 가장 기본적인 구성 요소 중 하나입니다.
   • 정점은 그래프 내에서 한 지점 또는 위치를 나타내며 일반적으로 원, 점 또는 노드로 표현됩니다.
   • 그래프 내의 객체 또는 엔터티를 나타내는데 사용됩니다. 예를 들어, 소셜 네트워크의 사용자, 도시 지도의 교차로, 컴퓨터 네트워크의 라우터 등을 정점으로 표현할 수 있습니다.
2. Edge (간선):
   • 간선은 그래프 내에서 두 개의 정점을 연결하는 연결선입니다.
   • 간선은 두 정점 간의 관계를 나타내며 방향이 있는 경우 방향성을 가질 수 있습니다.
   • 예를 들어, 소셜 네트워크에서 친구 관계, 도로 지도에서 도로, 인터넷에서 두 장치 간의 연결 등을 간선으로 표현할 수 있습니다.
3. Node (노드):
   • "노드"는 "정점"을 나타내는 용어 중 하나이며, 주로 네트워크와 관련된 컴퓨팅 분야에서 사용됩니다.
   • 노드는 그래프의 정점을 의미하며 네트워크에서 노드는 단일 장치, 서버, 컴퓨터, 라우터 또는 다른 네트워크 관련 장치를 나타냅니다.
4. Arc (아크):
   • "아크"는 방향 그래프(Directed Graph)에서 사용되는 용어로, 방향성을 가진 간선을 의미합니다.
   • 아크는 하나의 정점에서 다른 정점으로의 방향을 나타내며 흔히 화살표로 표시됩니다.
   • 방향 그래프에서 정보의 흐름이나 연결 관계를 표현할 때 사용됩니다.

이러한 용어는 그래프 이론과 네트워크 분야에서 다양한 응용 분야에 적용되며, 데이터 구조, 경로 탐색, 네트워크 분석, 알고리즘 등과 관련된 다양한 문제를 해결하는 데 사용됩니다.

 

 

전위 순회 (Preorder Traversal), 중위 순회 (Inorder Traversal), 후위 순회 (Postorder Traversal)는 이진 트리(Binary Tree)와 그래프의 일부 구조를 탐색하고 데이터를 검색하는 세 가지 주요 트리 순회 방법입니다. 이러한 순회 방법은 트리의 노드를 언제 방문할지에 따라 다릅니다. 각 순회 방법에 대한 설명은 다음과 같습니다:

1. 전위 순회 (Preorder Traversal):
   • 전위 순회는 트리 순회 방법 중 가장 일반적인 방법 중 하나입니다.
   • 전위 순회에서는 루트 노드를 먼저 방문하고, 그 다음에 왼쪽 서브트리를 전위 순회하고, 마지막으로 오른쪽 서브트리를 전위 순회합니다.
   • 전위 순회는 트리를 깊이 우선 탐색(DFS)하는 방법 중 하나이며, 루트 노드를 먼저 처리하는 것이 특징입니다.
2. 중위 순회 (Inorder Traversal):
   • 중위 순회는 이진 탐색 트리(Binary Search Tree)에서 특히 중요한 순회 방법입니다.
   • 중위 순회에서는 루트 노드를 중간에 방문하고, 왼쪽 서브트리를 중위 순회한 뒤에 루트 노드 다음에 오른쪽 서브트리를 중위 순회합니다.
   • 중위 순회는 이진 탐색 트리의 노드를 오름차순으로 방문하는 데 사용됩니다.
3. 후위 순회 (Postorder Traversal):
   • 후위 순회에서는 루트 노드를 가장 나중에 방문하며, 먼저 왼쪽 서브트리를 후위 순회하고, 그 다음에 오른쪽 서브트리를 후위 순회합니다.
   • 후위 순회는 서브트리의 연산을 먼저 수행한 후 루트 노드를 방문하는 경우에 유용합니다.
   • 후위 순회는 트리의 노드를 깊이 우선 탐색 중 루트 노드를 가장 나중에 처리하는 방법입니다.

이러한 세 가지 순회 방법은 트리 내의 노드를 다양한 순서로 방문하며, 특정 문제나 데이터 구조에 따라 어떤 방법을 선택할지는 상황에 따라 다릅니다. 각 순회 방법은 특정 작업을 수행하는 데 적합한 순서를 제공하므로, 트리 구조를 분석하거나 데이터를 처리하는 데 유용하게 활용됩니다.