너비 우선 탐색 (BFS; Breadth First Search)정의가까운 노드부터 탐색 즉, 시작한 노드와 연결된 인접 노드들을 모드 방문한 후, 방문한 노드들의 인접노드를 차례로 방문특징레벨 단위 탐색 : 루트 노드로부터 거리에 따라 레벨을 구분최단 경로 탐색 : 가중치가 동일한 경우 시작 노드로부터 각 노드까지 최단경로 구할 때 유용다음 방문할 노드를 저장하기 위해 큐 자료구조를 사용활용최단 경로 탐색시작점 ~ 모든 노드까지 최단경로(간선 수)를 탐색ex) 미로찾기, 네트워크 최단경로레벨 순서 탐색트리의 각 레벨별 노드를 순서대로 방문하여, 레벨 별 데이터를 처리하거나 출력ex) 조직도연결 요소 탐색연결된 노드들의 집합(연결요소)를 식별할 때 사용ex) SNS 친구 그룹 찾기흐름 및 구현 예제시작 ..

정의위상정렬은 무순환 방향 그래프 DAG(Directed Acyclie Graph)에서 정돈되지 않은 그래프를, 각 노드의 선후관계를 정립해 일관된 방향으로 향하도록 정렬하는 방식이다. (작업의 우선순위, 부품의 조립 순서)Kahn 알고리즘(BFS 기반)각 노드의 진입차수(indegree) 계산 후, 진입 차수가 0인 노드를 큐에 넣고, 연결된 노드의 진입 차수를 감소최종적으로 현재 진입 차수가 0인 노드를 선택from collections import dequedef topological_sort_kahn(graph, indegree): result = [] # 위상 정렬 결과 저장 queue = deque([i for i in range(1, len(indegree)..