[Algorithm] Concepts of DFS and BFS and Java implementation

DFS - depth-first search

---

It is literally a search that is carried out by searching up to the lowest node connected to the node and then moving back to the branch point if there is a node that was not reached. DFS is divided into implementations using stack and recursion, and the search order may vary depending on the method.

1. When using a stack

Due to the nature of the stack, input and output occur in one direction. Let’s find out the order and method of output using the example in the picture above.

1. First, start from node A, which is the root.

2. When node A is output, the child nodes B, C, and D are entered.

3. As it is output from above, node D is output and H, the child node, is input.

4. The H node at the top is output, and since there are no child nodes, the C node behind it is output.

5. The G node, which is a child node of the C node, enters.

6. The G node is output, and since there is no child node, the B node below is output.

7. E and F, which are child nodes of node B, enter in that order and are output from the top, so they are output in that order.

As a result, you can see that it is output in the order A - D - H - C - G - B - F - E.

2. When using recursion

When using recursion, the DFS method is executed repeatedly, outputting from the node found first to the node at the lowest depth, and then running to the lowest node of the next child node.

That is, in the tree example above, the output order is A - B - E - F - C - G - D - H.

BFS - Breadth First Search

---

Breadth-first search occurs by checking all child nodes below the root node and then checking the nodes of the next layer. The implementation of BFS uses queues.

I expressed the BFS search order using the same tree structure that described DFS. Due to the nature of the queue structure, input is possible in one direction and output is possible in the other direction. In the image above, it can be seen as input upward and output downward.

1. First, A, the root node, enters.

2. When node A is output, child nodes B, C, and D are entered.

3. When the B node at the bottom is output, B's child nodes E and F are stacked on top in that order.

4. When node C is output, child node G is stacked on top.

5. When the next D node is output, the child node H is piled on top.

6. Child nodes are output in the following order.

As a result, it can be seen that the output is in the order A - B - C - D - E - F - G - H.

Comparison of navigation methods at a glance

---

Below is an image that summarizes the tree search order used in each method above so that you can see at a glance. The order of nodes output when implementing a DFS stack, implementing DFS recursion, and implementing a BFS queue is indicated. The order may change depending on the situation, and it should be noted that the order of DFS stack and BFS queue implementation is not a fast output method in all cases just because the amount is small.

Common sense you need to know before implementing DFS and BFS

---

In Baekjun, you can see that the questions are presented in a way that first informs the node, number of edges, and search start position, and then reads the type of node and edge connected by processing it with BufferedReader using system.in. And programmer's problems are mainly given as arrays in which nodes and edges are connected.

Baekjun	programmers

In other words, for implementation, all we need to know is what nodes there are, the number of edges or how the edges are connected to the nodes, and where to start the search.

Here, there are two methods to obtain data about how nodes and edges are connected: the adjacency matrix method and the adjacency list method. If you know this part first, it will be easier to understand the implementation of each search method, so I summarized it first.

(It was organized in a two-way manner using the tree structure shown in the example above.)

Adjacency matrix method

First, the adjacency matrix method expresses connection by adding the value of 1 to all arrays when connected to each other based on each node. As you can see in the table below, you can see that the values ​​overlap around the diagonal line.

A	B	C	D	E	F	G	H
A	1	1	1
B	1	1	1
C	1	1	1
D	1	1	1
E	1
F	1
G	1
H	1

The above adjacency matrix method can be expressed simply in code as follows. The connection node point is displayed according to the position of each node in the array.

// n은 노드의 수
int[][] arr = new int[n+1][n+1];
arr[0][1] = arr[1][0] = 1

Adjacency list method

The next adjacency list method, unlike the adjacency matrix method above, has the advantage of using less memory space by eliminating unnecessary memory consumption and storing only tightly connected data. However, performance may be lower depending on the situation as it requires checking until the end to check each node connection.

A	B	C	D
B	A	E	F
C	A	D	G
D	A	C	H
E	B
F	B
G	C
H	D

The data structure of the adjacency list method is expressed in code as follows. I think all you need to do is get a feeling that it is contained in this way with briefly written code.

int n = 4;	// 노드의 수
int[][] node = {{1,2},{2,3},{3,4}};
ArrayList> list = new ArrayList<>();
for(int i=0; i());    // 초기화
}
for(int i=0; i

DFS, BFS implemented in Java

---

Now, let’s actually implement the DFS and BFS methods in Java. (백준 1260번 참조)

First, I wrote a method to implement DFS and BFS based on the Baekjun problem. Since each search method is made into a method, commonly used variables were treated as private static variables and processed outside the main function.

Because the value in question must be read in the main function, after processing system.in, it was divided into BufferReader and StringTokenizer to process variables and adjacency matrix. BufferReader is recommended because processing using BufferReader is faster than Scanner.

(In most programmer problems, they are given as separate variables, so there is no need to read them separately.)

Additionally, int[][] arr to process the adjacency matrix and boolean[] visited to display visited nodes are needed.

private static StringBuilder sb = new StringBuilder();
private static boolean[] visited;
private static int[][] arr;
private static int n, m, v;
private static Queue queue = new LinkedList<>();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());    // 노드 수
m = Integer.parseInt(st.nextToken());    // 간선 수
v = Integer.parseInt(st.nextToken());    // 시작 노드
visited = new boolean[n+1];     // 방문여부 체크
arr = new int[n+1][n+1];        // dfs
for(int i=0; i

DFS

This code uses the DFS recursive method. Below the for statement, the DFS method dfs(i); By continuously calling if the conditions are met, it is possible to search from the starting node until there is no lowest node through depth-first search. In the code below, since the adjacency matrix method is used, you can see that search is only possible when the value of arr[][] is 1, that is, when connected by an edge.

public static void dfs(int start) {
visited[start] = true;
sb.append(start+" ");
for(int i=1; i<=n; i++){
if(!visited[start] && arr[start][i]==1){
dfs(i);
}
}
}

BFS

Because a queue is used, you can see that visited nodes are processed by printing until there are no values ​​in the queue. In BFS search, iterative processing is performed using while.

public static void bfs(int start) {
queue.add(start);
visited[start] = true;
while(!queue.isEmpty()) {
start = queue.poll();
sb.append(start + " ");
for(int i = 1 ; i <= node ; i++) {
if(!visited[i] && arr[start][i]==1) {
queue.add(i);
visited[i] = true;
}
}
}
}

---

[개념,그래프] 인접행렬 ,인접리스트 - 그래프를 코드로 ! — Mapin

1분으로 보는 DFS/BFS 구현 방법 - YouTube