무방향 그래프

탐색

DFS(Depth-first search)

BFS(Breadth-first search)

• 단일 원점 최단 경로

  어떤 그래프와 원점 s가 주어졌을때, 그정점에서 다른 정점 v로 가는 경로가 존재하는가? 그렇다면 그 경로들 중 가장 짧은 경로는 무엇인가?

• 연결 컴포넌트

응용

분리 차수(Degrees of separation)

몇 사람 건너 아는 사람인가?

방향 그래프

정점과 방향을 가진 간선의 집합. 각각의 방향 간 선은 순서를 가진 두 정점 쌍을 연결

방향 그래프의 `도달성`과 무방향 그래프의 `연결성`을 구분해야 한다. 방향 그래프에서 두 정점 간 경로가 존재하는지 알아내는 것은 쉽지 않다.

도달성

복수 원점 도달성

주어진 방향 그래프와 원점의 집합에 대해, 주어진 정점 v로의 방향 경로가 존재하는 원점이 하나라도 있는가?

• garbage collection

  정점은 객체, 간선은 그 객체에 대한 참조를 나타내는 방향 그래프로 자바 프로그램의 런타임 메모리 사용 상태를 나타낼 수 있음. `표시하고 훑기` 전략은 비트 하나를 표시용으로 남겨두고, 객체를 정점으로 하는 방향 그래프에 대해 주기적으로 DFS와 같은 알고리즘을 수해해 잠재적으로 참조될 수 있는 객체를 표시. 전체 객체들을 훑어 표시되지 않은 객체들(garbage)를 메모리 재활용을 위해 수집함.

순환과 비순환 방향 그래프(Directed Acyclic Graph, DAG)

스케줄링 문제

작업 스케줄링은 어떤 작업들의 집합과 제약 조건의 집합이 있을 때 제약 조건들을 만족시키도록 작업을 배치하는 문제

• 선행 제약 스케줄링

• 위상 정렬

  어떤 방향 그래프가 주어졌을 때, 모든 정점들이 간선이 가리키는 방향으로만 나열되도록. 즉, 뒤에 있는 정점이 앞에 있는 정점 방향으로 간선이 연결되는 경우가 없도록 정렬 또는 그것이 불가능함을 확인.