DFS, BFS

• bfs.txt

4 5 1   점의 개수, 엣지 개수, 시작 점 번호
1 2
1 3
1 4
2 4
3 4

• linked list 형태로 graph생성

sys.stdin = open('bfs.txt')

N, M, V = list(map(int, input().split()))
graph = {i+1:[] for i in range(N)}

for m in range(M):
    v0, v1 = list(map(int, input().split()))

    graph[v0].append(v1)
    graph[v1].append(v0)

BFS

• queue를 사용해 구현
  - collection deque 사용

import sys
from collections import deque


def bfs(graph, root, visited):
    # root 방문 표시하고 root 를 queue 에 넣음
    visited[root] = True
    que = deque([root])

    while que:
        # queue에서 최상단 노드 방문하기
        # 노드 방문관련 연산을 여기서 처리한다
        v = que.popleft()
        print(v, end=' ')

	# 주변에 방문할 점 있는지 확인하기 (방문 안한점)
        for nextv in graph[v]:
            if visited[nextv]:
                continue
           	
            # 방문 표시 후 queue에 넣기
            visited[nextv] = True
            que.append(nextv)

DFS

• stack 사용해 구현

def dfs(graph, root, visited):
    # root 방문 표시하고 root 를 queue 에 넣음
    stack = [root]
    while stack:
        # queue에서 최상단 노드 방문하기        
        v = stack.pop()
        if not visited[v]:
            # 방문 안했다면 방문 표시하기            
            visited[v] = True
            print(v, end=' ')
            
            # 주변 점 중 방문 안한 점 stack에 넣기
            for nextv in graph[v]:
                if not visited[nextv]:
                    stack.append(nextv)

• 재귀 사용해 구현

def dfs2(graph, root, visited):
    if visited[root]:
        return

    print(root, end=' ')
    visited[root] = True

    for v in graph[root]:
        dfs(graph, v, visited)

    return