作者jay2115 (明早打老虎)
看板Grad-ProbAsk
標題[理工] 成大 資演
時間Wed Jan 15 15:20:01 2020
各位大神請問一下graph中的BFS
有辦法產生哪些edge?
例如：
back edge 在無向圖的情況下好像就無法產生
但是在有向圖的情況下好像又可以產生
所以小弟最近寫到成大一些題目時就不太確定答案 求各位大神解答
例如：106成大電通 選擇1（問是否True)
(c).There may exist back edges in a spanning tree generated by a breath-first
algorithm.就不確定要不要選
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 223.141.139.68 (臺灣)
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1579072803.A.689.html
1F：推 zuchang: 無向圖還要多判斷父點 才能判斷back edge01/15 15:31
2F：→ zuchang: 看成DFS 抱歉QQ01/15 15:31
3F：→ zuchang: 不對 等等 bfs會分邊的種類嗎OAO01/15 15:33
因為有寫到問BFS的題目所以才上來問QAQ
※ 編輯: jay2115 (223.141.139.68 臺灣), 01/15/2020 15:50:45
4F：推 mistel: 相信自己 01/15 16:03
5F：→ ching4562: 我認為應該存在但BFS不會去討論 01/15 16:42
6F：→ Kedge: bfs似乎不太會去討論邊的種類？不過如果直接把dfs對back ed 01/18 02:46
7F：→ Kedge: ge的定義套用在bfs上(v.color=gray)，可以發現spanning tre 01/18 02:46
8F：→ Kedge: e是不含back edge的，所以這題我認為是false 01/18 02:46