dfs2 그래프 이론 & 인접행렬 & 인접리스트 BFS가 궁금하면 아래 글을 참조BFS (Breadth-First Search)DFS가 궁금하면 아래 글을 참조DFS (Depth-First Search)✔ 그래프 이론 그래프는 수학에서 객체 간에 짝을 이루는 관계를 모델링하기 위해 사용되는 수학 구조이다.그래프(graph)는 아래의 순서쌍으로 볼 수 있다.$$ G = (V, E) $$여기서 V는 정점(vertex) 혹은 노드(node)를 의미하고, E는 간선(edge) 혹은 변을 의미한다. 즉, 그래프는 정점 집합과 간선 집합으로 선으로 연결된 구조이다.✔ 그래프 종류 위 그림은 6개의 노드 7개의 간선을 가지는 그래프이고, 6번 노드의 차수는 1이고, 5번 노드의 차수는 3이다.이와 같은 그래프를 무향 그래프(무방향 그래프, undirected gr.. 2025. 4. 17. DFS (Depth-First Search) BFS가 궁금하면 아래 글을 참조 BFS (Breadth-First Search) ✔ DFS(Depth-First Search) DFS는 깊이 우선 탐색이라고도 부르며, 그래프를 탐색하는 방법 중 하나이다. 하나의 정점으로부터 시작해 차례대로 모든 정점들을 한 번씩 방문하는 것으로 즉, 시작 노드에서 출발해 인접한 노드(가까운 노드)를 먼저 탐색하고 그 정점의 최대 깊이까지 탐색을 마친 후 돌아와 다른 분기로 다시 탐색하는 알고리즘이다. 넓게 탐색하기 전에 깊게 탐색 스택 or 재귀를 사용하여 구현 모든 노드를 방문할 때 사용 ※ 중요한 점은 방문한 정점은 다시 방문하지 않아야 한다. DFS는 스택으로도 구현할 수 있지만 재귀로 구현하는 편이 더 깔끔해서 재귀로 더 많이 구현하는 것 같다. DFS와 BF.. 2023. 6. 25. 이전 1 다음
