BFS(너비 우선 탐색)

BFS(너비 우선 탐색)

☁️ BFS란?

DFS는 깊이 우선 탐색으로 그래프의 탐색 방법 중 하나이다.

갈 수 있는 만큼 최대한 깊이 가고, 더 이상 갈 곳이 없다면 이전 정점으로 돌아가는 방식으로 그래프를 순회하는 방식이다.

스택 자료구조를 통해 구현할 수 있다.

☁️ BFS의 그래프 순회 방식

☁️ 구현 방법

1️⃣ 그래프의 구성

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]; for (int i = 0; i < size; i++) nodes[i] = new Node(i); } }

ㆍ 그래프가 가지고 있는 노드의 정보를 클래스로써 정의하였다.

ㆍ 각각의 노드는 데이터(data), 인접한 노드들(adjacentNodes), 방문 여부 획인 변수(marked)를 가지고 있다.

2️⃣ 엣지를 구성해주는 메서드

void addEdge(int index01, int index02) { if (!nodes[index01].adjacentNodes.contains(nodes[index02])) nodes[index01].adjacentNodes.add(nodes[index02]); if (!nodes[index02].adjacentNodes.contains(nodes[index01])) nodes[index02].adjacentNodes.add(nodes[index01]); }

ㆍ 엣지를 구성할 두 개의 노드를 매개변수로 입력받아 adjacentNodes에 각각의 노드들을 추가해준다.

3️⃣ 큐 자료구조를 이용한 BFS 알고리즘

void bfs(int startIndex) { Node root = nodes[startIndex]; Queue queue = new LinkedList(); queue.add(root); root.marked = true; while (!queue.isEmpty()) { Node returnNode = queue.poll(); Collections.sort(returnNode.adjacentNodes, new Comparator() { @Override public int compare(Node o1, Node o2) { if (o1.data > o2.data) return 1; else return -1; } }); for (Node node : returnNode.adjacentNodes) { if (node.marked == false) { node.marked = true; queue.add(node); } } System.out.print(returnNode.data + " "); } }

ㆍ 우선, 탐색을 시작할 노드를 큐 자료구조에 삽입한다.

ㆍ 큐에서 노드를 꺼내고 꺼낸 노드의 아직 방문하지 않은 인접한 노드들을 큐에 삽입한다.

ㆍ 인접한 노드들이 여러 개일 경우 노드의 데이터가 작은 순서대로 삽입한다.

ㆍ 삽입 과정이 마무리되면 꺼낸 노드에 대한 정보를 출력한다.

ㆍ 위 과정을 큐에 데이터가 없을 때까지 반복한다.

from http://qlsdud0604.tistory.com/25 by ccl(A) rewrite - 2021-09-25 11:26:55