[規格]1260番DFSとBFS
問題I/O
質問へのアクセス
ツリー構造をarraylistとして保存し、dfs、bfsを可能にします.
bfsは,キュー内のすべての隣接ノードをキューに入れ,1つずつ検索することを実現した.
dfsは、隣接ノードから隣接ノードへのナビゲートを継続する方法によって実現される.
インプリメンテーションコード
import java.io.*;
import java.util.*;
public class Main {
static ArrayList<Integer>[] al;
static boolean check[];
static void bfs(int a) {
Queue<Integer> queue = new LinkedList<Integer>();
queue.add(a);
check[a] = true;
while(!queue.isEmpty()) {
int x = queue.poll();
System.out.print(x + " ");
for(int y : al[x]) {
if(!check[y]) {
check[y] = true;
queue.add(y);
}
}
}
}
static void dfs(int a) {
if(check[a]) return;
check[a] = true;
System.out.print(a + " ");
for(int y : al[a])
if(!check[y])
dfs(y);
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
int V = Integer.parseInt(st.nextToken());
al = new ArrayList[N+1];
for(int i = 0; i < N + 1; i++) al[i] = new ArrayList<Integer>();
for(int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
al[a].add(b);
al[b].add(a);
}
for (int i = 1; i < N + 1; i++) {
Collections.sort(al[i]);
}
check = new boolean[N + 1];
dfs(V);
System.out.println();
check = new boolean[N + 1];
bfs(V);
}
}
Reference
この問題について([規格]1260番DFSとBFS), 我々は、より多くの情報をここで見つけました https://velog.io/@choiish98/백준-1260번-DFS와-BFSテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol