列出有向图中的所有路径-解网

问：

我有一些图表，我在这里找到的 depthFirst 搜索不起作用。我的节点不会直接指向另一个节点，但如下所示：

graph = {
    'type1': {'varname1': ['type2', 'comment1'], 'varname7': ['none', 'comment7']},
    'type2': {
        'varname2': ['type3', 'comment2'],
        'varname3': ['type3', 'comment3'],
        'varname4': ['none', 'comment4']
    },
    'type3': {'varname5': ['none', 'comment5']}
}

目标是：我想查找一个类型，并且只获取路径的变量名称。（现在让我们忽略评论）对于 type1，它将是：

[
    ['varname1', 'varname2', 'varname5'],
    ['varname1', 'varname3', 'varname5'],
    ['varname1', 'varname4'],
    ['varname7']
]

不同的变量可以具有相同的类型。例如，varname2 和 varname3 都指向 type3。这就是为什么我需要两者兼而有之。如果未找到类型，例如“none”，则路径应以该变量结尾。这同样适用于注释，以与变量名称相同的列表格式获取它们。

我试图调整深度优先搜索，但我无法让它工作。访问的元素要么包含太多，要么不够。

visitedList = []

def depthFirst(graph, currentVertex, visited):
    next_node = graph.get(currentVertex)
    if next_node:
        for type_name, var_name in next_node.items():
            visited.append(type_name)
            depthFirst(graph, var_name[0], visited.copy())
    else:
        visitedList.append(visited.copy())
        visited.pop()

depthFirst(graph2, 'type1', [])

初始图形不必采用该确切格式。如果有帮助，我可以以不同的方式构建它。

python 字典图深度优先搜索

graph = {
    "type1": {"varname1": ["type2", "comment1"], "varname7": ["none", "comment7"]},
    "type2": {
        "varname2": ["type3", "comment2"],
        "varname3": ["type3", "comment3"],
        "varname4": ["none", "comment4"],
    },
    "type3": {"varname5": ["none", "comment5"]},
}


def traverse(graph, node, current=None):
    if current is None:
        current = []

    for k, (t, _) in graph.get(node, {}).items():
        if t == "none":
            yield current + [k]
        else:
            yield from traverse(graph, t, current + [k])


out = list(traverse(graph, "type1"))
print(out)

指纹：

[
    ["varname1", "varname2", "varname5"],
    ["varname1", "varname3", "varname5"],
    ["varname1", "varname4"],
    ["varname7"],
]

列出有向图中的所有路径

List all paths in a directed graph

评论

评论