IT › 컴퓨터 시스템 › 알고리즘

그래프 알고리즘Graph Algorithms

정점과 간선으로 적은 연결 구조 위에서 «다 닿는가 · 한 출발점에서 가장 싼 길은 · 모두를 가장 싸게 잇는 법은»을 푸는 탐색 · 최단 경로 · 최소 신장 트리를 묶은 것이다. 간선을 가중치 순으로 늘어놓는 정렬을 비교 기준 알고리즘으로 함께 다루고, 그래프를 적는 자료 구조 자체는 자료구조가 맡는다.

1요약

  1. 그래프 알고리즘은 알고리즘 가운데 연결 구조 위의 세 질문(다 닿는가 · 가장 싼 길 · 가장 싼 연결)을 맡는 길목으로, 1956 ~ 1959년 최소 신장 트리(Kruskal 1956 · Prim 1957)와 최단 경로(Bellman 1958 · Dijkstra 1959)가 차례로 정리됐고 지금은 라우팅 · 지도 길찾기 · 배선 설계가 이 절차 위에서 돈다.
  2. 질문과 절차를 어긋나게 고르면 답이 틀리거나 비용이 폭발한다 — 사례 그래프에서 간선 수가 가장 적은 길은 비용 10, 가장 싼 길은 9이고, 정점 100만 개 그래프에서 음수 가중치를 허용하는 순간 연산 수가 다익스트라의 약 5만 배가 된다(원문 식 직접 계산 · 그림 5).
  3. 「경로 결과가 이상하다」는 가중치의 유무 · 부호 · 연결 여부로 가른다 — 가중치를 무시했으면 탐색을 쓴 것이고, 음수 간선이 있으면 최단 경로 전제 위반이며, 트리 간선이 정점 수 − 1 보다 적으면 그래프가 끊겨 있다.

2등장 배경

1950년대 전화망 · 송전망 설계자는 도시 수십 곳을 잇는 선로 조합이 너무 많아 하나씩 비교할 수 없었다. Kruskal 은 1956년 가장 짧은 간선부터 고리를 만들지 않게 고르는 방법을(Kruskal 1956), Prim 은 1957년 벨 연구소 논문에서 한 점에서 나무를 키우는 방법을 냈다(Prim 1957).

최단 경로는 같은 시기 수송 · 통신 경로 문제에서 나왔다. Bellman 은 1958년 동적 계획법으로 경로 문제를 풀었고(Bellman 1958), Dijkstra 는 1959년 세 쪽 논문 하나에 최소 신장 트리와 두 점 사이 최단 경로를 함께 실었다(Dijkstra 1959). Tarjan 은 1972년 깊이 우선 탐색 하나로 연결 성분 같은 문제를 선형 시간에 푸는 틀을 세웠다(Tarjan 1972).

지금은 이 절차들이 교과서 · 오픈소스 라이브러리에 정리되어 있어(NetworkX minimum_spanning_tree) 새로 짜는 일은 드물다. 실무의 일은 질문에 맞는 절차를 고르고 그 전제(가중치 부호 · 연결)를 지키는 것이다.

3쉽게 이해하기 — 다섯 섬을 맡은 군청 주무관

섬 다섯 개를 맡은 군청의 한 주무관은 섬 · 뱃길 지도 한 장으로 세 가지 일을 한다. 태풍 경보는 배 한 번에 닿는 섬부터 차례로 돌리고, 구급선은 운항 시간이 가장 짧은 뱃길로 보낸다. 섬을 모두 잇는 다리 공사는 견적서를 싼 순으로 쌓아 두고 위부터 승인하되, 이미 이어진 섬끼리 잇는 다리는 반려한다.

한 주무관 질문을 보고 절차를 고른다 알고리즘 선택 섬 · 뱃길 지도 그래프(정점 · 간선) 1 경보 돌리기 배 한 번에 닿는 섬부터 그래프 탐색 2 구급선 뱃길 운항 시간 합이 가장 짧게 최단 경로 3 다리 공사 모든 섬을 잇되 공사비 합 최소 최소 신장 트리 4 견적서 더미 공사비가 싼 순으로 쌓음 정렬 위부터 넘김

그림 1 · 같은 섬 지도 한 장으로 주무관이 세 가지 다른 질문을 풀며, 다리 공사는 싼 순으로 쌓은 견적서(정렬)를 받아 쓴다.

경보 돌리기한 번에 닿는 섬부터
구급선시간 합이 가장 짧은 뱃길
견적서 쌓기공사비 싼 순으로
다리 승인이미 이어진 섬이면 반려
공사 끝다리 수 = 섬 수 − 1
정렬 — 싼 순 견적서 더미 최소 신장 트리 — 위부터 승인 · 반려 솔섬–달섬 2억 본섬–솔섬 3억 본섬–달섬 4억 달섬–별섬 5억 본섬–별섬 7억 승인솔섬 · 달섬이 처음 이어짐 승인본섬이 솔섬 쪽에 붙음 반려본섬 · 달섬은 이미 이어짐(고리) 승인별섬까지 이어져 섬 4 · 다리 3 반려이미 모두 이어짐 — 볼 필요 없음 다리 3개(섬 4 − 1) · 공사비 합 2 + 3 + 5 = 10억 더미를 만드는 일과 위부터 고르는 일은 따로다 — 더미가 싼 순이 아니면 승인 결과가 최소가 아니다

그림 2 · 견적서를 싼 순으로 쌓는 일(정렬)과 위부터 승인 · 반려하는 일(최소 신장 트리)의 경계 — 정렬이 끝나면 다리 공사는 «이미 이어졌나»만 묻는다.

비유 속 역할실제 이름실제로 하는 일
섬 · 뱃길 지도그래프(정점 · 간선 · 가중치)연결과 비용을 인접 리스트 · 인접 행렬로 적는다
한 주무관질문별 절차 선택다 닿기 · 싼 길 · 싼 연결 중 무엇을 묻는지 보고 고른다
경보 돌리기그래프 탐색(BFS)출발점에서 간선 수가 적은 정점부터 큐로 방문한다
한 뱃길 끝까지 따라가기그래프 탐색(DFS)갈 수 있는 데까지 들어갔다 되돌아오며 연결 성분을 가른다
구급선 뱃길최단 경로(다익스트라)한 출발점에서 가중치 합이 가장 작은 경로를 정점마다 확정한다
시간이 줄어드는 뱃길음수 가중치(벨만-포드)모든 간선을 V − 1 번 완화하고 음수 사이클을 검사한다
싼 순 견적서 더미정렬간선을 가중치 순으로 늘어놓는다(비교 정렬 하한 N lg N)
다리 승인 · 반려최소 신장 트리(크루스칼)고리를 만들지 않는 가장 싼 간선을 정점 수 − 1 개까지 고른다

⚠ 비유가 맞지 않는 곳: 실제 뱃길 시간은 날씨에 따라 바뀌지만 이 절차들은 가중치를 고정 값으로 받는다. 다리는 양쪽으로 건너지만 그래프에는 한 방향만 가는 간선(방향 그래프)도 있고, 그 경우 최소 신장 트리는 따로 정의된다.

4구조 — 세 질문과 공통 입력

아래 토픽 넷은 같은 입력(그래프 표현) 위에서 서로 다른 질문을 맡는다. 탐색은 가중치 없이 «닿는가 · 몇 간선 만에», 최단 경로는 한 출발점 기준 «가장 싼 길», 최소 신장 트리는 출발점 없이 «전체를 가장 싸게»를 묻고, 정렬은 크루스칼에 간선 순서를 넘긴다.

질문별 알고리즘 위 = 무엇을 묻나 · 아래 = 공통 입력 정렬 비교 하한 N lg N 간선을 가중치 순으로 그래프 탐색 BFS · DFS · 가중치 없음 결과 = 방문 순서 · 간선 수 V + E 최단 경로 다익스트라 · 벨만-포드 결과 = 출발점 기준 트리 E log V · E V 최소 신장 트리 크루스칼 · 프림 결과 = 출발점 없는 트리 E log E · E log V 가중치 전체 그래프 표현(자료구조) 인접 리스트 = 항목 V + E개 · 인접 행렬 = 셀 V²개 · 가중치 = 간선마다 값 하나

그림 3 · 세 질문은 같은 그래프 표현을 입력으로 받고, 가중치를 더하면 탐색이 최단 경로로, 출발점을 지우고 전체 연결을 물으면 최소 신장 트리로 넘어가며, 정렬은 크루스칼의 첫 단계가 된다.

아래 토픽묻는 질문입력 전제결과 모양비용(근거)
그래프 탐색(BFS · DFS)닿는가 · 몇 간선 만에가중치 없음방문 순서 · BFS 트리V + E(Sedgewick · Wayne 4.1)
최단 경로(다익스트라 · 벨만-포드)한 출발점에서 가장 싼 길다익스트라 = 0 이상 · 벨만-포드 = 음수 사이클 없음최단 경로 트리E log V · E V(Sedgewick · Wayne 4.4)
최소 신장 트리(MST)모든 정점을 가장 싸게무방향 · 연결간선 V − 1 개E log E(Sedgewick · Wayne 4.3)
정렬간선을 가중치 순으로비교 가능한 키정렬된 간선 목록하한 lg(N!) ~ N lg N(Sedgewick · Wayne 2.2)

정렬은 그래프 알고리즘에서 «비교 기준»이다. 크루스칼의 E log E 는 간선 정렬 몫이 정하므로, 다른 그래프 알고리즘의 비용을 «정렬 한 번보다 싼가 비싼가»로 견줄 수 있다.

🔑 같은 그래프라도 «출발점이 있는 질문»은 최단 경로 트리를, «출발점이 없는 질문»은 최소 신장 트리를 내고, 두 트리는 일반적으로 다르다.

5동작 — 다섯 정점 그래프에 세 질문 던지기

설명용 가정 값 = 무방향 그래프 정점 5(S · A · B · C · D) · 간선 7(S–A 5 · S–B 3 · A–B 1 · A–C 2 · B–D 6 · C–D 4 · S–D 10 · 가중치 서로 다름).

  1. 인접 리스트로 저장한다 — 무방향 간선은 양 끝에 한 번씩 적어 목록 항목 14개 + 정점 5 = 19개이고, 인접 행렬이면 셀 25개다.
  2. S 에서 BFS 를 돌린다 — 큐에서 A · B · D 가 1간선, C 가 2간선(A 경유)으로 나온다. D 는 S–D 직항 1간선이지만 비용은 10이다(Sedgewick · Wayne 4.1).
  3. S 에서 다익스트라를 돌린다 — 확정 순서 S 0 → B 3 → A 4(S–A 5 보다 S–B–A 4) → C 6 → D 9(S–D 10 보다 S–B–D 9)(NIST DADS Dijkstra).
  4. 두 결과를 견준다 — S→D 가 BFS 로는 간선 1개 · 비용 10, 다익스트라로는 간선 2개 · 비용 9다.
  5. 간선 7개를 가중치 순으로 정렬한다 — A–B 1 · A–C 2 · S–B 3 · C–D 4 · S–A 5 · B–D 6 · S–D 10.
  6. 크루스칼로 앞에서부터 고른다 — A–B · A–C · S–B · C–D 를 채택하고 간선 4개(= 정점 5 − 1)에서 멈춘다. 합은 10이고 S–A · B–D · S–D 는 고리가 되어 버린다(NIST DADS Kruskal).
  7. 두 트리를 견준다 — 최단 경로 트리(S–B · B–A · A–C · B–D)는 합 12, 최소 신장 트리는 합 10이다. 최소 신장 트리 안에서 S→D 는 S–B–A–C–D 로 10이라 최단 9 보다 비싸다.
2 BFS — 간선 수 53 12 64 10 S A C B D S→D 간선 1 · 비용 10 3 다익스트라 — S 기준 비용 53 12 64 10 S A C B D 04 63 9 트리 합 12 · S→D 9 6 크루스칼 — 전체 합 53 12 64 10 S A C B D 트리 합 10 · S→D 10 굵은 선 = 고른 트리 간선 · 가는 선 = 버린 간선 · 가운데 굵은 숫자 = S 에서의 최단 비용

그림 4 · 같은 그래프에서 BFS 트리는 간선 수를, 최단 경로 트리는 S 기준 비용을, 최소 신장 트리는 전체 합을 줄이며, S→D 비용은 10 · 9 · 10 으로 갈린다.

🔑 «간선 수가 가장 적은 길», «한 점에서 가장 싼 길», «전체가 가장 싼 연결»은 세 다른 답이다 — 질문을 먼저 정하지 않으면 맞는 절차도 틀린 답을 낸다.

알고리즘 사이 비용 차이는 전제에서 나온다. 같은 그래프에서 가중치 조건을 약하게 할수록 쓸 수 있는 절차가 바뀌고 연산 수가 차수 단위로 뛴다.

설명용 가정 값 V = 10^6 · E = 3 × 10^6 · 초당 1억 번 가중치 없음 — BFS 4 × 10^6 · 0.04초 0 이상 — 다익스트라 6.0 × 10^7 · 0.6초 전체 연결 — 크루스칼 6.5 × 10^7 · 0.65초(정렬 몫) 음수 허용 — 벨만-포드 3 × 10^12 · 약 8.3시간 10^6 10^8 10^10 10^12 막대 = 연산 수(로그 눈금) · 식 = V + E · E log2 V · E log2 E · V × E(Sedgewick · Wayne 4.1 · 4.3 · 4.4)

그림 5 · 정점 100만 · 간선 300만 그래프에서 가중치가 없으면 약 400만 번, 0 이상이면 약 6,000만 번, 음수를 허용하면 3조 번으로 — 전제 하나가 연산 수를 5만 배 가른다.

🔑 음수 간선 하나가 다익스트라의 «꺼낸 정점은 다시 줄지 않는다»는 전제를 깨고, 그 대가로 모든 간선을 V − 1 번 다시 보는 벨만-포드 비용을 낸다.

6비교 — 관련 기술과의 경계

기술맡는 일경계넘기는 곳확인 자료
그래프 알고리즘탐색 · 최단 경로 · MST · 정렬그래프가 주어진 뒤의 절차그래프 저장 방식 → 자료구조정점 · 간선 수 · 가중치 범위
자료구조그래프 · 힙 · 스택 · 큐 · 해시 테이블넣기 · 빼기 · 찾기 한 번의 비용힙을 쓰는 다익스트라 → 그래프 알고리즘연산별 비용
알고리즘 설계 기법분할 정복 · 동적 계획법 · 그리디 · A*절차를 세우는 방식그리디 = 크루스칼 · 동적 계획법 = 벨만-포드 → 그래프 알고리즘최적해 보장 조건
알고리즘 분석(계산 복잡도)Big-O · P · NP비용을 재는 잣대다항 시간 그래프 문제의 절차 → 그래프 알고리즘증가 차수
라우팅 프로토콜OSPF · BGP 같은 경로 교환 규약경로 정보를 장비끼리 주고받는 방식각 장비 안의 최단 경로 계산 = 그래프 알고리즘의 절차라우팅 표
그래프 신경망(GNN)그래프 데이터로 표현 학습데이터로 맞춘 모델이웃 방문 순서 = 탐색 · 정답이 정해진 계산 = 그래프 알고리즘검증 오차

분석그래프가 주어지고 답이 하나로 정해지는 질문(닿는가 · 가장 싼 길 · 가장 싼 연결)은 그래프 알고리즘에서, 그래프를 어떻게 저장하느냐는 자료구조에서, 비용 차수 자체는 알고리즘 분석에서 본다. 근거는 표의 「경계」 열 — 같은 다익스트라라도 힙 연산 비용은 자료구조가 다루고 «가중치 0 이상» 전제는 그래프 알고리즘이 다룬다(NIST DADS Dijkstra).

7실무 진단 — 경로 결과가 이상할 때 하위 토픽 가르기

분석먼저 그래프가 끊겼는지와 가중치 부호를 보고, 그다음 고른 절차가 질문과 맞는지를 본다. 입력 전제가 깨진 상태에서는 어떤 절차도 맞는 답을 주지 않기 때문이다(NetworkX number_connected_components · NIST DADS Bellman-Ford).

#증상의심 원인하위 토픽확인 명령(NetworkX 3.7)판정 기준(근거)
1MST 간선 수가 V − 1 보다 적음그래프가 끊김 → 신장 숲그래프 탐색 · MSTnx.number_connected_components(G)1 보다 크면 성분마다 트리(NetworkX minimum_spanning_tree)
2최단 경로 비용이 손 계산과 다름음수 간선 · 음수 사이클최단 경로nx.negative_edge_cycle(G) · 가중치 최솟값True 면 최단 경로 정의 불가 · 음수만 있으면 벨만-포드(NIST DADS Bellman-Ford)
3경로가 간선 수만 적고 비쌈가중치 속성 누락 · 이름 틀림그래프 탐색 · 최단 경로G.edges(data=True) 로 weight 키 확인키가 없으면 가중치 1 로 처리되어 BFS 와 같은 답(NetworkX minimum_spanning_tree)
4같은 입력인데 MST 가 실행마다 다름같은 가중치 간선MST · 정렬가중치 중복 수 세기중복이 있으면 MST 가 하나가 아닐 수 있음 · 합은 같음(Sedgewick · Wayne 4.3)

1 · 2행은 입력 전제 문제라 3 · 4행보다 먼저 본다. 4행은 오류가 아니라 정렬의 동률 처리 차이이므로 합을 먼저 비교한다.

8시험 대비

시험에서는 다익스트라와 벨만-포드, 크루스칼과 프림을 견주는 비교형, 그리고 작은 그래프에 절차를 적용해 단계별 표를 쓰게 하는 동작 · 절차 설명형으로 나올 수 있다. 어느 쪽이든 «질문 → 전제 → 절차 → 비용» 순서로 쓰면 비교 축이 저절로 생긴다.

답안 목차
  1. 개요 — 정점 · 간선 · 가중치로 적은 연결 구조 · 세 질문(탐색 · 최단 경로 · MST) · 1956 ~ 1959 원 논문
  2. 구성 — 그림 3 질문별 알고리즘 + 아래 토픽 표(전제 · 결과 모양 · 비용)
  3. 절차 — 그림 4 다섯 정점 사례(BFS 간선 수 · 다익스트라 확정 순서 · 크루스칼 채택 · 고리 제외)
  4. 비교 — 다익스트라 · 벨만-포드(음수 가중치 · E log V ↔ E V) · 크루스칼 · 프림(간선 정렬 ↔ 정점에서 확장)
  5. 핵심 원리 — 그림 5 전제별 연산 수(가중치 없음 · 0 이상 · 음수 허용)
  6. 적용 — 라우팅 경로 계산 · 배선 · 망 설계의 최소 연결

꼭 쓸 키워드
인접 리스트BFSDFS완화다익스트라벨만-포드음수 사이클절단 성질크루스칼프림

다른 답안과 차이를 내는 한 가지는 그림 4 처럼 같은 그래프에서 최단 경로 트리(합 12)와 최소 신장 트리(합 10)가 다르게 나오는 것을 수치로 보이는 것이다.

9오해와 사실

  • 오해최소 신장 트리 안의 경로가 곧 최단 경로다.
    사실최소 신장 트리는 전체 합을 줄일 뿐 출발점이 없어, 사례에서 S→D 가 트리 안에서는 10, 최단으로는 9다(Sedgewick · Wayne 4.3).
  • 오해다익스트라는 음수 가중치가 몇 개 있어도 대체로 맞는다.
    사실정점을 꺼낼 때 확정하는 방식은 가중치 0 이상을 전제로 하며 음수 간선에서 틀린 답을 낼 수 있다(NIST DADS Dijkstra · Sedgewick · Wayne 4.4).
  • 오해BFS 는 가중치가 없을 때만 쓰는 낡은 방법이다.
    사실가중치가 모두 같으면 BFS 가 간선 수 기준 최단 경로를 V + E 시간에 주며 다익스트라보다 싸다(Sedgewick · Wayne 4.1).

10핵심 정리

하위 토픽질문전제결과비용쓰는 곳
BFS몇 간선 만에 닿나가중치 없음 · 같음간선 수 최단 트리V + E홉 수 · 전파 범위
DFS어디까지 이어졌나없음방문 · 종료 순서V + E연결 성분 · 사이클 검사
다익스트라한 점에서 가장 싼 길가중치 0 이상최단 경로 트리E log V지도 길찾기 · 링크 상태 라우팅
벨만-포드음수가 있어도 가장 싼 길음수 사이클 없음최단 경로 트리 · 사이클 판정E V음수 비용 · 거리 벡터
크루스칼 · 프림전체를 가장 싸게무방향 · 연결간선 V − 1 개E log E · E log V배선 · 망 설계
정렬간선 순서 맞추기비교 가능한 키정렬된 간선하한 N lg N크루스칼 첫 단계 · 비교 기준

11참고 문헌

  1. 먼저 볼 문헌
  2. ★ Algorithms 4th Edition (Sedgewick · Wayne) 4.1 Undirected Graphs — BFS · DFS 가 V + E 에 비례하는 시간에 끝나고 BFS 가 «간선 수가 가장 적은 경로»를 주는 근거를 볼 때
    Princeton University · 2026-11 · algs4.cs.princeton.edu/41graph/ · 확인 2026-11-14
  3. ★ Algorithms 4th Edition (Sedgewick · Wayne) 4.4 Shortest Paths — 다익스트라(E log V) · 벨만-포드(E V) · 비순환 그래프(E + V)의 전제와 비용을 나란히 볼 때
    Princeton University · 2026-11 · algs4.cs.princeton.edu/44sp/ · 확인 2026-11-14
  4. ★ Algorithms 4th Edition (Sedgewick · Wayne) 4.3 Minimum Spanning Trees — 절단 성질 · 같은 가중치일 때 MST 가 하나가 아닐 수 있다는 점 · 크루스칼 E log E 를 볼 때
    Princeton University · 2026-11 · algs4.cs.princeton.edu/43mst/ · 확인 2026-11-14
  5. ★ Dictionary of Algorithms and Data Structures - Bellman-Ford algorithm — V − 1 번 완화 뒤 한 번 더 돌려 음수 사이클을 찾는 절차를 볼 때
    NIST · 2019-02 · xlinux.nist.gov/dads/HTML/bellmanford.html · 확인 2026-11-14
  6. ★ NetworkX 3.7 documentation - minimum_spanning_tree — 끊긴 그래프에서 신장 숲이 나오는 것 · 가중치 속성이 없을 때 1 로 보는 것을 확인할 때
    NetworkX Developers · 2026-11 · networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.tree.mst.minimum_spanning_tree.html · 확인 2026-11-14
  7. 본문 근거
  8. Algorithms 4th Edition (Sedgewick · Wayne) 2.2 Mergesort - compare-based sorting lower bound — Princeton University · 2026-11 · algs4.cs.princeton.edu/22mergesort/ · 확인 2026-11-14
  9. Dictionary of Algorithms and Data Structures - Dijkstra's algorithm — NIST · 2024-05 · xlinux.nist.gov/dads/HTML/dijkstraalgo.html · 확인 2026-11-14
  10. Dictionary of Algorithms and Data Structures - Kruskal's algorithm — NIST · 2024-08 · xlinux.nist.gov/dads/HTML/kruskalsalgo.html · 확인 2026-11-14
  11. Dictionary of Algorithms and Data Structures - minimum spanning tree — NIST · 2022-07 · xlinux.nist.gov/dads/HTML/minimumSpanningTree.html · 확인 2026-11-14
  12. Dictionary of Algorithms and Data Structures - breadth-first search — NIST · 2019-04 · xlinux.nist.gov/dads/HTML/breadthfirst.html · 확인 2026-11-14
  13. Dictionary of Algorithms and Data Structures - depth-first search — NIST · 2021-10 · xlinux.nist.gov/dads/HTML/depthfirst.html · 확인 2026-11-14
  14. NetworkX 3.7 documentation - negative_edge_cycle — NetworkX Developers · 2026-11 · networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.shortest_paths.weighted.negative_edge_cycle.html · 확인 2026-11-14
  15. NetworkX 3.7 documentation - number_connected_components — NetworkX Developers · 2026-11 · networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.components.number_connected_components.html · 확인 2026-11-14
  16. Kruskal 1956 On the shortest spanning subtree of a graph and the traveling salesman problem (Proceedings of the AMS 7(1) · 48-50) — American Mathematical Society · 1956-02 · doi.org/10.1090/S0002-9939-1956-0078686-7 · 확인 2026-11-14
  17. Prim 1957 Shortest Connection Networks And Some Generalizations (Bell System Technical Journal 36(6) · 1389-1401) — AT&T · IEEE · 1957-11 · doi.org/10.1002/j.1538-7305.1957.tb01515.x · 확인 2026-11-14
  18. Bellman 1958 On a routing problem (Quarterly of Applied Mathematics 16(1) · 87-90) — American Mathematical Society · 1958-04 · doi.org/10.1090/qam/102435 · 확인 2026-11-14
  19. A Note on Two Problems in Connexion with Graphs (E. W. Dijkstra · Numerische Mathematik 1 · 269-271) — Springer · EuDML 기록 · 1959-12 · eudml.org/doc/131436 · 확인 2026-11-14
  20. Tarjan 1972 Depth-First Search and Linear Graph Algorithms (SIAM Journal on Computing 1(2) · 146-160) — SIAM · 1972-06 · doi.org/10.1137/0201010 · 확인 2026-11-14