查找图到N的所有路径从A [英] Find all paths in graph from A to N

查看:161
本文介绍了查找图到N的所有路径从A的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

我想端口下面的例子蟒蛇code到Java:

 高清find_all_paths(图,起点,终点,路径= []):
    路径=路径+ [开始]
    如果开始==结束:
        返回[路径]
    如果不是graph.has_key(开始):
        返回 []
    路径= []
    在图节点[开始]:
        如果节点不在路径:
            newpaths = find_all_paths(图,节点,为此,路径)
            为的新路径在newpaths:
                paths.append(的新路径)
    返回路径
 

问题是,基本情况停止递归:

 如果start ==结束:
    返回[路径]
 

它不支持我的允许下,A和N至相同节点的要求。

例如:

如果我有以下的有向图的:

  A  - > [公元前],
乙 - > [C,E],
C  - > [D,A]
 

和我想A和A之间的所有路径,我应该有结果:

  A  - >乙 - > C  - >一个
 

以上蟒蛇code只会给我:

  A
 

解决方案

从A的路径发生必须经过A的邻居因此,为了实现这一个方法是枚举所有向外邻居:

  [[[A] + Y y的在find_all_paths(G,X,A)]对于x在图[A]
 

有关你的图表,结果应该是

  [[[A,B,C,A],['A','C','A']]]
 

I'm trying to port the following example python code to Java:

def find_all_paths(graph, start, end, path=[]):
    path = path + [start]
    if start == end:
        return [path]
    if not graph.has_key(start):
        return []
    paths = []
    for node in graph[start]:
        if node not in path:
            newpaths = find_all_paths(graph, node, end, path)
            for newpath in newpaths:
                paths.append(newpath)
    return paths

The problem being, the base case to stop recursing:

if start == end:
    return [path]

It doesn't support my requirement of allowing both A and N to be the same node.

For example:

If I have the following digraph:

A -> [B, C], 
B -> [C, E], 
C -> [D, A]

And I want all paths between A and A, I should have the result:

A -> B -> C -> A

The above python code will just give me:

A

解决方案

A path from A to A must go through a neighbor of A. Thus, one way to implement this is to enumerate all of the outward neighbors:

[[["A"]+y for y in find_all_paths(G,x,"A")] for x in graph["A"]]

For your graph, the result should be

[[['A', 'B', 'C', 'A']], [['A', 'C', 'A']]]

这篇关于查找图到N的所有路径从A的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!

查看全文
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆