방향그래프의 행(row)은 출발 노드로 열(column)은 도착 노드로… | [7급 국가직 자료구조론] 12년 1회차 기출문제 상세 페이지

1[7급 국가직 자료구조론] 12년 1회차
방향그래프의 행(row)은 출발 노드로 열(column)은 도착 노드로 매핑하여 다음과 같이 인접행렬로 표현될 때, 위상 정렬(topological sort)이 가능한 것은?
1
abcdef
a11
b11
c11
d11
e11
f
2
abcdef
a11
b11
c11
d1
e111
f
3
abcdef
a11
b11
c11
d1
e11
f
4
abcdef
a11
b11
c11
d1
e11
f1
해설

위상 정렬은 사이클이 없는 방향그래프(DAG)에서만 가능하므로, 사이클이 없는 인접행렬을 고르면 된다.

d에서 c로, e에서 b로, f에서 a로 되돌아가는 간선 없이 d→f, e→d, e→f 만 있는 행렬은 사이클이 없으며, a, b, c, e, d, f 순으로 위상 정렬된다.

  • d→c 간선이 있는 행렬은 c→d와 함께 c→d→c 사이클이 생긴다.
  • e→b 간선이 있는 행렬은 b→c→e→b 사이클이 생긴다.
  • f→a 간선이 있는 행렬은 a→b→d→f→a 사이클이 생긴다.

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

이어서 풀어보기

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