根据连邻边的条件查询路径
来源：4-7 所有点对路径问题
zhoukui
2020-06-05
老师你好，我现在遇到了一些问题，希望老师能给一点思路。
我现在需要根据图的相邻边是否满足指定条件并获取到满足条件的所有路径
图大概是这样：
找到满足前后两条边的权值相差等于1的所有路径(节点数量大于等于3)。
结果：
写回答
1回答
-
liuyubobobo
2020-06-06
从每个节点出发，做 dfs，过程中记录路径并检查边的权值。一旦边的权值不符合条件，停止。路径中节点数只要大于等于3 则找到了一个合法的路径。
以每个节点起始的所有合法路径可以做一个记录，这样搜索过程中一旦遇到一个节点存在路径，可以直接把当前搜索的路径和以这个节点其实的所有路径接上，避免重复搜索。
但是，这个问题依然是指数级别的复杂度，因为问题的解最多是指数级别的。在最差情况下从某个点出发的所有路径都满足条件。比如下图中，每一层的所有节点到下一层的所有节点都有路径，且权值为上一层路经 +1
0 假设从 0 到 1 2 3 的权值为 1 1 2 3 假设从 1 2 3 均可以到达 4 5 6，且权值为 2 4 5 6 假设从 4 5 6 均可以到达 7 8 9，且权值为 3 7 8 9 上图总共有 27 条路径；如果再添加一层，就是 81 条路径。
和这里的讨论类似，虽然问题不一样，但都是指数级别的。
http://coding.imooc.com/learn/questiondetail/140717.html
继续加油！：）
10
相似问题