Q6.Graphs, Greedy and NP-Hard.
        1.對一 graph 作 pre-order traversal.
          課本沒有好例子，畫的不好請見諒。
        ex.

    出發點 →   a------------d
               / \          / \
              b   c---e    /   \
               \ / \      /     \
                f---g----/       h

          經過的原則是：走過的路盡量別再走，除非走到死巷子。
          從a出發，依序經過：a → b → f → c → e → c → g → d → h
                                            ^^^^^^^^^^^^
                                           遇到死路所以退回

          pre-order就是把「遇到的東西output出來，但是不重複」
          所以這個case的 Output：a b f c e g d h

        2.對一 graph 作 post-order traversal.
        ex.

    出發點 →   a------------d
               / \          / \
              b   c---e    /   \
               \ / \      /     \
                f---g----/       h


          經過的原則一樣是：走過的路盡量別再走，除非走到死巷子。
          從a出發，依序經過：a → b → f → c → e → c → g → d → h
                                            ^^^^^^^^^^^^
                                           遇到死路所以退回
          我們將遇到的東西依順序擺入暫存器，如果有遇到死路退回的，
          就優先丟到output(並非先output出來)。
                                        a
                             h          b
                             d          f     左列是暫存器，
           e                 g          c     右列是output，最上面的最先output
           c        c        c          g
           f    →  f    →  f    →    d
           b        b        b          h
           a        a  e     a  e       e
           ----     ----     ----    ----
           ^^^^^^^^^^^^^     ^^^^
遇到死路退回，先將e丟到右列     全部都跑完了暫存，就由上依序丟到右列

           從下面開始輸出，所以這個Output是e h d g c f b a (有更正)

        3.針對Graph作Dijkstra's演算法的流程圖，課本裡有。
        Ans.這個用打的可能打到死大家還是看不懂= =，自己看課本p.350 ~ p.360



--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.45.109.75
※ 編輯: y90633          來自: 114.45.109.75        (01/06 16:18)
※ 編輯: y90633          來自: 114.45.106.48        (01/08 20:04)
※ 編輯: y90633          來自: 114.45.106.48        (01/08 22:45)