用Networkx运行有向图随机遍历的更有效方法

Question

我试图模拟一个随机遍历有向networkx图。伪代码如下

Create graph G with nodes holding the value true or false. 
// true -> visited, false -> not visited

pick random node N from G
save N.successors as templist
while true
    nooptions = false
    pick random node N from templist
    while N from templist has been visited
        remove N from templist
        pick random node N from templist
        if templist is empty
            nooptions = true
            break
    if nooptions = true 
        break
    save N.successors as templist 

有没有一种更有效的方法来标记一条路径，而不是 创建临时列表并删除标记为已访问的元素？在

编辑

该算法的目标是在图中随机选取一个节点。随机选取该节点的后续节点/子节点。如果是未访问的，去那里并标记为已访问。重复此操作，直到没有继承者/子级或没有未访问的继承者/子级

Answer 1

根据图形的大小，可以使用内置的all_pairs_shortest_path函数。你的功能基本上是：

G = nx.DiGraph()
<add some stuff to G>

# Get a random path from the graph
all_paths = nx.all_pairs_shortest_path(G)

# Choose a random source
source = random.choice(all_paths.keys())
# Choose a random target that source can access
target = random.choice(all_paths[source].keys())
# Random path is at
random_path = all_paths[source][target]

似乎没有一种方法可以生成从source开始的随机路径，但是python代码是可以访问的，我认为添加这个特性将是很简单的。在

另外两种可能更快，但稍微复杂一点/手动，那就是使用bfs_successors，它执行广度优先搜索，并且应该只在列表中包含一次任何目标节点。对格式不是百分之百肯定，所以可能不方便。在

您还可以生成bfs_tree，这将生成一个子图，该子图对它可以到达的所有节点都没有循环。那可能更简单，也可能更短？在

^{pr2}$