import java.io.*;
import java.util.*;
public class DFSBFS_1260 {
private static ArrayList<ArrayList<Integer>> graph;
private static boolean[] visited;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
// n: 정점 갯수, m: 간선 갯수, v: 시작 정점
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
int v = Integer.parseInt(st.nextToken());
graph = new ArrayList<>();
for (int i = 0; i <= n; i++) {
graph.add(new ArrayList<>());
}
for (int i = 0; i < m; i++) {
st = new StringTokenizer(br.readLine());
int start = Integer.parseInt(st.nextToken());
int end = Integer.parseInt(st.nextToken());
graph.get(start).add(end);
graph.get(end).add(start);
}
for(int i = 1; i <= n; i++){
Collections.sort(graph.get(i));
}
visited = new boolean[n + 1];
dfs(v);
System.out.println();
visited = new boolean[n + 1];
bfs(v);
System.out.println();
}
public static void dfs(int v) {
visited[v] = true;
System.out.print(v + " ");
for (int next : graph.get(v)) {
if (!visited[next]) {
visited[next] = true;
dfs(next);
}
}
}
public static void bfs(int v) {
Queue<Integer> queue = new LinkedList<>();
queue.offer(v);
visited[v] = true;
while (!queue.isEmpty()) {
int current = queue.poll();
System.out.print(current + " ");
for (int next : graph.get(current)) {
if (!visited[next]) {
queue.offer(next);
visited[next] = true;
}
}
}
}
}
이 코드는 DFS (깊이 우선 탐색)과 BFS (너비 우선 탐색) 알고리즘을 사용하여 그래프를 탐색하는 프로그램입니다.
입력 받기
n
, 간선의 개수 m
, 시작 정점 v
를 입력 받습니다.BufferedReader
를 사용하여 받습니다.그래프 구성하기
graph
라는 2차원 ArrayList를 생성합니다. 이는 각 정점마다 연결된 정점들의 리스트를 저장하기 위한 용도입니다.n
개의 정점에 대해 빈 리스트를 생성하여 graph
에 추가합니다.m
개의 줄에서 간선 정보를 입력 받고, 해당 간선의 시작 정점과 끝 정점을 graph
에 추가합니다. 이때 양방향 간선이므로 양쪽 정점에 모두 추가합니다.그래프 정렬하기
visited
라는 boolean 배열을 생성하여 방문한 정점을 표시합니다.dfs
함수를 호출하여 시작 정점 v
부터 DFS 탐색을 시작합니다.v
를 방문했음을 표시하고, 정점 번호를 출력합니다.dfs
함수를 재귀적으로 호출합니다.Queue
인터페이스를 구현한 LinkedList
를 사용하여 BFS 탐색을 위한 큐를 생성합니다.v
를 큐에 추가하고 방문했음을 표시합니다.const readline = require('readline');
function dfs(v, visited, graph) {
visited[v] = true;
process.stdout.write(v + ' ');
for (const next of graph[v]) {
if (!visited[next]) {
dfs(next, visited, graph);
}
}
}
function bfs(v, visited, graph) {
const queue = [];
queue.push(v);
visited[v] = true;
while (queue.length > 0) {
const current = queue.shift();
process.stdout.write(current + ' ');
for (const next of graph[current]) {
if (!visited[next]) {
queue.push(next);
visited[next] = true;
}
}
}
}
function main() {
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout,
});
let n, m, v;
let graph = [];
rl.on('line', (line) => {
const tokens = line.trim().split(' ');
if (n === undefined) {
n = parseInt(tokens[0]);
m = parseInt(tokens[1]);
v = parseInt(tokens[2]);
for (let i = 0; i <= n; i++) {
graph.push([]);
}
} else {
const start = parseInt(tokens[0]);
const end = parseInt(tokens[1]);
graph[start].push(end);
graph[end].push(start);
}
}).on('close', () => {
for (let i = 1; i <= n; i++) {
graph[i].sort((a, b) => a - b);
}
const visited = new Array(n + 1).fill(false);
dfs(v, visited, graph);
process.stdout.write('\n');
visited.fill(false);
bfs(v, visited, graph);
process.stdout.write('\n');
});
}
main();
from collections import deque
def dfs(v, visited, graph):
visited[v] = True
print(v, end=' ')
for next in graph[v]:
if not visited[next]:
dfs(next, visited, graph)
def bfs(v, visited, graph):
queue = deque()
queue.append(v)
visited[v] = True
while queue:
current = queue.popleft()
print(current, end=' ')
for next in graph[current]:
if not visited[next]:
queue.append(next)
visited[next] = True
def main():
n, m, v = map(int, input().split())
graph = [[] for _ in range(n + 1)]
for _ in range(m):
start, end = map(int, input().split())
graph[start].append(end)
graph[end].append(start)
for i in range(1, n + 1):
graph[i].sort()
visited = [False] * (n + 1)
dfs(v, visited, graph)
print()
visited = [False] * (n + 1)
bfs(v, visited, graph)
print()
if __name__ == '__main__':
main()