[理工] [資結]-tree and grap

[NOtWorThy (分子小於64)]

a)If undirected grap is connected, there must exist more than one spanning tree.

// why true ?? 若原本圖就是tree,那spanning tree不就不會超過一種嗎??



b)If we use adjacency matrix to reprent the undirected grap, the time of DFS

  and BFS are all O(n*n), n is number of vertex

// 這題不太懂


c)There has more than one topology sort in AOV network

// why false ?? 不是會超過一種嗎??


Which time complexity is O(nlogn)

Delet min in binomial heap           // 不是O(logn)嘛??

Merge two leftist heap as a leftist  // why??

Search a n item in splay tree in amortimed analysis   // why??


煩請高手不吝賜教

感激不盡!!

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 219.70.230.32
推 assassin88:A.有weight才唯一
推 assassin88:B.也不懂= =
→ assassin88:最後一題題目出錯
→ trovadores:用相鄰矩陣實做DFS或BFS時因為要知道與點v相鄰的所有點
推 Astroboy0803:第二題你要先簡略劃個相鄰矩陣，然後從第一頂第一個
→ Astroboy0803:邊找，找到後再往下一個頂點找，依此類推...求完所有
→ trovadores:所以讀相鄰矩陣的第v列(O(n)),總共做n次,所以O(n*n)
→ Astroboy0803:點~求平均的話(1+2+3+..+N-1)*N/N所以就為O(N*N)
→ NOtWorThy:THX 不過第一題好像是ST不是MST 所以我想一條
→ NOtWorThy:simple path v1-v2-...-vn不竟是為一一個AT嗎?
→ NOtWorThy:還有可能超過一條嗎??
推 hahaha86888:第一題FALSE吧...題目說must耶