最近在业务上遇到了这么一个问题:
假想我们有一个工厂， 有一个万能制造机。 只要扔进去合适的源材料，再加上一些口令，就能立刻产生我们需要的生成物。
举例说明: 把苹果，草莓丢进机器产生混合果酱， 把果酱和面包丢进去，又可以生成夹心面包。如下图所示:
构建过程.png
如果我们把每一个源材料和生成物都加上版本，就可以精确的描述一个加工的链路。一旦最终产物（在这里是夹心面包）出现了问题， 我们可以很轻松的找出生成这个面包的所有材料。
那么是否有可能一个东西，经过若干次的加工，又生成了自己呢？
这个问题，在自然界当然是有可能的，最典型的就是水的三态之间的转换了。但是在我们的系统中，不允许出现这样的事情。因为我们是有版本控制的，水(v1.0) 凝固成冰(v1.0)，再从冰(v1.0)液化，只能生成水(v2.0)。
说了那么多前提假设， 现在回到我们业务上的问题：
源数据: 节点(node)List，每个节点的子节点List（没有子节点的节点是叶子节点）, 最终产物节点
求解: 生成最终产物的“构建链路”
这个问题咋一看很简单。 从最终节点入手，找出它的子节点list。再遍历它的子节点list， 找出每个子节点的子节点，一直追溯到叶子节点。最终我们可以画出一颗”树形“的链路。
然而，真的是树形吗？求解的过程中会遇到什么坑呢。
首先，这个模型很容易被误解成树形，因为它有非常明确的父子层次结构。但是不要忘了一点设定。一个构建源不仅仅可以生成一种生成物（比如说草莓可以生成草莓酱，也可以生成草莓汁），如果在之前的图中草莓和面包之间加一条线，这颗“树形结构”就变成了“图形结构”， 而且是有向图。
那么，会遇到什么坑呢？我们的源数据是一堆node和每个node的子node列表， 虽然业务上不允许某物体经过多次构建又生成了自己，但数据有可能是不准确的啊。设想一下如果是A->B->C->A这一条链路，那么对A溯源的结果就可能陷入一种死循环。 所以当我们编码实现的时候，一定要考虑这种异常情况， 避免程序陷入死循环。
这道题目，我作为面试题考过不少同学，但目前还没有人能答出。它实际上是一道检测有向图是否有环的算法。我们可以按照一般人的思维来推导出解题的过程。
容易想到的思路, 从根节点出发，按照“先序”（每个节点都是先访问自己，再从左到右访问自己的子节点）的方式遍历。 把所有已经搜索过的节点放进一个列表中。 一旦搜索到某个已经在列表中出现过的节点时， 则认为“成环”、
这个方法看起来没啥问题， 实际上考虑并不全。下图的情况会被误认为成环，而造成溯源失败。
溯源.png
之所以误认为成环是因为，在遍历A的子节点时，已经搜索了B了，后面在遍历C的字节点时又出现了B。其实，稍微动一下脑筋就可以发现解法了。
根据深度优先搜索的顺序，看一下流程：
- 搜索A， 把A加入列表
- 搜索A的第一个子节点B， 把B加入列表
- 搜索A的第二个子节点C， 把C加入列表
- 搜索C的第一个子节点B， 发现列表重复
我们看第三步，搜索C的前提是B和B的子节点均搜索完毕了。C和B都是A的子节点，不应该共享A－>B的这一个搜索路径，因此在第二步后加上一个pop（B）的逻辑，整个算法就完美了。
用程序员的语言来说就是， 按照深度优先搜索的顺序， 并且当一个节点为叶子节点时，搜索完之后，需要把自己从队列中清除。 当一个节点的所有子节点都已搜索完毕时， 需要把自己从队列中清除。
本文主要介绍了一个把业务模型如何一步步抽象成具体算法的思路。 代码实现不是本文的重点，就略过了～
网友评论