这是一个创建于 1632 天前的主题，其中的信息可能已经有所发展或是发生改变。
原数据结构 [ { from:a, to:b }, {from: b, to: c} , {from: a, to: d}, {from: c, to: d}, { from:c, to :a }, {from:a , to: a}]
现在需要求起始点 a 到 目标点 d , 所有的路径数据 ，类似 结果 ： [ [ a，b，c，d ], [a，d] ]
数据中可能会有环的情况 {from:a , to: a}
技术栈是 javascript
用深度优先递归遍历了， 但是遍历的路径总有些问题，不知道写法有什么不对 , 第一次发帖不知道怎么贴图， 求大佬帮助，给个思路或者解答
现在需要求起始点 a 到 目标点 d , 所有的路径数据 ，类似 结果 ： [ [ a，b，c，d ], [a，d] ]
数据中可能会有环的情况 {from:a , to: a}
技术栈是 javascript
用深度优先递归遍历了， 但是遍历的路径总有些问题，不知道写法有什么不对 , 第一次发帖不知道怎么贴图， 求大佬帮助，给个思路或者解答
第 1 条附言 · 2020-06-10 11:01:46 +08:00
//s1.ax1x.com/2020/06/10/toKXXn.png 代码图床，https:
 |
1
also24 2020-06-09 23:44:59 +08:00
『遍历的路径总有些问题』 具体是什么问题？
是否正确处理了成环的情况？ [ab, bc, ac, cd] [a, b, c, a, b, c, d] |
 |
2
Timefly OP @also24 目前我吧环的数据过滤掉了， 具体主要是路径保存问题，我用 childPaths=[ ]保存遍历路径, 深度递归到一个终点不是 目标值 d 的时候，就从 childPaths 中 pop 推出最后一个，理论上感觉没啥问题，但是结果保存了未指向 d 的路径记录，明天看看怎么贴图大佬看下， 或者大佬能给个大概写法不
|
|
4
Timefly OP 密码忘了，图床链接放不上来， 尴尬
|
|
6
also24 2020-06-10 11:16:05 +08:00
@Timefly #5
啊，JS 我不熟…… 大概看思路没感觉到太大问题，贴下文本单步调一下看看。 https://gist.github.com/ https://pastebin.com/ https://paste.ubuntu.com/ |
|
7
Timefly OP |
|
8
also24 2020-06-10 13:56:27 +08:00
@Timefly #7
我看了一下，大概看到两个问题 1 、你的 47 行 dfs(nextData .....) 这里，传入的 nextData，里面的 isVisit 似乎没有做处理，这导致 a->h->d->e 这条路径跑不出来。 2 、我只看到你标记了已被使用的路径，但是似乎没有处理重复使用的点，这样还是存在成环的可能，建议用一个 map 直接把已经走过的点存起来，这样就可以不用标记路径的 isVisit 了。 比如说在这样的情况下： a->b, b->c , c->a 虽然没有走重复路径，但是 a 点被走了两次，实际上已经成环了。 |
Select Language