자바 알고리즘 정복 4 - DFS, BFS

자바 알고리즘 정복 4 - DFS, BFS

1. 그래프 + 스택을 이용한 DFS & BFS

package StudyJava.DFSBFS; import java.util.LinkedList; import java.util.NoSuchElementException; import java.util.Stack; class Queue { ... } // 생략 class Graph { class Node { // 그래프 노드 :D int data; LinkedList adjacent; boolean marked; Node (int data) { // 생성자 this.data = data; this.marked = false; adjacent = new LinkedList(); } } Node[] nodes; Graph(int size) { // 생성자 nodes = new Node[size]; for(int i = 0; i < size; i++) { nodes[i] = new Node(i); } } void addEdge(int i1, int i2) { // 노드 연결 Node n1 = nodes[i1]; Node n2 = nodes[i2]; if(!n1.adjacent.contains(n2)) { // n1노드와 n2노드가 연결되어 있지 않다면 n1.adjacent.add(n2); // 연결 추가 } if(!n2.adjacent.contains(n1)) { n2.adjacent.addFirst(n1); } } void dfs() { dfs(0); } void dfs(int index) { Node root = nodes[index]; Stack stack = new Stack<>(); stack.push(root); root.marked = true; while(!stack.isEmpty()) { Node r = stack.pop(); for(Node n : r.adjacent) { if(n.marked == false) { n.marked = true; stack.push(n); } } visit(r); } } void bfs() { bfs(0); } void bfs(int index) { Node root = nodes[index]; Queue queue = new Queue<>(); queue.add(root); root.marked = true; while(!queue.isEmpty()) { Node r = queue.remove(); for(Node n : r.adjacent) { if(n.marked == false) { n.marked = true; queue.add(n); } } visit(r); } } void visit(Node r) { System.out.print(r.data + " "); } void dfsR(Node r) { // 재귀함수를 이용한 dfs (=스택) if(r == null) return; r.marked = true; visit(r); for(Node n : r.adjacent) { if(n.marked == false) { dfsR(n); } } } void dfsR(int index) { Node r = nodes[index]; dfsR(r); } void dfsR() { dfsR(0); } } public class MainClass { public static void main(String[] args) { Graph g = new Graph(9); g.addEdge(0, 1); g.addEdge(1, 2); g.addEdge(1, 3); g.addEdge(2, 3); g.addEdge(2, 4); g.addEdge(3, 4); g.addEdge(3, 5); g.addEdge(5, 6); g.addEdge(5, 7); g.addEdge(6, 8); g.dfsR(); } }

from http://sedangdang.tistory.com/83 by ccl(A) rewrite - 2021-08-08 15:00:15