11-2

1. 1. 그래프의 운행
   • 그래프를 구성하는 모든 정점들을 체계적으로 방문하는 방법
   • 스택을 이용한 깊이 우선 탐색 방법과
   • 대기열을 이용한 넓이 우선 탐색 방법이 있다.
2. 2. 그래프의 응용
   • 최단 경로(shortest path)
     • 단일 점 출발 최단 경로 문제 (single source shortest path problem)
     • 모든 노드 간의 최단 경로 문제 (all pairs shortest path problem)
   • 최소 비용 신장 트리(minimal cost spanning tree)
     • 신장 트리
     • 최소 비용 신장 트리 알고리즘
     • Kruskal의 방법
   • 작업 네트워크의 위상 정렬과 임계 경로