[規格]1260号:DFSとBFS(Python)

質問する

私の答え

from collections import deque
import sys
input = sys.stdin.readline

n,m,v=map(int,input().split())#정점,간선,시작노드
g = [[0] * (n + 1) for i in range(n + 1)] #n+1개의 노드를 가진, 0으로 초기화 된 그래프 생성

for i in range(m):
    x,y=map(int,input().split())
    g[x][y],g[y][x]=1,1

arr_dfs=[0]*(n+1)
arr_bfs=[0]*(n+1)

def dfs(dv):#스택 or 재귀
    arr_dfs[dv]=1
    print(dv,end=' ')

    for i in range(n+1):
        if arr_dfs[i]==0 and g[i][dv]:#해당 노드에 접근한적 있는지, 간선이 있는지
            dfs(i)
            
def bfs(bv):#큐, 큐가 빌 때까지 반복
    arr_bfs[bv]=1
    dq=deque()
    dq.append(bv)

    while dq:
        node=dq.popleft()
        print(node,end=' ')
        for i in range(n+1):
            if arr_bfs[i]==0 and g[i][node]:#해당 노드에 접근한적 있는지, 간선이 있는지
                dq.append(i)#노드 삽입
                arr_bfs[i]=1#방문했다고 표시

dfs(v)
print()
bfs(v)

これはDFSとBFSの基本的な実装を尋ねる問題である.
DFSは、深度優先ナビゲーションによってすべてのノードにアクセスし、スタックまたは再帰関数で実現される.
BFSは2つのノード間の最短経路に幅優先ナビゲーション方式でアクセスし,キュー方式で実現する.