Pra*_*han 5 algorithm optimization graph-theory
我的意思是"非常大的图形"是每个顶点有1000个相邻的顶点,但如果你去看最终的解决方案,从A到B的距离只有6(比方说).
在这种情况下,使用基本的BFS算法将是浪费,因为它放置所有1000个A的相邻顶点,然后在下一轮1000中的每一个等等.按时间到达BI将考虑1000 ^ 6顶点..
任何想法如何优化？或者更确切地说是有办法吗？
一件容易的事就是从两个方向工作:
在每一步,执行以下操作:
如果图形很大但高度连接,那么你将以这种方式节省相当多的空间,但它确实需要一些额外的时间来比较邻居集.