我有以下Python代码，它与有向图完美配合。我的问题是如何以这种方式修改代码，以找到忽略边的方向的所有路径。
例如，如果我们有以下连接：
1->2
3->2
我的代码不会返回1和3之间的路径，这是预期的。但是忽略边的方向，代码应该找到从1到3的路径。
我希望代码忽略方向并查找两个给定节点之间的所有路径。
我尝试了所提出的解决方案，它非常有效，解决方案是：">最简单的解决方案可能是通过为图中的每个A->B添加弧B->A来预处理图。">
我真正想要的是修改算法本身，以按原样处理图形。
Python代码：
# a sample graph
graph = {'A': ['B', 'C','E'],
'B': ['A','C', 'D'],
'C': ['D'],
'D': ['C'],
'E': ['F','D'],
'F': ['C']}
class MyQUEUE: # just an implementation of a queue
def __init__(self):
self.holder = []
def enqueue(self,val):
self.holder.append(val)
def dequeue(self):
val = None
try:
val = self.holder[0]
if len(self.holder) == 1:
self.holder = []
else:
self.holder = self.holder[1:]
except:
pass
return val
def IsEmpty(self):
result = False
if len(self.holder) == 0:
result = True
return result
path_queue = MyQUEUE() # now we make a queue
def BFS(graph,start,end,q):
temp_path = [start]
q.enqueue(temp_path)
while q.IsEmpty() == False:
tmp_path = q.dequeue()
last_node = tmp_path[len(tmp_path)-1]
#print tmp_path
if last_node == end:
print "VALID_PATH : ",tmp_path
for link_node in graph[last_node]:
if link_node not in tmp_path:
new_path = []
new_path = tmp_path + [link_node]
q.enqueue(new_path)
BFS(graph,"A","D",path_queue)
----------------代码的输出------------------
['A', 'B', 'D']
['A', 'C', 'D']
['A', 'E', 'D']
['A', 'B', 'C', 'D']
['A', 'E', 'F', 'C', 'D']
注意：我使用Java，以防有人在Java中找到相同问题的解决方案
最简单的解决方案可能是通过为图中的每个A->B添加圆弧B->A来预处理图。然后你应该能够按原样使用你的算法。
每个算法都适用于特定的数据结构和该数据结构所表示的确定图。对于表示特定类型的图，特定的数据结构也是不错的选择。
例如，如果你有(正如你所拥有的)表示有向图的邻接表，并且你希望你的算法将其用作表示无向图的数据结构，你可以这样做，但这将是非常无效的，因为找出节点"A"和节点"B"之间是否存在边意味着确定"B"是否位于表示"A"的相邻节点的行中，以及"A"是否位于表示"B"的相邻节点的行中。因此，如果您只想使用数据结构来识别与节点"A"相邻的所有节点，而不需要进行一些预处理，则搜索完整的邻接列表需要时间。
在您的情况下，用一些更复杂的表达式替换for link_node in graph[last_node]:行，该表达式贯穿整个邻接列表。
编辑：我想到了另一个想法，你也可以在飞行中"预处理"你的图形。我的意思是，每当你的算法到达边"A"->"B"时，它也会将边"B"->"A"添加到你的图中。一个缺点是，如果已经添加了一些边，则需要额外的数据结构来保存信息，相反，您必须只添加有趣的边。