- There are two kinds of way to search graph

- DFS and BFS

- DFS

- Depth First Search Algorithm

- Search graph as deeply and many as it can

- It uses Stack

- BFS

- Breadth First Search Algorithm

- Search graph as broadly as it can

- It uses Queue

- When all edges' weight is 1

- it becomes the algorithm for getting shortest distance - Purpose of graph search (DFS, BFS)

- To visit all vertices once - Algorithm of DFS

- by using stack, it goes as much as it can- when there is no way to go, it goes back to a previous vertex

- example)- first, to check if this vertex is already visited
- it's good to make array for remembering the vertex number it visited.

- i ........... 1 2 3 4 5 6- check[i] 1 0 0 0 0 0
- it is a first state. start point is 1 and it is not moving yet
- when all of check array's value have value of 1, this algorithm will be over.

- when graph's state is like this, it can move any direction (2 or 5).

- but in this case, we will make this go to smaller number first.

- so it went to number 2

- when all of check array's value have value of 1, this algorithm will be over.

- it is a first state. start point is 1 and it is not moving yet
- and array will be like

- i ........... 1 2 3 4 5 6

- check[i] 1 1 0 0 0 0

- vertex of this point : 2 - order : 1 2
- stack : 1 2

- vertex of this point : 3

- i ........... 1 2 3 4 5 6

- check[i] 1 1 1 0 0 0 - order : 1 2 3
- stack : 1 2 3

- vertex of this point : 4

- i ........... 1 2 3 4 5 6

- check[i] 1 1 1 1 0 0 - order : 1 2 3 4
- stack : 1 2 3 4

- vertex of this point : 5

- i ........... 1 2 3 4 5 6

- check[i] 1 1 1 1 1 0 - order : 1 2 3 4 5
- stack : 1 2 3 4 5
- in this case, it has to go back to go to vertex 6
- by using stack, it can trace the number of vertices it has stopped by at
- after popping stack it will go to vertex number 4

- vertex of this point : 5

- i ........... 1 2 3 4 5 6

- check[i] 1 1 1 1 1 0

- after popping stack it will go to vertex number 4

- by using stack, it can trace the number of vertices it has stopped by at
- order : 1 2 3 4 5 6
- stack : 1 2 3 4 6

- it's all over now- once it over, people can know it's over but
- stack goes popping one by one
- after stack : 1 2 3 4

- it can know that there is no vertex to go.

- it is judged by checking if array 'check[i]'s value is 1 or 0

- only if the value is 0, we can go to that number of vertex- it should pop the stack out

- after stack : 1 2 3
- after stack : 1 2
- after stack : 1
- after stack : empty

- implement of DFS with Adjecency Matrix

- once it over, people can know it's over but

- check[i] 1 0 0 0 0 0

- it's good to make array for remembering the vertex number it visited.

- first, to check if this vertex is already visited
- time complexity = V * O(V) -> O(V^2)
- implement of DFS with Adjacency List
- time complexity = O(V + E)

- when there is no way to go, it goes back to a previous vertex
- Algorithm of BFS

- by using queue, it puts all the vertices which it can go to into queue- when it puts vertices into queue, it should check that number of vertex is in queue

- vertex of this point : 1

- i ........... 1 2 3 4 5 6

- check[i] 1 0 0 0 0 0

- order : 1

- queue : 1

- vertex of this point : 1

- i ........... 1 2 3 4 5 6

- check[i] 1 1 0 0 1 0

- order : 1 2 5

- queue : 1 2 5

- vertex of this point : 2

- i ........... 1 2 3 4 5 6

- check[i] 1 1 0 0 1 0

- order : 1 2 5

- queue : 2 5

- in this case, it can't go to 5 because 5 has been already checked at this point.

- so it saves only vertex number 3

- vertex of this point : 2

- i ........... 1 2 3 4 5 6

- check[i] 1 1 1 0 1 0

- order : 1 2 5 3

- queue : 2 5 3

- vertex of this point : 5

- i ........... 1 2 3 4 5 6

- check[i] 1 1 1 0 1 0

- order : 1 2 5 3

- queue : 5 3

- vertex of this point : 5

- i ........... 1 2 3 4 5 6

- check[i] 1 1 1 1 1 0

- order : 1 2 5 3 4

- queue : 5 3 4

- vertex of this point : 3

- i ........... 1 2 3 4 5 6

- check[i] 1 1 1 1 1 0

- order : 1 2 5 3 4

- queue : 3 4

- vertex of this point : 4

- i ........... 1 2 3 4 5 6

- check[i] 1 1 1 1 1 0

- order : 1 2 5 3 4

- queue : 4

- vertex of this point : 4

- i ........... 1 2 3 4 5 6

- check[i] 1 1 1 1 1 1

- order : 1 2 5 3 4 6

- queue : 4 6

- vertex of this point : 6

- i ........... 1 2 3 4 5 6

- check[i] 1 1 1 1 1 1

- order : 1 2 5 3 4 6

- queue : 6

- implement of BFS with Adjacency Matrix

- when it puts vertices into queue, it should check that number of vertex is in queue

- boj.kr/1260