출처
해당 게시글은 [Java] 어서와! 자료구조 알고리즘은 처음이지?https://programmers.co.kr/learn/courses/13577를 간략히 요약한 게시글이며 모든 출처는 해당강의에 있습니다
이론
Graph
Node: 하나의 종착점Edge: Node간 연결
필수적인 요소로는 Node와 Edge가 존재합니다.
weight: 가중치direction: 방향
Weight와 direction은 필수는 아니지만, 필요에 따라 그래프를 더욱 풍부하게 표현할 수 있도록 합니다.
DFS, BFS
BFS: 너비 우선 탐색, 가장 가까운 노드부터 차례로 탐색합니다. 최단 거리를 구할 때 사용 하며 중간 저장체로Queue사용DFS: 깊이 우선 탐색, 하나의 깊이 부터 끝단을 변경해 가며 탐색합니다. 여러 조합할 때 사용하며 중간 저장체로Stack사용
BFS와DFS는 중간 저장체로 큐를 사용하냐 스택을 사용하냐에 따라 달라집니다.
실습
그래프
class Node{
String name;
List<Node> links;
boolean visited;
public Node(String name) {
this.name = name;
this.links = new LinkedList<>();
}
@Override
public String toString() {
return name;
}
void link(Node node){
links.add(node);
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Node node = (Node) o;
return name.equals(node.name);
}
@Override
public int hashCode() {
return Objects.hash(name);
}
void visit(){
this.visited = true;
}
boolean isVisited(){
return this.visited;
}
}
public class Main {
public static void main(String[] args) {
Node a = new Node("A");
Node b = new Node("B");
Node c = new Node("C");
Node d = new Node("D");
Node e = new Node("E");
a.link(b);
a.link(d);
b.link(a);
b.link(c);
b.link(e);
c.link(b);
c.link(d);
d.link(a);
d.link(c);
d.link(e);
e.link(b);
e.link(d);
}
}자바에서 그래프만을 위한 라이브러리는 기본적으로 제공하지 않지만 노드를 인스턴스를 만들어 관리함으로써 자바를 통해 편리하게 그래프를 구현할 수 있습니다.
하나의 노드는 하나의 데이터와 방문여부, 여러개의 링크를 가질 수 있습니다.
노드는 데이터, 인접 노드 링크, 방문 여부를 가지므로 탐색 시 여러 노드를 참고할지 안할지 선택할 수 있습니다.
BFS
// BFS
Queue<Node> queue = new LinkedList<>();
queue.offer(a);
while(!queue.isEmpty()){
Node n = queue.poll();
n.visit();
System.out.println(n);
if(n.equals(target)){
//find!!
System.out.println("Found!! " + n);
break;
}
for(Node l : n.links){
if(l.isVisited()) continue;
if(queue.contains(l)) continue;
queue.offer(l);
}
}BFS는 큐를 이용하여 탐색을 시도합니다.
- 시작 위치의 노드를 넣고
- 노드를 하나씩 빼가면서
- 찾는 노드인지 확인하고
- 찾는 노드가 아니라면 방문한적 없고 큐에 없으면 큐에 추가합니다.
DFS
// DFS
Stack<Node> queue = new Stack<>();
queue.push(a);
while(!queue.isEmpty()){
Node n = queue.pop();
n.visit();
System.out.println(n);
if(n.equals(target)){
//find!!
System.out.println("Found!! " + n);
break;
}
for(Node l : n.links){
if(l.isVisited()) continue;
if(queue.contains(l)) continue;
queue.push(l);
}
}DFS는 BFS와 다르게 큐가아닌 스택을 이용합니다.
- 시작 위치의 노드를 넣고
- 노드를 하나씩 빼가면서
- 찾는 노드인지 확인하고
- 찾는 노드가 아니라면 방문한적 없고 큐에 없으면 큐에 추가합니다.
작동 로직은 BFS와 DFS가 완전히 동일합니다. (자료구조만 바꾸면 바뀜)
Github
오늘도 내일도 화이팅!