dfs6 Tree, BFS 1. 트리 1) 트리의 개념 - 비선형 구조 - 원소들 간에 1:N 관계를 가지는 자료구조 - 원소들 간에 계층관계를 가지는 계층형 자료구조 - 상위 원소에서 하위 원소로 내려가면서 확장되는 트리모양의 구조 2) 트리의 용어 - 노드 : 트리의 원소 - 루트 : 최상위 노드 - 형제 노드 : 같은 부모 노드의 자식 노드들 - 조상 노드 : 산선을 따라 루트 노드까지 이르는 경로에 있는 모든 노드들 - 서브 트리 : 부모 노드와 연결된 간선을 끊었을 때 생성되는 트리 - 자손 노드 : 서브 트리에 있는 하위 레벨의 노드들 - 노드의 차수 : 노드에 연결된 자식 노드의 수 - 트리의 차수 : 트리에 있는 노드의 차수 중에서 가장 큰 값 - 단말 노드 : 차수가 0인 노드 - 노드의 높이 : 루트에서 노드에 .. 2024. 2. 6. DFS / BFS 1. DFS - 깊이 우선 탐색은 그래프의 시작 노드에서 출발하여 탐색할 한 쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘입니다. - 재귀 함수를 이용하므로 스택 오버플로에 유의 - ex. 단절점 찾기, 단절선 찾기, 사이클 찾기, 위상 정렬 - 작동 원리 - 예제 코드 public class BJ_11724 { static ArrayList[] A; static boolean visited[]; static void DFS(int v) { if (visited[v]) { return; } visited[v] = true; for (int i : A[v]) { if (!visited[i]) { DFS(i); } } } public static vo.. 2024. 1. 22. 이전 1 2 다음
