인접 행렬로 DFS와 BFS 구현하기

간선 목록을 파일에서 읽어 인접 행렬로 만들고, 같은 그래프를 두 순서로 훑는다.

행렬 만들기

f = open('adjacencyMatrix/input.txt', 'r')
node = int(f.readline())
adj = [[0] * node for i in range(node)]

for a in f.readlines():
    i, j = map(int, a.strip().split())
    adj[i][j] = 1
    adj[j][i] = 1

첫 줄이 정점 수고 그 다음부터 간선이 한 줄에 하나씩이다. 무방향이라 adj[i][j] 와 adj[j][i] 를 같이 세운다.

정점 수만큼 정사각 행렬을 잡으므로 간선이 없는 정점도 자리를 차지한다. 이 입력은 정점이 10개인데 간선에 나오는 건 0부터 7까지라, 8과 9는 아무 데도 연결되지 않은 채 행렬에만 있다.

DFS

def dfs(i):
    dfs_path.append(i)

    for j in range(node):
        if adj[i][j] == 1 and j not in dfs_path:
            dfs(j)

지금 정점을 경로에 넣고, 연결된 정점 중 아직 안 간 곳으로 바로 내려간다.

방문 여부를 dfs_path 에서 in 으로 확인한다. 경로 리스트가 방문 기록을 겸하는 셈이다. 짧아서 좋은데 정점이 많아지면 매번 리스트를 처음부터 훑게 된다.

되돌리는 코드가 없다. 한 번 들어간 정점은 계속 남으므로 모든 경로가 아니라 순회 하나만 나온다.

BFS

def bfs(start):
    q = [start]
    visited = {start}
    path = []

    while q:
        cur = q.pop(0)
        path.append(cur)

        for j in range(node):
            if adj[cur][j] == 1 and j not in visited:
                visited.add(j)
                q.append(j)

    return path

이쪽은 방문 집합을 따로 뒀다. 그리고 큐에 넣을 때 표시한다.

넣을 때 표시하지 않으면 같은 정점이 큐에 여러 번 들어간다. 여러 정점에서 같은 이웃을 가리킬 수 있기 때문이다. 꺼낼 때 걸러도 답은 맞지만 큐가 불필요하게 커진다.

DFS 쪽은 리스트에 in, BFS 쪽은 집합에 in 으로 두 방식이 섞여 있다. 하는 일은 같다.

결과

DFS: [0, 1, 2, 3, 4, 5, 6, 7]
BFS: [0, 1, 5, 2, 6, 7, 4, 3]

DFS는 한 방향으로 끝까지 파고들어 번호가 이어지는 모양이 됐다. BFS는 0의 이웃인 1과 5를 먼저 보고, 그 다음 층으로 넘어간다.

둘 다 8개만 나온다. 연결되지 않은 8과 9에는 닿지 못한다. 전체를 훑으려면 시작점을 바꿔가며 다시 불러야 한다.

인접 행렬의 대가

for j in range(node) 로 매번 한 행을 전부 훑는다. 실제 이웃이 둘뿐이어도 정점 수만큼 확인한다.

이 그래프는 정점 10개에 간선 10개라 행렬이 대부분 0이다. 이웃 목록을 정점마다 리스트로 들고 있으면 이웃 수만큼만 돌면 된다. 정점 수에 비해 간선이 적으면 그쪽이 낫다.