Module: 심층적으로 검색하십시오. DFS

Problem

2/12

깊이 우선 검색(DFS)은 그래프의 주요 알고리즘 중 하나입니다. 알고리즘은 O(N + M)에서 실행됩니다.

우선 맨 위부터 시작하여 이 맨 위의 하위 항목을 고려하고 입력한 적이 없는 경우 해당 항목에서 DFS를 시작합니다.

시작 정점 S에서 무방향 그래프의 깊이를 순회하고 정점 <에서 시작하여 순회 순서로 모든 정점을 출력하는 프로시저 def dfs(v)를 작성하세요. code>S 한 줄에 공백으로 구분됩니다.

<사업부>
첫 번째 줄에는 세 개의 숫자 N - 그래프의 정점 수, M - 가장자리 수, S - 시작 꼭지점. 다음 M 줄에서 2개의 변수 U_i 및 V_i 제공되는 , 그래프 에지 설명. 입력의 모든 숫자는 1000을 초과하지 않습니다.

<사업부>
DFS 순회 순서대로 모든 정점을 출력합니다.

위의 프로그램에서 V[i][j]는 정점 i와 j 사이에 가장자리가 있음을 의미하며, 배열 Visited 이 피크를 방문했는지 여부를 표시합니다.

들여쓰기를 나타내기 위해 공백 4개를 사용합니다.

Python

Write the program below
def dfs(start):

n, m, s = map(int, input().split()) Visited = [False]*(n+1) V = [set() for i in range(n+1)] for i in range(m): u, v = map(int, input().split()) V[u].add(v) V[v].add(u) dfs(s)