Search of Graph
- 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)
void dfs(int x) { // implemented recursively check[x] = true; printf("%d ", x); for (int i=1; i<=n; i++) { if (a[x][i] == 1 && check[i] == false) { dfs(i); } } } - implement of DFS with Adjacency List
- time complexity = O(V + E)
void dfs(int x) { check[x] = true; printf("%d ", x); for (int i=0; i<a[x].size(); i++) { int y = a[x][i]; if (check[y] == false) { dfs(y); } } } ```
- 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 Matrixqueue<int> q; check[1] = true; q.push(1); while(!q.empty()) { int x = q.front(); q.pop(); printf("%d ", x); for (int i=1; i<=n; i++) { // it's really similar to DFS, but DFS is implemented by recursive function if (a[x][i] == 1 && check[i] == false) { check[i] = true; q.push(i); } } }- implemented of BFS with Adjacency Listqueue<int> q; check[1] = true; q.push(1); while (!q.empty()) { int x = q.front(); q.pop(); printf("%d ", x); for (int i=0; i<a[x].size(); i++) { int y = a[x][i]; if (check[y] == false) { check[y] = true; q.push(y); } } } ```
- when it puts vertices into queue, it should check that number of vertex is in queue
Problem implementing DFS and BFS
- boj.kr/1260
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.StringTokenizer;
public class Main {
static boolean[] checkList;
static int numOfVisitedVertices;
static StringBuffer sb = new StringBuffer();
public static void dfs(ArrayList<Integer>[] adjacentList, int startVertexNum, int numOfVertices){
int currentVertexNum;
for(int i=0; i<adjacentList[startVertexNum].size(); i++) {
if(!checkList[adjacentList[startVertexNum].get(i)]) {
currentVertexNum = adjacentList[startVertexNum].get(i);
sb.append(currentVertexNum + " ");
checkList[currentVertexNum] = true;
numOfVisitedVertices++;
dfs(adjacentList, currentVertexNum, numOfVertices);
}
}
}
public static void bfs(ArrayList<Integer>[] adjacentList, int startVertexNum, int numOfVertices){
LinkedList<Integer> queue = new LinkedList();
queue.push(startVertexNum);
while(!queue.isEmpty()){
int currentVertexNum = queue.peekFirst();
for(int i=0; i<adjacentList[currentVertexNum].size(); i++) {
int currentEdgeNum = adjacentList[currentVertexNum].get(i);
if(!checkList[currentEdgeNum]) {
queue.add(currentEdgeNum);
checkList[currentEdgeNum] = true;
}
}
sb.append(queue.poll() + " ");
}
}
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int numOfVertices = Integer.parseInt(st.nextToken());
int numOfEdges = Integer.parseInt(st.nextToken());
int startVertex = Integer.parseInt(st.nextToken());
ArrayList<Integer>[] adjacentList = new ArrayList[numOfVertices + 1];
for(int i=0; i<numOfEdges; i++){
st = new StringTokenizer(br.readLine());
int vNum = Integer.parseInt(st.nextToken());
int eNum = Integer.parseInt(st.nextToken());
if(adjacentList[vNum] == null) adjacentList[vNum] = new ArrayList();
if(adjacentList[eNum] == null) adjacentList[eNum] = new ArrayList();
adjacentList[vNum].add(eNum);
adjacentList[eNum].add(vNum);
}
for(int i=1; i<=numOfVertices; i++)
if(adjacentList[i] != null)
Collections.sort(adjacentList[i]);
checkList = new boolean[numOfVertices + 1];
checkList[startVertex] = true;
numOfVisitedVertices = 1;
sb.append(startVertex + " ");
dfs(adjacentList, startVertex, numOfVertices);
sb.append("\n");
checkList = new boolean[numOfVertices + 1];
checkList[startVertex] = true;
bfs(adjacentList, startVertex, numOfVertices);
System.out.print(sb);
}
}
풀스택 웹개발자로 일하고 있는 Jake Seo입니다. 주로 Jake Seo라는 닉네임을 많이 씁니다. 프론트엔드: Javascript, React 백엔드: Spring Framework에 관심이 있습니다.