정점·간선·인접 목록과 인접 행렬

지도·친구 관계·작업 의존성을 같은 방식으로 표현할 수 있습니다. 목표는 자료의 값보다 자료 사이의 연결을 읽고, 그래프 입력을 만들 수 있는 것입니다. 리스트와 딕셔너리를 복습하면 그래프 경험 없이 시작할 수 있습니다.

개념과 약속

그래프의 정점은 대상, 간선은 대상 사이의 관계입니다. 무방향 간선 A—B는 양쪽으로 이동할 수 있어 인접 목록에도 양쪽을 적습니다. 방향 간선 A→B는 출발 A가 tail, 도착 B가 head이며 반대 이동을 뜻하지 않습니다. 가중치는 이동 비용처럼 간선에 붙는 값입니다. 무방향 차수는 연결된 간선 수, 방향 그래프는 들어오는 진입 차수와 나가는 진출 차수를 구분합니다.

인접 목록은 정점별 이웃 목록이고, 인접 행렬은 정점 순서를 정해 행 i·열 j에 연결 여부를 적습니다. 자기 고리와 다중 간선은 이 본문의 단순 무방향 예제에서는 제외합니다.

고립점·간선 없는 그래프·완전 그래프

이웃이 없는 차수 0의 정점이 고립점입니다. {"A": [], "B": []}는 정점 두 개가 모두 고립되어 간선이 0인 그래프입니다. 정점도 하나 없는 {}와 구분합니다. 원문의 널 그래프는 간선이 없는 그래프를 뜻하며, 다른 자료에서 이 용어를 읽을 때도 정점 수와 간선 수의 약속을 확인하세요.

단순 무방향 완전 그래프는 서로 다른 모든 정점 쌍이 하나의 간선으로 이어져 있습니다. n개 정점에서 각 정점은 다른 n-1개와 연결됩니다. n(n-1)로 세면 A—B와 B—A라는 같은 간선을 두 번 세므로 2로 나눈 n(n-1)/2가 간선 수이자 단순 무방향 그래프의 최대 간선 수입니다.

예를 들어 A,B,C,D 네 정점이면 A—B, A—C, A—D, B—C, B—D, C—D의 여섯 간선입니다. 자기 고리가 없는 방향 그래프에서 서로 다른 모든 순서쌍의 간선을 넣으면 A→B와 B→A가 별개의 간선이므로 최대 4×3=12개입니다. 무방향 행렬은 대칭이지만 방향 행렬은 양방향 간선을 모두 넣었다는 추가 조건 없이 대칭이라고 할 수 없습니다.

보행·단순경로·트레일·사이클

간선을 따라 이동한 정점 열을 보행(walk)이라고 합니다. 간선 수가 보행의 길이이고, 정점이나 간선을 다시 지날 수도 있습니다. 정점이 한 번도 반복되지 않는 보행은 단순경로(simple path), 간선이 반복되지 않는 보행은 트레일(trail)입니다. 무방향 A—B를 B→A로 다시 지나도 같은 간선을 반복한 것입니다. 모든 단순경로는 트레일이지만 트레일에는 같은 정점을 다시 방문하는 경우가 있습니다.

사이클은 한 개 이상 간선을 지나는 닫힌 트레일에서, 마지막에 다시 적은 출발점을 빼면 모든 정점이 서로 다른 경우입니다. 이 본문의 자기 고리·다중 간선 없는 단순 무방향 사례에서는 최소 세 간선이 필요합니다. A→B→A는 닫힌 보행이지만 같은 무방향 간선을 두 번 사용하므로 사이클이 아닙니다. 정점 비반복의 단순경로와 단순사이클 정의는 NetworkX 단순경로, 단순사이클의 용어와도 연결됩니다. 라이브러리를 설치할 필요는 없습니다.

간선 A—B, B—C, C—A, A—D만 있는 그래프를 읽어 봅시다.

원문이 간선 비반복을 '기본경로'라고 부른 구분은 여기서 트레일로 명시합니다. 나중에 '경로 복원'이라 부르는 반환 정점 열을 읽을 때도 어떤 반복이 허용되는지 문제의 약속을 확인하세요.

희소 인접 행렬의 0칸 비용

값 대부분이 0인 행렬을 희소 행렬이라고 합니다. 정점 100개, 간선 3개인 단순 무방향 그래프를 0/1 인접 행렬로 저장하면 100×100=10,000칸을 만듭니다. 각 간선은 대칭인 두 칸을 1로 만들므로 1은 6칸이고 나머지 9,994칸, 즉 99.94%가 0입니다. 0이라고 저장 공간이 사라지는 것은 아닙니다.

인접 목록은 정점 100개의 항목과 이웃 항목 6개로 연결을 표현합니다. 그래서 희소 그래프에서 O(V+E) 목록과 O(V²) 행렬의 공간 차이가 커집니다. 이 수치는 논리적인 칸·항목 수이며 Python 객체의 실제 바이트 수와 같다는 뜻은 아닙니다. 행렬의 특정 두 정점 조회는 한 칸이지만 목록은 그 정점의 이웃을 찾는 비용이 있으므로 필요한 연산과 함께 선택합니다. 희소 행렬의 압축 형식·고급 수치 연산은 이 입문 단원의 구현 범위가 아닙니다.

모든 간선을 한 번씩 지나는 오일러 길과 모든 정점을 한 번씩 지나는 길은 다릅니다. 무방향 그래프의 닫힌 오일러 순환은 간선이 있는 정점들이 연결되어 있고 모든 차수가 짝수일 때 가능합니다. 열린 오일러 길은 같은 연결 조건에서 홀수 차수 정점이 정확히 둘입니다. 아래 코드는 순환 가능성만 판정하며 실제 길을 만들지 않습니다. 간선이 없으면 빈 순환을 허용한다고 약속합니다. 이는 검사 함수의 빈 오일러 순환 정책이며, 위에서 정의한 간선을 가진 단순사이클이 존재한다는 뜻은 아닙니다.

손으로 상태 추적하기

분리된 삼각형 두 개도 차수는 모두 2입니다. 그러나 한 순환으로 두 곳의 모든 간선을 지날 수 없어서 연결 검사가 필요합니다.

직접 실행하기

아래 코드는 이 본문만으로 실행할 수 있습니다. lesson.py로 저장하고 첫 장에서 확인한 Python 명령으로 실행하세요.

set()은 중복 없는 집합을 만듭니다. graph.items()는 정점 이름과 이웃 목록을 한 쌍씩 줍니다. vertex in visited는 이미 집합에 있는지 확인합니다. {**triangle, ...}는 기존 딕셔너리 항목을 새 딕셔너리에 펼친 뒤 새 항목을 더하는 표현입니다.

def has_euler_circuit(graph):
    # Contract: simple undirected graph with symmetric neighbor lists.
    active = {v for v, neighbors in graph.items() if neighbors}
    if not active:
        return True
    if any(len(graph[v]) % 2 for v in active):
        return False
    visited, stack = set(), [next(iter(active))]
    while stack:
        vertex = stack.pop()
        if vertex in visited:
            continue
        visited.add(vertex)
        stack.extend(graph[vertex])
    return visited == active

triangle = {"A": ["B", "C"], "B": ["A", "C"], "C": ["A", "B"]}
separated = {**triangle, "D": ["E", "F"], "E": ["D", "F"], "F": ["D", "E"]}
line_graph = {"A": ["B"], "B": ["A", "C"], "C": ["B"]}
print(has_euler_circuit(triangle))
print(has_euler_circuit(separated))
print(has_euler_circuit(line_graph))
assert has_euler_circuit({})
assert has_euler_circuit({"A": []})

실행 결과:

True
False
False

왜 맞고 언제 끝나는가

짝수 차수만으로 충분하다고 판정하지 않고 간선이 있는 정점들을 스택으로 방문합니다. 방문 집합이 그 정점 집합과 같으면 하나의 연결 성분입니다. 단순 무방향·대칭 입력이라는 계약 아래 알려진 오일러 조건을 적용합니다. 스택에는 유한한 이웃만 들어가며 이미 방문한 정점을 재처리하지 않아 종료합니다.

비용과 적용 범위

인접 목록은 정점 V와 간선 E에 O(V+E) 저장 공간을 씁니다. 인접 행렬은 O(V²)이지만 특정 두 정점의 연결을 한 칸에서 확인할 수 있습니다. 순환 판정은 목록 입력에서 O(V+E) 시간입니다. 간선이 매우 적은 큰 그래프는 목록이 자연스럽습니다.

스스로 풀어 보기

1. A—B—C에서 각 차수를 쓰고 열린 오일러 길과 닫힌 순환을 판정하세요.
2. 방향 간선 A→B만 있는 행렬은 대칭인가요?
3. 정점 5개의 단순 무방향 완전 그래프와 모든 순서쌍에 간선을 둔 자기 고리 없는 방향 그래프의 최대 간선 수는 각각 얼마인가요?
4. 간선 P—Q, Q—R, R—P, P—S에서 P,Q,R,P,S와 P,Q,P,S를 보행·단순경로·트레일 기준으로 분류하세요.
5. 정점 200개·간선 20개의 단순 무방향 인접 행렬에서 전체 칸 수, 1의 수, 0의 수를 계산하세요.

힌트

1. 양 끝은 연결이 하나입니다.
2. 반대 방향 간선은 별도입니다.
3. 무방향에서는 두 방향으로 센 같은 간선을 한 번으로 줄입니다.
4. 반복한 정점과 반복한 무방향 간선을 따로 표시하세요.
5. 전체는 V²이고 한 무방향 간선은 두 칸을 1로 만듭니다.

해설

1. 차수는 A=1,B=2,C=1입니다. 연결되어 있고 홀수 정점이 둘이라 열린 길 A→B→C가 가능하지만 닫힌 순환은 아닙니다.
2. 대칭이 아닙니다. 행 A·열 B는 1, 행 B·열 A는 0입니다. 무방향 입력의 대칭 성질을 그대로 옮기면 안 됩니다.
3. 무방향은 5×4/2=10개, 방향은 5×4=20개입니다. 5×5=25개로 세면 제외한 자기 고리 5개까지 포함합니다.
4. 첫 열은 정점 P가 반복되지만 네 간선은 모두 달라 트레일입니다. 전체가 단순경로는 아니며 시작 P와 끝 S가 달라 사이클도 아닙니다. 둘째 열은 P—Q를 왕복해 같은 간선을 두 번 사용하므로 트레일도 아닌 보행입니다.
5. 200²=40,000칸 중 1은 2×20=40칸, 0은 40,000−40=39,960칸입니다. 99.9%가 0이어도 행렬 표현은 그 칸을 보유합니다. 목록 표현은 정점 항목 200개와 이웃 항목 40개를 사용하며 실제 바이트 비교는 객체 표현까지 따로 봐야 합니다.

흔한 오해

그래프의 연결성을 판단할 때 정점이 연결되어 보인다는 그림의 인상만으로는 충분하지 않습니다. 실제 인접 자료를 기준으로 방문 가능한 집합과 간선 방향을 확인하세요.

복습과 다음 연결

다음 절의 스택과 DFS에서는 연결된 영역을 방문합니다. 큐와 BFS는 간선 수가 적은 길도 찾습니다.