그래프 - 연결·경로·의존성

이 장에서 배우는 것

프로그램을 만드는 데 필요한 작업을 나열했다고 해서 곧바로 실행할 수 있는 것은 아니다. 설정을 읽어야 코드를 생성할 수 있고, 코드를 생성해야 묶음 파일을 만들 수 있다. 작업의 이름만 저장하면 이런 순서를 놓치기 쉽다. 작업과 작업 사이의 연결도 함께 저장해야 한다.

그래프(graph)는 대상과 그 사이의 연결을 표현하는 구조다. 지도 위의 장소와 도로, 사용자와 친구 관계, 작업과 선행 작업을 같은 틀로 다룰 수 있다. 앞 장에서 반복 구조를 식과 코드로 나타냈다면, 이번에는 연결 구조를 코드로 나타낸다. 어떤 대상을 서로 연결할 것인지, 연결에 방향이 있는지부터 결정한다.

• 정점·간선·차수의 뜻을 작은 그래프와 실행 코드로 확인한다.
• 인접 리스트로 연결을 저장하고, 경로와 연결 요소를 찾는다.
• 방향 그래프에서 선행 작업과 후속 작업의 관계를 구분한다.
• 의존성 그래프의 위상 정렬을 구현하고, 순환 때문에 실행 순서를 만들 수 없는 경우를 감지한다.

문제 상황

로컬 개발 도구가 다섯 작업을 처리한다고 하자. 설정을 읽는 작업은 config, 코드를 만드는 작업은 generate, 자원을 준비하는 작업은 assets, 결과를 묶는 작업은 bundle, 결과를 검사하는 작업은 check다.

generate와 assets는 모두 config가 끝난 뒤 시작할 수 있다. bundle은 두 작업이 모두 끝나야 시작할 수 있다. check는 bundle 다음에 실행한다. 작업 이름을 글자순으로 정렬하면 assets가 config보다 먼저 나오므로 요구 조건을 지키지 못한다.

더 난감한 경우도 있다. 설정 작업이 검사 결과를 필요로 하도록 잘못 고치면, 설정을 읽으려면 검사해야 하고 검사하려면 설정을 읽어야 한다. 이때 필요한 것은 임의의 실행 순서가 아니라, 현재 의존성으로는 전체 순서를 만들 수 없다는 판단이다.

실무에서 만나는 곳

빌드 도구는 작업 사이의 의존성을 보고 실행 순서를 정한다. 데이터 처리에서도 원본을 읽고, 변환하고, 결과를 저장하는 순서를 지켜야 한다. 서비스 구성 요소의 시작 순서나 문서 생성 단계에도 같은 문제가 나타난다. 다만 그래프가 알려 주는 것은 입력한 선행 조건에 따른 순서다. 파일이 실제로 존재하는지, 작업이 성공했는지까지 보장하지는 않는다.

정점과 간선을 코드로 저장하기

그래프에서 연결의 대상 하나를 정점(vertex)이라고 한다. 정점 두 개 사이의 연결은 간선(edge)이라고 한다. 전공 수업에서는 보통 정점의 집합을 V, 간선의 집합을 E라고 쓰고, 그래프를 G = (V, E)로 나타낸다. 여기서 괄호는 그래프를 이루는 두 재료를 함께 적었다는 뜻이다.

정점 이름은 위치나 순위를 뜻하지 않는다. "작업실"이라는 문자열을 정점 이름으로 쓰더라도, 그래프가 아는 것은 다른 이름과 어떻게 연결되어 있는지뿐이다. 현실의 거리나 이동 시간을 다루려면 추가 정보가 필요하다. 이번 장에서는 간선마다 수치를 붙이지 않는다.

방향이 없는 연결을 무방향 그래프라고 한다. 두 장소를 오가는 통로를 생각하면 된다. 아래 그래프에서는 작업실·창고·출입구가 이어져 있고, 휴게실은 따로 떨어져 있다.

각 정점에 직접 연결된 이웃들을 저장하는 방식을 인접 리스트(adjacency list)라고 한다. 여기서 인접한다는 말은 간선 하나로 바로 연결된다는 뜻이다. Python에서는 정점 이름을 이웃 목록에 대응시키는 딕셔너리로 표현할 수 있다. 딕셔너리는 키로 값을 찾는 자료형이며, graph["작업실"]은 해당 정점의 이웃 목록을 꺼낸다.

graph = {
    "작업실": ["창고"],
    "창고": ["작업실", "출입구"],
    "출입구": ["창고"],
    "휴게실": [],
}

for vertex in graph:
    print(vertex, len(graph[vertex]))

degree_sum = sum(len(neighbors) for neighbors in graph.values())
print("차수 합:", degree_sum)
print("간선 수:", degree_sum // 2)

출력은 다음과 같다. 딕셔너리를 순회하면 이 코드에서는 작성한 순서대로 키가 나온다. values()는 이웃 목록들을 꺼내며, sum()은 계산된 수를 더한다.

작업실 1
창고 2
출입구 1
휴게실 0
차수 합: 4
간선 수: 2

한 정점에 닿는 간선의 수를 차수(degree)라고 한다. 위 그래프에서 창고의 차수는 2다. 연결이 하나도 없는 휴게실의 차수는 0이며, 이런 정점을 고립 정점이라고 한다. 빈 목록도 정점의 존재를 나타내므로 생략하면 안 된다.

무방향 간선 하나는 양쪽 이웃 목록에 한 번씩 나타난다. 따라서 이 표현에서는 차수의 합이 간선 수의 두 배가 된다. 다만 같은 간선을 중복 저장하지 않고, 자기 자신으로 향하는 간선도 없다고 정한 예제다. 이 조건 없이 목록 길이를 차수로 해석하면 수가 달라질 수 있다.

무방향 그래프를 저장할 때 지켜야 할 약속

대상	저장 예	뜻
정점	"휴게실": []	연결이 없어도 키로 남긴다.
무방향 간선	작업실 목록에 창고, 창고 목록에 작업실	양쪽에서 같은 연결을 확인할 수 있다.
차수	len(graph["창고"])	이 예제의 표현에서는 이웃 수와 같다.
간선 수	차수 합을 2로 나눈 값	양쪽에 저장한 연결을 한 번만 센다.

만약 창고 목록에서 작업실을 지우면, 작업실에서 창고로는 갈 수 있지만 반대 방향으로는 갈 수 없게 된다. 같은 딕셔너리 모양이라도 저장 규칙을 어기면 다른 관계를 표현한다. 자료형을 골랐다는 사실보다 그 자료형에 어떤 약속으로 넣었는지가 더 중요하다.

경로를 따라가며 연결 요소 찾기

간선을 따라 정점들을 차례로 이동한 것을 생각해 보자. 작업실에서 창고를 거쳐 출입구로 갈 수 있다. 이처럼 두 정점을 잇는 이동 순서를 경로(path)라고 한다. 용어를 더 세밀하게 나누는 수업에서는 정점의 반복을 허용하는 이동을 보행이라고 하고, 정점을 반복하지 않는 것을 경로라고 구분한다. 여기서는 방문한 정점을 다시 확장하지 않으며, 도달 가능한지를 확인한다.

시작 정점에서 간선을 따라 목적지까지 갈 수 있으면 도달 가능하다고 한다. 자기 자신에는 간선을 한 번도 지나지 않고 도달할 수 있다고 정한다. 따라서 고립 정점도 자기 자신에는 도달 가능하다.

연결을 따라 정점을 살펴보는 과정을 탐색이라고 한다. 아래 코드는 방금 정의한 graph 뒤에 붙여 실행한다. pending에는 앞으로 살펴볼 정점을 넣고, seen에는 이미 발견한 정점을 넣는다.

def reachable(graph, start):
    seen = {start}
    pending = [start]

    while pending:
        current = pending.pop()
        for neighbor in graph[current]:
            if neighbor not in seen:
                seen.add(neighbor)
                pending.append(neighbor)

    return seen


print(sorted(reachable(graph, "작업실")))
print("휴게실 도달:", "휴게실" in reachable(graph, "작업실"))
print(sorted(reachable(graph, "휴게실")))

['작업실', '창고', '출입구']
휴게실 도달: False
['휴게실']

pop()은 리스트 끝의 원소를 꺼내면서 지운다. 나중에 넣은 정점을 먼저 꺼내므로, 이웃 하나를 따라 더 깊이 들어가는 방식으로 진행한다. 전공 수업에서는 이를 깊이 우선 탐색(depth-first search)이라고 부른다. 나중에 넣은 것을 먼저 꺼내는 저장 방식을 스택이라고 한다. 여기서는 별도의 자료형을 만들지 않고 리스트를 사용한다.

정점을 발견하는 즉시 seen에 넣는 이유는 같은 정점을 여러 번 대기 목록에 넣지 않기 위해서다. 작업실과 창고는 서로의 이웃이다. 방문 기록이 없으면 작업실에서 창고로, 창고에서 작업실로 되돌아가는 일이 반복된다. 연결 구조에서는 반복이 끝난다는 근거도 코드에 있어야 한다.

sorted()는 정렬된 새 리스트를 반환한다. 탐색 결과는 집합이므로 그대로 출력하는 대신 정렬하여 출력 순서를 고정했다. 이 코드는 실제 이동 경로를 반환하지 않는다. 경로를 출력하려면 각 정점을 어느 정점에서 발견했는지도 저장해야 한다.

무방향 그래프에서 서로 도달할 수 있는 정점들을 최대한 묶은 덩어리를 연결 요소(connected component)라고 한다. 최대한 묶었다는 말은 같은 덩어리에 넣을 수 있는 정점을 밖에 남기지 않는다는 뜻이다. 작업실과 창고만 묶으면 출입구도 이어져 있으므로 아직 하나의 연결 요소를 다 모은 것이 아니다.

def connected_components(graph):
    remaining = set(graph)
    groups = []

    for start in sorted(graph):
        if start in remaining:
            group = reachable(graph, start)
            groups.append(sorted(group))
            remaining.difference_update(group)

    return groups


print(connected_components(graph))

[['작업실', '창고', '출입구'], ['휴게실']]

set(graph)는 딕셔너리의 키들을 집합으로 만든다. difference_update()는 찾은 정점들을 남은 집합에서 제거한다. 한 연결 요소를 찾으면 그 안의 다른 정점에서 다시 탐색할 필요가 없다. 휴게실도 정점 하나로 이루어진 연결 요소다.

이 함수는 무방향 그래프라는 전제에서 사용한다. 한쪽으로만 갈 수 있는 관계에서는 한 정점에서 도달한 집합을 곧바로 연결 요소라고 부를 수 없다. 방향을 무시할지, 서로 오갈 수 있어야 할지에 따라 묶는 기준이 달라지기 때문이다.

방향과 의존성으로 실행 순서 정하기

방향 그래프(directed graph)는 간선에 출발점과 도착점이 있는 그래프다. 이번 의존성 그래프에서는 A → B를 “A를 끝내야 B를 시작할 수 있다”로 정한다. 화살표 방향은 저장 전에 정해야 한다. “B가 A에 의존한다”는 문장은 주어가 B이지만, 이 약속에서 화살표는 A에서 B로 향한다.

방향 그래프에서는 차수를 두 가지로 나눈다. 정점으로 들어오는 간선의 수는 진입 차수(in-degree), 정점에서 나가는 간선의 수는 진출 차수(out-degree)다. 그림에서 bundle의 진입 차수는 2이고 진출 차수는 1이다. config의 진입 차수는 0이므로 처음부터 선택할 수 있다.

모든 간선 A → B에 대해 A가 B보다 앞에 오도록 정점을 나열하는 것을 위상 정렬(topological sort)이라고 한다. 숫자나 이름의 크기로 정렬하는 방식과는 다르다. 서로 선행 조건이 없는 두 작업의 상대 순서는 바뀔 수 있으므로 정답이 여러 개일 수 있다.

다음 세 단계를 반복하면 위상 정렬을 구할 수 있다. 전공 수업에서는 이 방법을 칸 알고리즘이라고도 부른다.

1. 각 정점의 진입 차수를 센다. 진입 차수가 0인 정점들을 대기 목록에 넣는다.
2. 대기 목록에서 정점 하나를 꺼내 결과에 넣는다. 그 정점에서 나가는 간선마다 도착점의 진입 차수를 1 줄인다.
3. 진입 차수가 새로 0이 된 정점을 대기 목록에 넣는다. 꺼낼 정점이 없을 때까지 반복한다.

진입 차수를 줄이는 것은 완료한 선행 조건을 계산에서 제외한다는 뜻이다. 실제 그래프의 간선을 지울 필요는 없다. bundle은 선행 작업 하나가 끝났을 때 2에서 1이 되고, 나머지도 끝나야 0이 된다.

이 설명에서 작업을 결과에 넣는 것은 실행 순서를 계산하는 일이다. 아래 완성 코드는 빌드 명령을 실행하지 않는다. 실제 실행기에 연결할 때는 선행 작업이 성공적으로 끝났다는 사실을 확인한 다음 후속 작업을 풀어 주어야 한다.

정점을 따라가다가 시작한 정점으로 되돌아오는 방향 연결을 순환(cycle)이라고 한다. 예를 들어 generate → bundle → generate가 있으면 두 작업 모두 상대가 먼저 끝나기를 기다린다. 자기 자신을 선행 작업으로 지정한 경우에도 순환이 생긴다.

왜 정렬 결과의 길이로 순환을 감지할 수 있을까. 순환 위의 정점들은 앞 정점에서 들어오는 간선이 남기 때문에 진입 차수가 0이 되지 않는다. 반대로 처리하지 못한 정점이 남았는데 모두 진입 차수가 양수라면, 남은 정점 하나에서 선행 정점을 계속 거슬러 올라갈 수 있다. 남은 정점 수는 유한하므로 언젠가 같은 정점을 다시 만난다. 그 사이에 순환이 있다.

따라서 결과에 모든 정점이 들어갔다면 순서를 만들었고, 일부가 남았다면 순환이 있다. 단, 남은 정점 모두가 순환의 구성원인 것은 아니다. 순환 뒤에서 기다리는 후속 작업도 남는다. 완성 코드는 순환의 존재와 처리하지 못한 작업 목록을 알려 주며, 순환 경로 자체를 찾아내지는 않는다.

완성 코드

다음 내용을 main.py로 저장한다. 입력은 작업별 선행 작업 목록이다. build_graph()가 이를 선행 작업에서 후속 작업으로 향하는 인접 리스트로 바꾼다. 예제에서는 모든 선행 작업 이름이 작업 키로 등록되어 있다고 가정한다. 같은 선행 작업이 반복되면 한 번만 반영한다.

기본 예제와 순환 예제, 자기 자신을 기다리는 예제를 차례로 실행한다. 외부 패키지나 파일은 필요하지 않다.

def build_graph(dependencies):
    graph = {task: [] for task in sorted(dependencies)}

    for task in sorted(dependencies):
        for prerequisite in sorted(set(dependencies[task])):
            graph[prerequisite].append(task)

    return graph


def topological_sort(graph):
    indegree = {task: 0 for task in graph}

    for followers in graph.values():
        for follower in followers:
            indegree[follower] += 1

    ready = sorted(task for task in graph if indegree[task] == 0)
    head = 0
    order = []

    while head < len(ready):
        task = ready[head]
        head += 1
        order.append(task)

        for follower in sorted(graph[task]):
            indegree[follower] -= 1
            if indegree[follower] == 0:
                ready.append(follower)

    blocked = sorted(task for task in graph if indegree[task] > 0)
    return order, blocked


def show_result(label, dependencies):
    graph = build_graph(dependencies)
    order, blocked = topological_sort(graph)

    print(label)
    if blocked:
        print("순환 감지: 전체 실행 순서를 만들 수 없다.")
        print("처리하지 못한 작업:", ", ".join(blocked))
    else:
        print("실행 순서:", " -> ".join(order))
    print()


def main():
    normal = {
        "config": [],
        "generate": ["config"],
        "assets": ["config"],
        "bundle": ["generate", "assets"],
        "check": ["bundle"],
    }

    cyclic = {
        "config": [],
        "generate": ["config", "bundle"],
        "assets": ["config"],
        "bundle": ["generate", "assets"],
        "check": ["bundle"],
    }

    self_cycle = {
        "solo": ["solo"],
    }

    show_result("정상 의존성", normal)
    show_result("순환 의존성", cyclic)
    show_result("자기 의존성", self_cycle)


if __name__ == "__main__":
    main()

줄별 해설

def build_graph(dependencies):는 입력을 그래프 표현으로 바꾸는 함수다. 입력의 "bundle": ["generate", "assets"]는 묶음 작업의 선행 작업 두 개를 뜻한다. 반환할 그래프에서는 반대로 generate와 assets의 이웃 목록에 bundle이 들어간다.

{task: [] for task in sorted(dependencies)}는 작업마다 빈 목록을 만드는 딕셔너리 내포다. 내포는 반복문으로 원소를 만들고 모으는 축약 문법이다. 모든 작업을 먼저 등록하므로 후속 작업이 없는 check도 그래프에 남는다.

바깥 for는 작업을 하나씩 고른다. 안쪽 for의 set()은 선행 작업 이름의 중복을 없애고, sorted()는 처리 순서를 고정한다. graph[prerequisite].append(task)는 선행 작업의 후속 목록에 현재 작업을 추가한다.

topological_sort()의 첫 줄은 모든 진입 차수를 0으로 만든다. 다음 두 반복문은 각 간선의 도착점에 1을 더한다. 간선의 출발점에 더하는 것이 아니라는 점을 확인한다. graph.values()에서 꺼내는 각 목록은 그 출발점의 후속 작업들이다.

ready = sorted(...)는 진입 차수가 0인 작업만 골라 처음 대기 목록을 만든다. 괄호 안의 task for ... if ...는 조건에 맞는 작업 이름을 하나씩 제공하는 표현이다. 여기서는 sorted()가 그 이름들을 받아 리스트로 만든다.

head는 다음에 읽을 위치다. ready[head]를 읽은 뒤 head를 1 늘리면 앞에서부터 차례로 처리한다. 먼저 들어온 원소를 먼저 꺼내는 방식을 큐(queue)라고 한다. 리스트 맨 앞을 매번 삭제하는 대신 읽을 위치를 이동하므로, 뒤의 원소들을 앞으로 당기는 작업을 피한다.

order.append(task)는 선택한 작업을 결과 뒤에 붙인다. 이어지는 반복문은 그 작업의 후속 작업들만 살핀다. 각 진입 차수를 1 줄이고, 정확히 0이 되는 순간 대기 목록에 추가한다. 중복 간선을 제거했고 각 출발점을 한 번만 처리하므로, 같은 작업을 반복해서 추가하지 않는다.

처음 대기 목록과 각 후속 목록을 정렬했으므로 같은 입력에는 같은 결과가 나온다. 하지만 매 순간 가능한 작업 중 이름이 가장 앞선 것을 고른다는 뜻은 아니다. 새로 가능해진 작업은 이미 기다리던 작업 뒤에 붙는다. 결정적인 출력과 사전순으로 가장 작은 순서는 서로 다른 요구다.

blocked는 반복이 끝났는데도 진입 차수가 남은 작업들이다. return order, blocked는 두 값을 튜플로 묶어 반환한다. 튜플은 여러 값을 순서대로 묶는 자료형이다. order, blocked = ...는 반환된 두 값을 각각 이름에 나누어 담는다.

show_result()는 계산과 출력을 나눈다. 남은 작업이 있으면 부분 순서를 전체 실행 순서처럼 출력하지 않는다. ", ".join(blocked)는 문자열 사이에 쉼표와 공백을 넣어 하나로 합친다. 마지막 print()는 사례 사이에 빈 줄을 만든다.

main()은 사례 세 개를 준비한다. 순환 사례에서는 generate의 선행 작업에 bundle을 추가했다. 자기 의존 사례는 정점 하나만으로도 순환이 생긴다는 작은 반례다. 마지막 조건은 이 파일을 직접 실행했을 때 main()을 호출하는 Python의 실행 관례다.

정점 수를 V, 간선 수를 E라고 하면, 정렬 작업을 제외한 진입 차수 계산과 큐 처리는 정점과 간선을 각각 일정한 횟수만큼 살핀다. 전공 수업에서는 이를 시간 복잡도 O(V + E)라고 표현한다. 이 코드에는 출력 순서를 고정하기 위한 정렬도 있으므로 전체 실행 시간을 그 식 하나로만 설명하면 안 된다.

실행 결과

터미널에서 파일을 저장한 디렉터리로 이동한 뒤 다음 명령을 실행한다. 프로그램은 입력을 기다리지 않고 끝난다. 마지막 사례 뒤에도 빈 줄이 하나 출력된다.

python3 main.py

정상 의존성
실행 순서: config -> assets -> generate -> bundle -> check

순환 의존성
순환 감지: 전체 실행 순서를 만들 수 없다.
처리하지 못한 작업: bundle, check, generate

자기 의존성
순환 감지: 전체 실행 순서를 만들 수 없다.
처리하지 못한 작업: solo

정상 사례에서는 config가 끝난 뒤 assets와 generate를 선택할 수 있다. 후속 목록을 정렬했으므로 assets가 먼저 들어간다. 둘을 모두 처리해야 bundle의 진입 차수가 0이 된다.

순환 사례에서는 config와 assets까지 처리할 수 있다. 그러나 generate와 bundle이 서로 기다린다. check는 순환을 이루는 간선을 갖지 않아도 bundle을 기다리므로 함께 남는다. 이 차이가 출력 문구를 “순환에 속한 작업”이 아니라 “처리하지 못한 작업”으로 정한 이유다.

실무에서 자주 틀리는 것

의존성을 읽은 방향 그대로 간선을 넣는다

입력이 작업에서 선행 작업을 가리킨다고 해서, 실행 순서를 계산할 그래프도 같은 방향이어야 하는 것은 아니다. 다음은 작은 입력에서 방향 차이를 확인하는 코드다. 두 조각은 각각 실행할 수 있다.

틀린 코드는 선행 작업이 필요한 build를 먼저 선택 가능한 작업으로 만든다.

dependencies = {"prepare": [], "build": ["prepare"]}
graph = {task: [] for task in dependencies}

for task, prerequisites in dependencies.items():
    for prerequisite in prerequisites:
        graph[task].append(prerequisite)

indegree = {task: 0 for task in graph}
for followers in graph.values():
    for follower in followers:
        indegree[follower] += 1

print(sorted(task for task in graph if indegree[task] == 0))
# ['build']

고친 코드는 준비 작업에서 빌드 작업으로 연결한다. items()는 딕셔너리의 키와 값을 한 쌍씩 꺼낸다.

dependencies = {"prepare": [], "build": ["prepare"]}
graph = {task: [] for task in dependencies}

for task, prerequisites in dependencies.items():
    for prerequisite in prerequisites:
        graph[prerequisite].append(task)

indegree = {task: 0 for task in graph}
for followers in graph.values():
    for follower in followers:
        indegree[follower] += 1

print(sorted(task for task in graph if indegree[task] == 0))
# ['prepare']

간선에 나타난 정점만 등록한다

연결이 없는 작업은 실행할 필요가 없다는 뜻이 아니다. 다른 작업과 독립적으로 실행할 수 있다는 뜻이다. 다음 틀린 코드는 간선을 읽을 때만 정점을 등록하므로 standalone이 사라진다.

tasks = ["prepare", "build", "standalone"]
edges = [("prepare", "build")]
graph = {}

for source, target in edges:
    graph.setdefault(source, []).append(target)
    graph.setdefault(target, [])

print("standalone" in graph)
# False

setdefault()는 키가 없으면 기본값을 등록하고 해당 값을 돌려준다. 간선만으로 그래프를 조립할 때는 편하지만, 간선에 나오지 않는 정점을 만들어 주지는 않는다. 고친 코드는 전체 작업을 먼저 등록한다.

tasks = ["prepare", "build", "standalone"]
edges = [("prepare", "build")]
graph = {task: [] for task in tasks}

for source, target in edges:
    graph[source].append(target)

print("standalone" in graph)
# True

정점을 다시 만났다는 이유만으로 순환이라고 한다

방향 그래프에서 서로 다른 두 경로가 같은 정점에 합류할 수 있다. 앞에서 본 bundle이 그런 경우다. 방문한 정점이 다시 나왔다는 사실만으로 순환을 판정하면 정상적인 합류도 잘못 막는다.

다음 틀린 코드는 간선의 도착점을 두 번 보았다는 이유로 순환을 보고한다.

graph = {"left": ["end"], "right": ["end"], "end": []}
seen = set()
has_cycle = False

for followers in graph.values():
    for follower in followers:
        if follower in seen:
            has_cycle = True
        seen.add(follower)

print(has_cycle)
# True

위 그래프에서 end는 어디로도 나가지 않으므로 되돌아오는 경로가 없다. 고친 코드는 완성 코드의 함수 정의 뒤에서 실행한다. 전체 정점을 처리할 수 있는지 확인하면 이 사례를 올바르게 판정한다.

graph = {"left": ["end"], "right": ["end"], "end": []}
order, blocked = topological_sort(graph)
print(bool(blocked))
print(len(order) == len(graph))
# False
# True

bool()은 값이 비어 있는지 등을 참과 거짓으로 바꾼다. 빈 목록은 거짓이고, 원소가 있는 목록은 참이다. 탐색으로 방향 순환을 찾는 별도 방법도 있지만, 그때는 이미 처리를 마친 정점과 현재 따라가는 경로 위의 정점을 구분해야 한다.

남은 작업 전부를 순환의 구성원이라고 표시한다

완성 코드의 순환 사례에서 check는 순환에서 이어지는 후속 작업이다. 이를 순환 자체에 속한다고 표시하면 수정해야 할 의존성을 잘못 짚을 수 있다. 다음 틀린 진단은 계산한 목록보다 강한 주장을 한다.

blocked = ["bundle", "check", "generate"]
print("순환에 속한 작업:", ", ".join(blocked))

고친 진단은 실제로 확인한 사실만 말한다. 정확한 순환 경로가 필요하면 추가 탐색을 구현해야 한다.

blocked = ["bundle", "check", "generate"]
print("순환 때문에 처리하지 못한 작업:", ", ".join(blocked))

한눈에 보기

그래프 개념을 코드에서 확인하는 기준

개념	뜻	코드에서 볼 곳	주의할 점
정점	연결의 대상	딕셔너리의 키	고립 정점도 등록한다.
간선	대상 사이의 연결	이웃 목록의 항목	방향과 중복 규칙을 정한다.
차수	정점에 닿는 간선 수	무방향 예제의 이웃 수	방향이 있으면 들어옴과 나감을 나눈다.
도달 가능성	간선을 따라 갈 수 있음	reachable()	방문 기록으로 반복 처리를 막는다.
연결 요소	서로 이어진 최대 묶음	connected_components()	여기서는 무방향 그래프에 적용한다.
위상 정렬	모든 선행 조건을 지키는 나열	진입 차수 0인 작업부터 선택	가능한 순서는 여러 개일 수 있다.
순환 감지	의존성이 되돌아와 전체 순서가 막힘	처리 뒤 남은 정점 확인	남은 정점이 모두 순환 위에 있지는 않다.

연습 문제

1. 무방향 예제에 "보관실": []을 추가한다. 연결 요소는 몇 개가 되는가. 이어서 휴게실과 보관실을 양방향으로 연결하면 몇 개가 되는가. 코드로 확인한다.
2. 완성 코드의 정상 입력에 "notes": []을 추가한다. notes는 config보다 먼저 실행되어야 하는가. 실제 출력 순서와 의존성이 요구하는 조건을 구분해 설명한다.
3. 완성 코드의 함수들로 {"first": ["last"], "middle": ["first"], "last": ["middle"], "free": []}를 처리한다. 결과에 들어가는 작업과 처리하지 못하는 작업을 예상한 뒤 확인한다.
4. 입력에 등록되지 않은 선행 작업이 있으면 현재 build_graph()는 해당 키를 찾다가 실행을 중단한다. 그래프를 만들기 전에 빠진 작업 이름을 정렬된 목록으로 반환하는 함수를 작성한다. 빠진 이름이 있으면 그래프 생성을 진행하지 않도록 호출 코드도 작성한다.

정답과 해설

독립된 정점과 연결 요소

보관실을 추가하면 연결 요소는 3개다. 휴게실과 보관실을 연결하면 둘이 한 묶음이 되어 2개가 된다. 정점 수는 그대로여도 간선 하나가 연결 요소 수를 바꿀 수 있다. 다음 코드는 앞서 작성한 탐색 함수들과 함께 실행한다.

rooms = {
    "작업실": ["창고"],
    "창고": ["작업실", "출입구"],
    "출입구": ["창고"],
    "휴게실": [],
    "보관실": [],
}

print(len(connected_components(rooms)))
rooms["휴게실"].append("보관실")
rooms["보관실"].append("휴게실")
print(len(connected_components(rooms)))
# 3
# 2

독립 작업의 상대 순서

notes와 config 사이에는 선행 조건이 없다. 어느 쪽을 먼저 실행해도 의존성은 지킨다. 현재 구현에서는 처음 대기 목록이 ["config", "notes"]가 된다. config를 처리하며 추가한 작업들은 이미 기다리던 notes 뒤에 붙는다.

dependencies = {
    "config": [],
    "generate": ["config"],
    "assets": ["config"],
    "bundle": ["generate", "assets"],
    "check": ["bundle"],
    "notes": [],
}
order, blocked = topological_sort(build_graph(dependencies))
print(order)
print(blocked)
# ['config', 'notes', 'assets', 'generate', 'bundle', 'check']
# []

이 출력의 상대 순서를 모두 필수 조건으로 받아들이면 안 된다. 위상 정렬에서 지켜야 하는 것은 입력 간선의 앞뒤 관계다. 구현이 고른 순서에는 그 조건 외에 대기 목록을 다루는 방식도 반영된다.

순환과 독립 작업

first → middle → last → first가 순환이다. free는 그 순환과 연결되지 않았으므로 처리할 수 있다. 일부 작업을 처리했다는 사실은 전체 실행 순서를 만들었다는 뜻이 아니다.

dependencies = {
    "first": ["last"],
    "middle": ["first"],
    "last": ["middle"],
    "free": [],
}
order, blocked = topological_sort(build_graph(dependencies))
print(order)
print(blocked)
# ['free']
# ['first', 'last', 'middle']

등록되지 않은 선행 작업 검사

선행 작업으로 언급된 이름들을 모은 뒤 등록된 작업 집합을 빼면 빠진 이름만 남는다. 입력 오류와 순환은 서로 다른 문제이므로 그래프를 조립하기 전에 구분한다. 아래 호출 부분은 완성 코드의 함수 정의 뒤에서 실행한다.

def missing_tasks(dependencies):
    mentioned = set()
    for prerequisites in dependencies.values():
        mentioned.update(prerequisites)
    return sorted(mentioned - set(dependencies))


dependencies = {"bundle": ["generate"]}
missing = missing_tasks(dependencies)

if missing:
    print("등록되지 않은 작업:", ", ".join(missing))
else:
    order, blocked = topological_sort(build_graph(dependencies))
    print(order, blocked)

# 등록되지 않은 작업: generate

update()는 여러 원소를 집합에 추가한다. 선행 작업이 빠졌다고 해서 자동으로 빈 작업을 만들면 오타를 정상 입력처럼 받아들일 수 있다. 작업 목록을 입력의 기준으로 삼았다면, 빠진 이름을 먼저 알려 주는 편이 그 약속에 맞는다.

그래프를 사용할 때는 정점과 간선의 의미, 방향, 중복 처리 규칙을 먼저 적는다. 그다음 작은 입력으로 연결과 순서를 확인한다. 다음 장에서 다룰 트리는 연결에 추가 제약이 있는 구조다. 이번에 만든 정점·간선·방문 기록의 관점이 계층 구조를 살펴보는 출발점이 된다.