BFS VS DFS

0. 그래프

• 정점과 간선들의 유한집합 G=(V,E)
• 정점(vertex): 여러 특성을 가지는 객체, 노드
• 간선: 이 객체들의 연결 관계를 나타냄. 링크
• 간선은 방향성이 있는 경우와 없는 경우가 있음.
• 그래프를 구현하는 방법: 인접 행렬, 인접 리스

1. BFS와 DFS란?

• 대표적인 그래프 탐색 알고리즘
  • 너비 우선 탐색(Breadth First Searh) : 정점들과 같은 레벨에 있는 노드들(형제 노드들)을 먼저 탐색하는 방식
  • 깊이 우선 탐색(Depth First Search) : 정점의 자식들을 먼저 탐색하는 방식

 

• BFS
  • 한 단계씩내려가면서 해당 노드와 같은 레벨에 있는 노드들(형제 노드들)을 먼저 순회함.
  • 동일한 노드를 먼저 탐색
• DFS
  • 한 노드의 자식을 타고 끝까지 순회한 후, 다시 돌아와서 다른 형제들의 자식을 타고 내려가며 순회.
  • 하나의 노드의 최 하단부 노드까지 탐색한 후에 다른 노드를 탐색.

DFS 알고리즘 구현

• 자료구조 스택을 이용. 
  • needVisit 스택

import java.util.ArrayList;

ArrayList<String> aList = new ArrayLit<String>);
aList.add("A");
aList.add("B"); // 스택이니까 B가 먼저 나감
Stirng node = aList.remove(aList.size()-1);  // pop
System.out.println(aList);  // [A]
System.out.println(node); // B


public calss DFSSearch
	public ArrayList<Stirng> dfsFunc(HashMap<Stirng, ArrayList<String>> graph, String startNode) { // 키와 키에 대응하는 값을 받고, 최초 노드는 설정해주기
    	ArrayList<Stirng> visited = new ArrayList<String>();
        ArrayList<Stirng> needVist = new ArrayList<String>();
        
        needVisit.add(startNode);
        
        while(needVisit.size()>0) {
        String node = needVisit.remove(needVisit.size()-1);  // 스택에서 맨 끝에서 데이터 POP
        if(!visited.contains(node)) {  // 방문한 적이 없다면
        visited.add(node);  // 해당 노드를 방문한 것으로 처리
        needVisit.addAll(graph.get(node));  // 해당 노드와 연결되어 있는 노드들을 needVisit으로 
        }
        }
        return visited;
        }
        }

DFSSearch dObject = new DFSSearch();
dObject.dfsFunc(graph, "A");  // 최초 노드 넣기

[A,C,I,JH,G,B,D,F,E]

 

https://daily-life-of-bsh.tistory.com/35

깊이우선탐색 (Depth First Search)