バックアップ-グラフ(#1260)

https://www.acmicpc.net/problem/1260

Code 1

import sys

def dfs(v):
    print(v, end=' ')
    already_visited[v] = 1
    for i in range(1,n+1):
        if adj_matrix[v][i] == 1 and already_visited[i] == 0:
            dfs(i)

def bfs(v):
    already_visited = [0]*(n+1)

    queue = [v]
    already_visited[v] = 1

    while queue:
        v = queue[0]
        del queue[0]
        print(v, end=' ')
        for i in range(1, n+1):
            if adj_matrix[v][i] == 1 and already_visited[i] == 0:
                queue.append(i)
                already_visited[i] = 1

n, m, v = map(int, input().split())
adj_matrix = [[0]*(n+1) for _ in range(n+1)]

for _ in range(m):
    a, b = map(int, sys.stdin.readline().split())
    adj_matrix[a][b] = 1
    adj_matrix[b][a] = 1

already_visited = [0]*(n+1)
dfs(v)
print()

bfs(v)

Code 2

import sys

def dfs(v):
    visited = {}
    stack = [v]

    while stack:
        s = stack.pop()
        if s not in visited:
            visited.setdefault(s)
            stack += reversed(adj_dict[s])

    return visited


def bfs(v):
    visited = {}
    queue = [v]

    while queue:
        s = queue[0]
        del queue[0]
        if s not in visited:
            visited.setdefault(s)
            queue += adj_dict[s]
    
    return visited


n, m, v = map(int, input().split())
adj_dict = {i:[] for i in range(1,n+1)}
for i in range(1,m+1):
    a, b = map(int, sys.stdin.readline().split())
    adj_dict[a].append(b)
    adj_dict[b].append(a)

for k in adj_dict:
    adj_dict[k].sort()

dfs_result = dfs(v)
bfs_result = bfs(v)

print(' '.join(list(map(str, dfs_result))))
print(' '.join(list(map(str, bfs_result))))

リファレンス

Code1
:隣接行列を用いてDFS,BFSを実現した.
DFSは再帰関数で実現され,BFSはqueueで実現される.
アクセスしたノードがリストに表示されます.
Code2:
隣接テーブルを用いてDFS,BFSを実現した.
DFSはスタックとして実装され、BFSはqueueとして実装される.
アクセスしたノードはdictで記録されます.
dictを使用すると、リストにアクセスしたノードを記録および確認するよりも高速です.dictでは、ある要素がlistよりも効率的に存在するかどうかを確認するプロセスがあるからです.
また,コード2はコード1よりも速い.