[理工] [軟設]-中正99&100-資工

[love5566188 (I'dont kown)]

100:http://www.cs.ccu.edu.tw/recruit/MasterExam/100software.pdf

9.Finding a topological order,G with vertex set V and edge E,in whtch Q is
  a FIFO quque.

  Algprithm TS

    for each u ∈ V do

       store (  (1)  ) in XX[u];
              ¯¯¯¯
       if xx[u] = 0 then insert u into Q;

    while (Q is not empty)

       u = Extract(Q);

       for each edge (u,v) do

          (  (2)  );
          ¯¯¯¯¯
          if   (3)   theninsert v into Q;
            ¯¯¯¯¯

 (1)~(3)格要怎麼填?

(紅兔在講Topology order時只講原理,不太清楚是怎麼跑的)


99 :http://www.cs.ccu.edu.tw/recruit/MasterExam/99software.pdf


13.Graph G, an edge weight w,a vertex r of G, and Q is a priority queue.

   Algorithm WT(G, w, r)

      for each u ∈ V(G)

         key[u] = ∞;

      Insert all nodes into Q;

      key[r] = 0;

      while (Q is not empty)

          u = ExtractMin(Q);

          for each neighbor v u and v ∈ Q

              if (  (1)  )
                 ¯¯¯¯¯
                 key[V] =  (2) ;
                         ¯¯¯¯
  完成空格(1)和(2)
  (a)The algorithm finds minimum spanning tree.
  (b)The algorithm finds shortest-paths tree.

  我自己寫的:(a)(1)key[u] < key[v]
                (2)key[u]

             (b)(1)key[u] + WT(G,w,r) < key[v]
                (2)key + WT(G,w,r)

   請問這樣對嗎?

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 175.98.50.200
→ xling5216:我不知道要怎麼填第一格~
→ xling5216:但是第一格要填的東西大概是那個點的indegree
→ xling5216:一班來說會說如果你要加入Q的點如果沒有前行節點則加入
→ xling5216:Q裡
→ xling5216:第二格我會填把u輸出 第三格是找看看u所連的點的indegre
→ xling5216:是不是零
→ xling5216:當然第三格是當把u輸出後的狀況所以u所連到的v的
→ xling5216:indegree必須是扣掉(u.v)的狀況
→ xling5216:第二題的話我會寫
→ xling5216:(a)(1)w[u,v]<key[u,v]  (2)w[u,v]
→ xling5216:(b)(1)key[u]+w[u,v]<key[v] (2)key[u]+w[w,v]
→ xling5216:他有給你一個w當所有邊的重量就加減拿來用一下吧XD
→ xling5216:還有你第二題答案(b)小題下去會坐遞迴 會很恐怖喔...
→ xling5216:以上存屬唬爛 如有雷同存屬巧合~
→ WJAider:第二題沒寫，以下第一題:
→ WJAider:(1) number of (x, u) in E for some x in V
→ WJAider:中文: 將所有以 u 結尾的邊個數存入 xx[u]
→ WJAider:(2) output u
→ WJAider:中文: 輸出 u
→ WJAider:(3) (--xx[u] > -1)
→ WJAider:沒中文XD 這是程式語言呢~~
→ WJAider:更正 (3) (--xx[v] == 0)
→ love5566188:我懂了,謝謝兩位大大,我想問xl大(a)(1)
→ love5566188:為甚麼要寫成w[u,v]<k[u,v],而不是w[u,v]<k[v]就好?
→ xling5216:痾!我手殘..是k[v]...抱歉
→ sneak: 輸出 u https://daxiv.com