BJ 1260 DFSとBFS
15329 ワード
https://www.acmicpc.net/problem/1260
DFS深度優先ナビゲーションとBFS幅優先ナビゲーションが実現できるかどうかの問題.
入力した値を使用して隣接行列を作成します.
BFSをQueue,DFSを再帰関数として実現すればよい.
DFS深度優先ナビゲーションとBFS幅優先ナビゲーションが実現できるかどうかの問題.
入力した値を使用して隣接行列を作成します.
BFSをQueue,DFSを再帰関数として実現すればよい.
package day0221;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
/*7
8 1
0 1
0 2
1 3
1 4
2 4
3 5
4 5
5 6
*/
public class BFSDFS {
static int N;
public static void bfs(int[][] adjMatrix, int start) {
Queue<Integer> queue = new LinkedList<Integer>();
boolean[] visited = new boolean[N];
queue.offer(start);
visited[start] = true;
while(!queue.isEmpty()) {
int current = queue.poll();
System.out.print(current+1 + " ");
// current 정점의 인접정점 처리(단, 방문하지 않은 인접정점만)
for(int j = 0; j < N; j++) {
if(!visited[j] && adjMatrix[current][j] > 0) {
queue.offer(j);
visited[j] = true;
}
}
}
}
public static void dfs(int[][] adjMatrix, boolean[] visited, int current) {
visited[current] = true;
System.out.print(current+1 + " ");
// current 정점의 인접정점 처리(단, 방문하지 않은 인접정점만)
for(int j = 0; j < N; j++) {
if(!visited[j] && adjMatrix[current][j] > 0) {
dfs(adjMatrix, visited, j);
}
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
int C = sc.nextInt();
int V = sc.nextInt();
int[][] adjMatrix = new int[N][N];
for(int i = 0; i < C; i++) {
int from = sc.nextInt() - 1;
int to = sc.nextInt() - 1;
adjMatrix[from][to] = 1;
adjMatrix[to][from] = 1;
}
/* for(int[] is : adjMatrix) {
System.out.println(Arrays.toString(is));
}*/
dfs(adjMatrix, new boolean[N], V - 1);
System.out.println();
bfs(adjMatrix, V - 1);
}
}
Reference
この問題について(BJ 1260 DFSとBFS), 我々は、より多くの情報をここで見つけました https://velog.io/@mraz0210/BJ1260-DFS와-BFSテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol