너비 우선 탐색
-
BFS(너비 우선 탐색)Computer Science/Algorithm 2021. 9. 25. 11:02
BFS란? ㆍ DFS는 깊이 우선 탐색으로 그래프의 탐색 방법 중 하나이다. ㆍ 갈 수 있는 만큼 최대한 깊이 가고, 더 이상 갈 곳이 없다면 이전 정점으로 돌아가는 방식으로 그래프를 순회하는 방식이다. ㆍ 스택 자료구조를 통해 구현할 수 있다. BFS의 그래프 순회 방식 구현 방법 그래프의 구성 class Graph { class Node { int data; LinkedList adjacentNodes; boolean marked; Node(int data) { this.data = data; adjacentNodes = new LinkedList(); this.marked = false; } } Node[] nodes; Graph(int size) { nodes = new Node[size]; fo..
-
DFS(깊이 우선 탐색)Computer Science/Algorithm 2021. 9. 25. 10:57
DFS란? ㆍ DFS는 깊이 우선 탐색으로 그래프의 탐색 방법 중 하나이다. ㆍ 갈 수 있는 만큼 최대한 깊이 가고, 더 이상 갈 곳이 없다면 이전 정점으로 돌아가는 방식으로 그래프를 순회하는 방식이다. ㆍ 스택 자료구조를 통해 구현할 수 있다. DFS의 그래프 순회 방식 구현 방법 그래프의 구성 class Graph { class Node { int data; LinkedList adjacentNodes; boolean marked; Node(int data) { this.data = data; adjacentNodes = new LinkedList(); this.marked = false; } } Node[] nodes; Graph(int size) { nodes = new Node[size]; fo..