def hamiltonkreis(graph): kreisExistiert = False startKnoten = graph[0][0] wege = [[startKnoten]] wegeErweitert = [] zaehler = 0 while wege != [] and not kreisExistiert: aktuellerWeg = wege[0] wege = wege[1:] if len(aktuellerWeg) == len(graph): # Test, ob zu Hamiltonkreis erweiterbar zaehler = zaehler + 1 letzterKnoten = aktuellerWeg[len(aktuellerWeg)-1] # bestimme die Nachbarn von letzterKnoten knotenGefunden = False i = 0 while not knotenGefunden: if letzterKnoten == graph[i][0]: knotenGefunden = True listeNachbarknoten = graph[i][1] i = i+1 # teste, ob es eine Kante zum startKnoten gibt if startKnoten in listeNachbarknoten: kreisExistiert = True #print(aktuellerWeg+[startKnoten]) else: letzterKnoten = aktuellerWeg[len(aktuellerWeg)-1] # bestimme die Anzahl der Nachbarn von letzterKnoten knotenGefunden = False i = 0 while not knotenGefunden: if letzterKnoten == graph[i][0]: knotenGefunden = True listeNachbarknoten = graph[i][1] i = i+1 for nachbarKnoten in listeNachbarknoten: erweiterterWeg = aktuellerWeg + [nachbarKnoten] zaehler = zaehler + 1 if not nachbarKnoten in aktuellerWeg: erweiterterWeg = aktuellerWeg + [nachbarKnoten] wege = [erweiterterWeg] + wege return (kreisExistiert, zaehler) # Test - einfach graph1 = \ [ ['1', ['2', '3']], ['2', ['1', '5', '4', '3']], ['3', ['2', '4', '5', '1']], ['4', ['2', '3']], ['5', ['2', '3']] ] graph2 = \ [ ['1', ['2', '3', '7', '8']], ['2', ['1', '3']], ['3', ['2', '1', '8', '4']], ['4', ['3', '7', '9', '5']], ['5', ['9', '4']], ['6', ['7', '9']], ['7', ['1', '4', '9', '6']], ['8', ['1', '3']], ['9', ['4', '7', '6', '5']], ] print(hamiltonkreis(graph1)) # Test - automatisiert from random import * def graph(n): graph = [] for i in range(n): nachbarn = [] for j in range(4): #range(n//2): nachbarn = nachbarn + [randint(0, n-1)] graph = graph + [[i, nachbarn]] return graph for j in range(4, 20): zaehlerSumme = 0 for i in range(100): aktuellerGraph = graph(j) (kreisExistiert, zaehler) = hamiltonkreis(aktuellerGraph) zaehlerSumme = zaehlerSumme + zaehler zaehlerDurchschnitt = zaehlerSumme // 100 print(j, zaehlerDurchschnitt)