作者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/cn.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