在DI-Graph中检查是否存在任何路径 [英] Check if exists any path, in 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= {}

这篇关于在DI-Graph中检查是否存在任何路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！