隨機遍歷有向圖

我有一個有向圖，下面的程序遍歷從一個隨機起點到一個隨機終點的圖。我需要做的是隨機遍歷圖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()

來源

2016-03-17 user2987377

爲什麼你需要方法只是爲了獲得一個隨機數？ –

也要小心你的可變默認參數。 http://stackoverflow.com/questions/1132941/least-astonishment-in-python-the-mutable-default-argument –

如果我理解正確的，你要問什麼，下面的代碼應該這樣做（見註釋在線）：

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

來源

2016-03-17 15:22:23

這很完美。正是我想要的。 – user2987377

@ user2987377不客氣。 –

隨機遍歷有向圖

回答

相關問題