1mo.dev

다크 모드

DAG와 위상 정렬 ​

커밋 그래프가 왜 순환 없는 그래프(DAG)여야 하는지, 그리고 그 위에서 부모가 먼저 나오도록 로그를 정렬하는 위상 정렬을 다룹니다.

그래프와 DAG - 왜 순환이 없어야 하나? ​

그래프 = 점(노드)과 선(간선)으로 이루어진 구조. DAG (Directed Acyclic Graph) = 방향이 있고(Directed), 루프(사이클)가 없는(Acyclic) 그래프.

왜 커밋 구조에 사이클이 있으면 안 되나?

  • A의 부모가 B, B의 부모가 A라면 → "누가 먼저냐"를 알 수 없음
  • 로그 출력이 무한 반복되거나, 조상 계산이 끝나지 않음

그래서 커밋 생성 규칙("부모는 항상 이미 존재하는 과거 커밋")이 자연스럽게 사이클을 막아줍니다.

그래프와 DAG 비교 ​

구분그래프DAG (Directed Acyclic Graph)
방향있을 수도, 없을 수도 있음반드시 있음 (단방향)
사이클존재 가능없음 (순환 X)
  • 노드: 점, 간선: 노드와 노드를 잇는 선
  • A→C, C→B, B→A처럼 한 바퀴 돌아오면 사이클이 있는 그래프
  • A→B, A→C, B→C처럼 되돌아오는 길이 없으면 DAG

DAG와 그래프, DFS/BFS 손글씨 노트

직접 손으로 정리한 노트: DAG와 그래프, DFS/BFS

위상 정렬 - 부모가 먼저 나오는 로그 ​

요구사항: LOG는 "최신순 나열"이 아니라 부모 커밋이 항상 자식보다 먼저 출력되어야 합니다. 이런 정렬을 **위상 정렬(topological sort)**이라고 합니다.

간단한 방법 (DFS 후위 순회):

  1. 아직 출력 안 된 커밋을 하나 고른다
  2. 그 커밋의 부모들을 먼저 재귀적으로 출력하고
  3. 마지막에 자기 자신을 출력한다
python
def topo_visit(commit, visited, out):
    """부모를 먼저 방문한 뒤 자신을 기록하는 함수"""
    if commit.hash in visited:
        return                    # 이미 처리한 커밋이면 건너뜀
    visited.add(commit.hash)
    for parent in commit.parents: # 1) 부모 먼저
        topo_visit(parent, visited, out)
    out.append(commit)            # 2) 그다음 자신

이렇게 하면 모든 커밋에서 "조상들이 항상 앞에" 오는 순서가 보장됩니다.

위상 정렬 결과는 하나가 아닐 수 있다 ​

  • 부모 커밋: 이전에 만들어진 커밋 (과거)
  • 자식 커밋: 부모를 기반으로 새롭게 작성된 커밋 (미래)
  • 브랜치: main, develop처럼 커밋을 가리키는 이름표이고, HEAD는 현재 브랜치를 가리킴

예시: M1(최초 커밋), M2, F1(feature 브랜치 분기), F2, M3(Merge Commit)

  • 출력 결과 1: M1 → M2 → F1 → F2 → M3
  • 출력 결과 2: M1 → F1 → F2 → M2 → M3

부모가 자식보다 먼저 나오기만 하면 되므로 위상 정렬 결과는 하나로 정해지지 않을 수 있습니다.

BFS/DFS 탐색 순서와 위상 정렬 손글씨 노트

직접 손으로 정리한 노트: 탐색 순서와 위상 정렬

더 넓게 보면 위상 정렬은 커밋뿐 아니라 "선행 작업이 끝나야 다음 작업을 할 수 있는" 모든 곳에 쓰입니다. 예) 선수 과목 순서 정하기, 빌드할 때 의존 패키지부터 설치하기. 커밋 두 개의 공통 조상을 찾는 문제는 최소 공통 조상 (LCA), 그래프를 차례로 훑는 방법은 DFS & BFS에서 다룹니다.

정리 ​

개념비전공자 버전 요약
커밋/DAG"누가 언제 뭘 했다" 기록 + 루프 없는 부모 가리키기
위상 정렬부모를 항상 자식보다 먼저 보여주는 출력 순서

출처: Codyssey-B1/B5-2 (학습 노트 포함)