python - 随机遍历有向图

Question

我有一个有向图，以下程序从随机起点遍历该图到随机终点。我需要它做的是随机遍历该图x次，每次从前一个节点中随机选择一个节点，但我不确定如何实现这一点。节点是否被多次访问并不重要。

    def find_path(graph, start, end, path=[]):

        path = path + [start]
        print path
        if start == end:
            return path

        for node in graph[start]:
            if node not in path:
                newpath = find_path(graph, node, end, path)
                if newpath: return newpath

        return None
        print path

# main function
def main():



    start = str(random.randint(1,10))


    finish = str(random.randint(1,10))

    print start
    print finish

    graph = {'1': ['9'],
         '2': ['10'],
         '3': ['6', '8'],
         '4': ['1', '6'],
         '5': ['1'],
         '6': ['7'],
         '7': ['1', '3'],
         '8': ['2'],
         '9': ['4'],
         '10': ['3', '5']}          

    find_path(graph, start, finish)       


if __name__ == '__main__':
    main()

Answer 1

如果我正确理解了您的要求，则以下代码应该可以做到这一点(请参阅内联注释):

import random

def find_path(graph, start, end, path, max_):
    # Append to the path
    path.append(start)
    # If the end has been reached, or the length about to exceed, return
    if start == end or len(path) == max_:
        return path

    # Randomly select the next neighbor and traverse it
    find_path(graph, random.choice(graph[start]), end, path, max_)

graph = {1: [9], 2: [10], 3: [6, 8], 4: [1, 6], 5: [1], 6: [7], 7: [1, 3],
         8: [2], 9: [4], 10: [3, 5]}

start = random.randint(1, 10)
end = random.randint(1, 10)

path = []
find_path(graph, start, end, path, 20)
print start, end, path