下列选项中,哪个不可能是下图的广度优先遍历序列( )。
(1) ──→ (2) ──→ (3) │ ╲ ╱ │ ↓ ↘ ↙ ↓ (4) (5) (6) │ ╱ ↑ ╱ │ ↓ ↙ │ ↙ ↓ (7) ──→ (8) ──→ (9)
有向边:1→21 \to 21→2,1→41 \to 41→4,1→51 \to 51→5,2→32 \to 32→3,3→53 \to 53→5,3→63 \to 63→6,4→74 \to 74→7,5→75 \to 75→7,6→86 \to 86→8,6→96 \to 96→9,7→87 \to 87→8,8→58 \to 58→5,8→98 \to 98→9。
1, 2, 4, 5, 3, 7, 6, 8, 9
1, 2, 5, 4, 3, 7, 8, 6, 9
1, 4, 5, 2, 7, 3, 8, 6, 9
1, 5, 4, 2, 7, 3, 8, 6, 9