인접 행렬로 표현된 방향 그래프 중 위상 정렬이 불가능한 것은? | [7급 국가직 자료구조론] 25년 1회차 기출문제 상세 페이지

3행 1열이 1인 행렬은 1→2→3→1의 사이클을 포함하므로 위상 정렬이 불가능하다.
위상 정렬은 사이클이 없는 방향 그래프에서만 가능하다. 행 i, 열 j의 1을 간선 i→j로 읽을 때 대각선 아래가 모두 0인 상삼각 행렬은 번호가 큰 정점에서 작은 정점으로 가는 간선이 없어 사이클이 생기지 않는다.
1→2→3→4의 한 줄 경로 행렬: 상삼각이므로 1, 2, 3, 4 순으로 정렬된다.
1과 2가 각각 3, 4로, 3이 4로 가는 행렬: 상삼각이므로 위상 정렬이 가능하다.
번호가 작은 정점에서 큰 정점으로 모든 간선이 있는 행렬: 상삼각이므로 위상 정렬이 가능하다.