다음 그래프의 위상 정렬(topological sorting) 결과로 … | [7급 국가직 자료구조론] 16년 1회차 기출문제 상세 페이지

1[7급 국가직 자료구조론] 16년 1회차
다음 그래프의 위상 정렬(topological sorting) 결과로 나올 수 있는 위상 순서(topological order)로 옳지 않은 것은?
문제 이미지
1
A, B, C, D, E, F
2
C, A, B, E, D, F
3
A, C, B, E, D, F
4
C, A, D, B, E, F
해설

위상 순서로 옳지 않은 것은 C, A, D, B, E, F이다.

그래프의 간선은 A→B, B→D, B→E, B→F, C→D, C→E, E→F이다. 위상 순서는 모든 간선 u→v에 대해 u가 v보다 앞서야 하는데, 이 순서는 B→D 간선이 있음에도 D가 B보다 먼저 나온다.

  • A, B, C, D, E, F: 모든 간선의 선후 관계를 만족한다.
  • C, A, B, E, D, F: 진입 차수가 0인 C, A가 먼저 오고 B 다음에 E, D, 마지막에 F가 와 모든 조건을 만족한다.
  • A, C, B, E, D, F: A→B, C→D, C→E, B→D, B→E, E→F 조건을 모두 만족한다.

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

이어서 풀어보기

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