다음은 방향성 그래프(directed graph)를 인접행렬로 표현한 … | [7급 국가직 자료구조론] 13년 1회차 기출문제 상세 페이지

1[7급 국가직 자료구조론] 13년 1회차
다음은 방향성 그래프(directed graph)를 인접행렬로 표현한 것이다. 이에 대한 위상 정렬(topological sorting)의 결과로 옳은 것은? (단, 행(row)은 출발 노드로 열(column)은 도착 노드로 매핑된다)
abcdef
a11
b11
c11
d1
e11
f
1
a, b, c, d, e, f
2
a, b, c, e, d, f
3
a, c, b, e, d, f
4
a, c, e, b, d, f
해설

위상 정렬 결과는 a, b, c, e, d, f이다.

간선은 a→b, a→c, b→c, b→d, c→d, c→e, d→f, e→d, e→f이다. 진입차수가 0인 노드를 차례로 꺼내면 a → b → c → e → d → f로 순서가 하나로 정해진다.

  • a, b, c, d, e, f: e→d 간선이 있어 d가 e보다 앞설 수 없다.
  • a, c, b, e, d, f: b→c 간선이 있어 c가 b보다 앞설 수 없다.
  • a, c, e, b, d, f: 역시 c가 b보다 먼저 나와 b→c 간선을 어긴다.

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

이어서 풀어보기

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