[理工] 成大 資演

[jay2115 (明早打老虎)]

各位大神請問一下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://www.ptt.cc/bbs/Grad-ProbAsk/M.1579072803.A.689.html
推 zuchang: 無向圖還要多判斷父點 才能判斷back edge
→ zuchang: 看成DFS 抱歉QQ
→ zuchang: 不對 等等 bfs會分邊的種類嗎OAO
因為有寫到問BFS的題目所以才上來問QAQ
※ 編輯: jay2115 (223.141.139.68 臺灣), 01/15/2020 15:50:45
推 mistel: 相信自己
→ ching4562: 我認為應該存在但BFS不會去討論
→ Kedge: bfs似乎不太會去討論邊的種類？不過如果直接把dfs對back ed
→ Kedge: ge的定義套用在bfs上(v.color=gray)，可以發現spanning tre
→ Kedge: e是不含back edge的，所以這題我認為是false