2

E我有一个带有节点的图的边（）列表V = [1,2,3,4,5,6]：

E = [(1,2), (1,5), (2,3), (3,1), (5,6), (6,1)]

其中每个元组分别(a,b)指边缘的开始和结束节点。

如果我知道边在图 G 中形成闭合路径，我可以恢复路径吗？

请注意，这E不是图的所有边的集合。它只是一组边缘。

在本例中，路径为1->2->3->1->5->6->1

我能想到的一种天真的方法是使用以节点开头的树，例如1，然后查看所有以1、 这里(1,2)和开头的元组(1,5)。然后我有两个分支，节点为2& 5，我继续这个过程，直到我在一个分支的起始节点处结束。

如何在python中有效地编码？

4

2 回答 2

0

您正在（子）图中寻找有向欧拉回路。欧拉回路是一条每条边都只访问一次的路径。

该networkx软件包具有可以在线性时间内为您生成所需电路的功能：

import networkx as nx

edges = [(1,2), (1,5), (2,3), (3,1), (5,6), (6,1)]
G = nx.MultiDiGraph()
G.add_edges_from(edges)

# Prints [(1, 5), (5, 6), (6, 1), (1, 2), (2, 3), (3, 1)]
# which matches the desired output (as asked in the comments).
print([edge for edge in nx.algorithms.euler.eulerian_circuit(G)])

如果您有兴趣了解该算法的工作原理，该文档引用了 1973 年的一篇论文。您也可以在此处查看源代码。请注意，我们在这里使用多重图，因为您可以拥有多个具有相同源节点和目标节点的边。Internet 上可能还有其他实现，但它们可能适用于多图，也可能不适用于多重图。

于 2022-01-23T16:42:28.543 回答
0

networkx 包具有可以在线性时间内为您生成所需电路的功能...

有可能，如所讨论的那样，构建nx.MultiDiGraph()速度较慢且效率不高，或者仅将外部包用于一个功能是相当过度的。如果是这样，还有另一种方法。

计划：首先我们会找到一些从start_nodeto 的方式start_node，然后我们将插入所有尚未访问的循环。

from itertools import chain
from collections import defaultdict, deque
from typing import Tuple, List, Iterable, Iterator, DefaultDict, Deque


def retrieve_closed_path(arcs: List[Tuple[int, int]], start_node: int = 1) -> Iterator[int]:
    if not arcs:
        return iter([])

    # for each node `u` carries queue of its
    # neighbours to be visited from node `u`
    d: DefaultDict[int, Deque[int]] = defaultdict(deque)
    for u, v in arcs:
        # deque pop and append complexity is O(1)
        d[u].append(v)

    def _dfs(node) -> Iterator[int]:
        out: Iterator[int] = iter([])
        # guarantee, that all queues
        # will be emptied at the end
        while d[node]:
            # chain returns an iterator and helps to
            # avoid unnecessary memory reallocations
            out = chain([node], _dfs(d[node].pop()), out)
            # if we return in this loop from recursive call, then
            # `out` already carries some (node, ...) and we need
            # only to insert all other loops which start at `node`
        return out

    return chain(_dfs(start_node), [start_node])


def path_to_string(path: Iterable[int]) -> str:
    return '->'.join(str(x) for x in path)

例子：

    E = [(1, 2), (2, 1)]
    p = retrieve_closed_path(E, 1)
    print(path_to_string(p))
    >> 1->2->1

    E = [(1, 2), (1, 5), (2, 3), (3, 1), (5, 6), (6, 1)]
    p = retrieve_closed_path(E, 1)
    print(path_to_string(p))

    >> 1->5->6->1->2->3->1

    E = [(1, 2), (2, 3), (3, 4), (4, 2), (2, 1)]
    p = retrieve_closed_path(E, 1)
    print(path_to_string(p))

    >> 1->2->3->4->2->1


    E = [(5, 1), (1, 5), (5, 2), (2, 5), (5, 1), (1, 4), (4, 5)]
    p = retrieve_closed_path(E, 1)
    print(path_to_string())
    >> 1->4->5->1->5->2->5->1
于 2022-01-23T18:13:19.000 回答