在DI

本文介绍了在DI-Graph中检查是否存在任何路径的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

如果我有Di-Graph，如何检查所有节点对(a，b)是否都创建路径?

If i have a Di-Graph, how to check if all pairs (a,b) of nodes create a path?

示例:

输入:

v1 v2 v5 v6 v2 v3 v3 v4 v4 v5 v0 v1

我需要检查是否存在通过该图的至少一条路径，而不必再访问每个节点一次.

And i need check if exist atleast one path through this graph, without visiting each node more then once.

我已经尝试过回溯，但要获得最大的投入，将需要数小时...

I have already tried backtracking, but for biggest input it will took hours...

具体示例:

输入时，我有边缘:

{m,a}, {a,c}, {a,m}

我必须检查是否存在路径，在这种情况下，它会返回True，因为存在

and i have to check, if there is a path, in this case it will return True, because exist

{a,m} -> {m, a} -> {a,c}

推荐答案

一种相对幼稚的二次算法

从路径列表中弹出路径.在列表中弹出另一个路径以与其连接.将串联的路径推回列表中.如果在任何时候都找不到另一条路径与其连接，则意味着答案是否定的，所有节点对都不会合并为一条路径，因此我们返回None.

def combine_into_one_path(list_of_paths): path = list_of_paths.pop() while list_of_paths: path2 = pop_adjacent_path(list_of_paths, path[0], path[-1]) if path2 is None: return None elif path[-1] == path2[0]: path = path[:-1] + path2 elif path2[-1] == path[0]: path = path2[:-1] + path else: assert(False) return path def pop_adjacent_path(list_of_paths, a, b): for i,p in enumerate(list_of_paths): if p[0] in (a, b) or p[-1] in (a,b): return list_of_paths.pop(i) return None print(combine_into_one_path([[1, 2], [5, 6], [2, 3], [3, 4], [4, 5], [0, 1]])) # [0, 1, 2, 3, 4, 5, 6] print(combine_into_one_path([[1, 2], [5, 6], [2, 3], [3, 7], [4, 5], [0, 1]])) # None

此算法的路径数是二次的，因为combine_into_one_path中的while-循环在列表中的每个路径上都有一个迭代，并且函数pop_adjacent_path也在列表中迭代.

This algorithm is quadratic in the number of paths because the while-loop in combine_into_one_path has one iteration per path in the list, and function pop_adjacent_path iterates through the list as well.

请注意，此代码不会检查节点是否唯一；例如，[v1, v2, v3, v2, v4, v1, v5]将被视为有效路径.您可以在combine_into_one_path的最终返回值之前添加一个检查，以确保路径中的每个元素都是唯一的.

Note that this code doesn't check that nodes are unique; for instance, [v1, v2, v3, v2, v4, v1, v5] would be considered a valid path. You could add a check just before the final return in combine_into_one_path to make sure every element in the path is unique.

该算法的速度变慢了，它必须遍历整个列表以找到一对将我们的当前路径与之结合的节点.避免这种情况的一种方法是将对存储在字典中，这样我们就可以回答对以a结尾吗?"的问题.和一对以b开头吗?"?在恒定的时间内.

What slow the algorithm down is having to iterate through the whole list to find a pair of nodes to combine our current path with. One way to avoid that would be to store the pairs in a dictionary, so we can answer the questions "does a pair end with a?" and "does a pair start with b?" in constant time.

def combine_into_one_path(list_of_paths): path = list_of_paths.pop() forwards = {p[0]:p for p in list_of_paths} backwards = {p[-1]:p for p in list_of_paths} while forwards: if path[-1] in forwards: p2 = forwards[path[-1]] del forwards[path[-1]] del backwards[p2[-1]] path = path[:-1] + p2 elif path[0] in backwards: p2 = backwards[path[0]] del backwards[path[0]] del forwards[p2[0]] path = p2[:-1] + path else: return None print('\npath =', path) print('forwards =', forwards) print('backwards=', backwards) return path print(combine_into_one_path(['manta', 'alcats', 'random'])) # randomantalcats

这几乎是相同的算法，但是我们用字典检查代替了函数pop_adjacent_path，这是恒定时间而不是线性时间.

This is almost the same algorithm, but we replaced function pop_adjacent_path with a dictionary check, which is constant time instead of linear.

只需了解算法的工作原理即可:

Just to understand how the algorithm works:

list_of_paths = [[1, 2], [5, 6], [3, 4], [4, 5], [0, 1], [2, 3]] path = [2, 3] forwards = {1: [1, 2], 5: [5, 6], 3: [3, 4], 4: [4, 5], 0: [0, 1]} backwards= {2: [1, 2], 6: [5, 6], 4: [3, 4], 5: [4, 5], 1: [0, 1]} path = [2, 3, 4] forwards = {1: [1, 2], 5: [5, 6], 4: [4, 5], 0: [0, 1]} backwards= {2: [1, 2], 6: [5, 6], 5: [4, 5], 1: [0, 1]} path = [2, 3, 4, 5] forwards = {1: [1, 2], 5: [5, 6], 0: [0, 1]} backwards= {2: [1, 2], 6: [5, 6], 1: [0, 1]} path = [2, 3, 4, 5, 6] forwards = {1: [1, 2], 0: [0, 1]} backwards= {2: [1, 2], 1: [0, 1]} path = [1, 2, 3, 4, 5, 6] forwards = {0: [0, 1]} backwards= {1: [0, 1]} path = [0, 1, 2, 3, 4, 5, 6] forwards = {} backwards= {}