作者dinex ()
看板Prob_Solve
标题[问题] DFS建特定条件下的Edge
时间Fri Jul 1 23:40:46 2016
大大们好 第一次来本版发言 若有冒犯之处敬请见谅
最近需要制作DFS所需要的Graph。Graph中每个node的位置平均分配如下图所示的各种颜色区块的边界(p.s边界只有水平与垂直两种方向)
http://imgur.com/0uEts8u
现在要建立任两node之间的edge。其中edge只能出现在单一颜色区块内
（所以红线标示的就是错误的edge，黑色才是正确的）。想请问要怎麽做才能建立出正确的edge？先谢谢大家帮忙了！
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 175.180.243.195
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1467387649.A.7DE.html
※ 编辑: dinex (175.180.243.195), 07/01/2016 23:42:45
1F：→ yr: 这问题跟 DFS 无关，提 DFS 是多余的 :p07/02 09:59
2F：→ yr: 色块区域定义好以後，检查一个 edge 是否通过两个以上的区块即07/02 10:01
那如果不考虑用另外的资料结构去存原本图形吗？
目前每个node有存本身的绝对位置与跟哪些区域相邻 不知道这样可不可以直接判断？
※ 编辑: dinex (112.104.141.232), 07/02/2016 23:43:15
3F：→ yr: 看你的 edges 是不是都是从你的 nodes 构成，照你的图 07/04 11:37
4F：→ yr: 看起来只要检查是不是你要新增的 edge 是不是跟区块的边有交叉 07/04 11:38