<보기>의 방향 그래프에 대해 위상 정렬(topologica… | [7급 서울시 자료구조론] 26년 1회차 기출문제 상세 페이지

1[7급 서울시 자료구조론] 26년 1회차
<보기>의 방향 그래프에 대해 위상 정렬(topological sort)을 수행할 때, 가능한 서로 다른 위상 순서의 총 개수는?
문제 이미지
1
3
2
4
3
5
4
6
해설

가능한 위상 순서는 모두 5가지이다.

그래프의 간선은 A→B, A→C, B→D, C→D, C→E, D→F, E→F이다. 진입 차수가 0인 정점은 A뿐이므로 A가 맨 앞, 모든 경로가 끝나는 F가 맨 뒤에 고정된다.

가운데 B, C, D, E는 D가 B·C 뒤에, E가 C 뒤에 와야 한다. B로 시작하면 B−C−D−E, B−C−E−D의 2가지, C로 시작하면 C−B−D−E, C−B−E−D, C−E−B−D의 3가지가 있어 합은 5가지이다.

  • 3가지는 C로 시작하는 경우만 센 값이다.
  • 4가지는 C−E−B−D처럼 E가 B보다 먼저 오는 순서를 빠뜨린 값이다.
  • 6가지는 가능한 5가지보다 많아, 간선 제약을 어기는 순서를 포함해야만 나오는 값이다.

오류나 개정된 내용이 보이면 알려주세요

이어서 풀어보기

[7급 서울시 자료구조론] 26년 1회차 20문항 이어서 보기문제·정답·해설을 한 페이지에서 이어서 볼 수 있어요7급 서울시 자료구조론 기출문제 암기장 전체 보기