[그래프 개념] 그래프, DFS, BFS 정리

https://www.youtube.com/watch?v=gl5RhtU2mF8&list=PLDV-cCQnUlIZH0wklfVG1IN9ks4g92oN7&index=3 

 

코드없는 프로그래밍님의 그래프 강의를 공부하며 작성했습니다.

 

 

Graph

---

vertices와 edges로 이루어짐

edge들의 방향성이 있다면 -> directed graph

 

edge들의 방향성이 없다면 -> undirected graph

 

vertices 사이에 value가 있다면 weighted graph

 

 

그래프에 싸이클이 있으면 cyclic graph --> 그림에서 (A,B,E/E,B,C)

그래프에 싸이클이 없다면 Acyclic Graph  --> 그림에서 (E,C,D)

 

DAG(Directed Acyclic Graph) : 사이클은 없지만 방향이 있는 그래프 

 

 

  

Grap Traversals(DFS/BFS)

---

1) DFS

=Depth First Search 

 

--> recursion (call stack 이용)

--> iteration (stack이용)

 

스택공간과 중복처리를 위해 저장했던 해쉬set인 sean이 필요 

 

 

우선 A부터 시작을 한다. 

그러면 스택에 A를 쌓고, Seen에도 A를 넣어준다.

A와 연결된 vertices들은 D,C,B를 쌓는 대신 A를 pop해준다. 그리고 Seen에 B,C,D를 넣어준다.

 

가장 위에 있는 B를 pop해주기 위해 B와 연결된 vertices 들을 쌓아야한다. B와 연결된 애는 A와 E인데 이미 Seen에 A가 있으므로, E만 stack에 쌓고 Seen에 넣어준다.

 

다시 E를 pop하기 위해 연결된 B,C,G를 쌓아주려 하지만 이미 Seen에 B,C가 있으므로 G만 추가해준다.

 

G를 pop하기 위해 연결된 E는 이미 Seen에 있기에 G는 stack에 쌓지 않고 G만 pop해준다.

 

그러면 stack의 가장 위에 있는 C를  pop하기 위해 C와 연결된 A,D,F,E가 있는데 여기서 Seen에 없는건 F이므로 F만 stack에 쌓고, Seen에 넣어준다.

 

F를 pop하기 위해 f와 연결된 C,D는 이미 Seen에 있기에 바로 F를 pop해준다.

 

마지막으로 D를 pop하기 위해 연결된 A,C,F는 이미 Seen에 있으므로 D만 pop해준다. 

 

즉, A B E G C F D 순으로 pop된다. 

 

2) BFS

 

= Breadth First Search

 

- 첫번째 vertice부터 멀어지는 구조로 이루어짐

 

- Queue를 사용해서 푼다.

 

큐와 Sean에 A를 넣는다.

 

A를  pop해주며 연결된 B,C,D를 enque해준다.

 

B를 pop해주며 연결된 E,A를 enque해주는데 A는 Sean에 이미 있으므로 E만 넣어준다.

 

C를 pop해주기 위해 연결된 A,D,F,E 중 Sean에 없는 F만 추가해준다.

 

이런 식으로 반복시켜주다보면

 

A B C D E F G 순서로 deque가 된다. 

 

DFS와 BFS의 차이점

---

 

https://yunyoung1819.tistory.com/86

[알고리즘] 깊이 우선 탐색(DFS) 과 너비 우선 탐색(BFS)