HSM 개발공부

개요 대표적인 그래프 탐색 알고리즘 너비 우선 탐색 (BFS, Breadth-First Search): 노드들과 같은 레벨에 있는 노드를 먼저 탐색하는 방식. 한 단계씩 내려가면서 같은 단계에 존재하는 노드들을 먼저 순회함. 깊이 우선 탐색 (DFS, Depth-First Search): 노드의 자식들을 먼저 탐색하는 방식. 한 노드 의 자식을 타고 끝까지 순회한 후, 다시 돌아와 다른 노드들의 자식을 타고 내려가며 순회함. 파이썬의 딕셔너리와 리스트 자료구조를 활용해 그래프를 표현 가능함 BFS (너비우선탐색, Breadth-First Search) 구현 방문할 노드(need_visti_queue)들과 방문한 노드(visited_queue)들을 append하는 두 개의 큐를 활용함 graph = dic..

그래프 실제 세계의 현상이나 사물을 정점(vertex) 또는 노드(node)와 간선(edge)으로 표현하기 위해 사용함 용어 무방향 그래프 정점의 차수: 하나의 노드에 인접한 노드 수 방향 그래프 진입 차수: 외부에서 들어오는 간선 수 진출 차수: 외부로 나가는 간선 수 경로 길이: 경로를 구성하기 위해 사용된 간선 수 단순 경로: 처음 노드와 끝 노드를 제외하고 종복된 노드가 없는 경로 A → B → D (O) A → C → D (O) A → B → A → C → D (X) A → B → D → C → A (O) 사이클: 단순 경로 중에서 시작 노드와 끝 노드가 동일한 경우 A → B → C → A 그래프 종류 무방향 그래프 방향이 없는 그래프 간선을 통해 노드는 양방향으로 갈 수 있다 방향 그래프 간..