ich muss für die Uni in einem gegebenen Graphen (Adjazenzliste) eine Eulertour finden.
Gibt es keine soll False zurückgegeben werden
Ansonsten die Tour in der Form [Startknoten, nächsterKnoten. nächsterKnoten, nächsterKnoten, ..., Startknotem]
Mein Programm funktioniert soweit (für die im folgenden Code angegebenen Beispiele (Funkition: test()))
Das Abnahmeprogramm gibt jedoch noch ca 1 min zurück:
Dein Programm gibt falsche Ergebnisse zurück
oder hat zu lange gebraucht.
Kann mir jemand weiterhelfen ob es einen Fehler gibt (und welche Eingabe diesen provoziert) oder ein Tipp geben wie ich die Laufzeit verbessern kann!?
Vielen Dank!!
Code: Alles auswählen
#!/usr/bin/env python
def eulertour(adj): #übergabe adj ist adjazenzliste (liste von listen)
#prüfen ob es Knoten mit ungeradem Knotenknotengrad gibt?
#Suche des Starknotens
startknoten = -1
j=-1
aloi = len(adj)
for knoten in adj: #gehe die Verknüpfungs listen der einzelnen Knoten durch (listen in adj)
j += 1 #Hilfsvariable für startknoten
if len(knoten)%2 != 0: #wenn knotengrad ungerade
#print("knotengrad")
return False
if len(knoten) == 0:
aloi -= 1
else:
startknoten= j
if startknoten == -1: #Sollte Starknoten immer noch = -1 sein ,dann besteht adj nur aus leeren listen bzw. aus isolierten knoten
listeO = []
return listeO #in diesem Fall wird ein einzelner Knoten (der erste) aus der (index) adj liste ausgegeben oder eine Leere liste
#Eulertoursuche
#print(a)
Kreisliste = [[startknoten]] #Kreisliste mit dem startknoten
Kreisanzahl = 1
nextknoten = startknoten #nextknoten als startknoten initialisieren
NeuerKreis = 0 #Hilfsvariable um zu ueberpruefen ob ein Kreis geschlossen wurde
Knotengrade = 0
GeloeschteGrade = 0 #variable um die geloeschten verknüpfungen zu zaehlen
h =0 #Hilfsvariable um spaeter festzustellen ob der Graph ohne die iso Knoten zushaengend ist
for elemente in adj: #summiere die knotengrade
Knotengrade += len(elemente)
while GeloeschteGrade != Knotengrade: #solange nicht alle verknüpfungen gelöscht sind
#print(nextknoten)
if len(adj[nextknoten]) == 1 and adj[nextknoten][0] == startknoten: #wenn nextknoten nur noch eine verknuepfung hat und diese der aktuelle startknoten ist
#print("neuer Kreis", Kreisliste)
Kreisliste[Kreisanzahl-1].append(startknoten) #dann wird der Kreis geschlossen
d =adj[startknoten].index(el) # d wird zum index des aktuellen nextknotens in startknotenliste
del adj[startknoten][d] # verknuepfung von nextknoten in startknotenliste wird geloescht
del adj[nextknoten][0] # verknuepfung des startknotens in der nextknotenliste wird geleoscht
GeloeschteGrade +=2
for elem in adj:
if len(elem) > 0: #wenn ein Knoten noch mehr als 1 verknuepfung hat (die liste alsoi mehr als einen eintrag
h +=1
#print(h)
for elle in elem: #gehe die verknuepfungen durch
if elle in Kreisliste[Kreisanzahl-1]: #wenn verknuepfungsknoten (elle) bereits besucht wurde
#print("asdfasdf")
startknoten = elle #neuer Startknoten wird initialisiert
nextknoten = startknoten #naechster Knoten ist der Startknoten
NeuerKreis = 1 #Hilfsvariable zum überpruefen ob zushaengend
Kreisanzahl += 1
Kreisliste.append([nextknoten]) #Fügt Kreisliste neuen Kreis hinzu mit startknoten a
break
if NeuerKreis == 1:
break
if NeuerKreis != 1 and h > 0: #überpruefung zusammenhaengend???
#print("zushang")
return False
else:
Neuerkreis = 0
h =0
for el in adj[nextknoten]: #gehe die (el) die elemente (verknüpfungen) des nextKnoten durch
if el != startknoten: #wenn el nicht der Startknoten
b = adj[nextknoten].index(el) # b wird zum index des elementes in nextknoten
c = adj[el].index(nextknoten) # c wird zum index von nextknoten in el
del adj[nextknoten][b] #lösche die verknüpfung von nextknoten zu el in nextknotenliste
del adj[el][c] #loesche die verknuepfung von el zu nextknoten in elliste
GeloeschteGrade +=2
nextknoten = el #naechster knoten wird el
Kreisliste[Kreisanzahl-1].append(nextknoten) #naechster knoten (el) wird der Kreisliste hinzugefuegt
break
while len(Kreisliste)>1: #zusammenfügen der Kreislisten zu einer Eulertour
#print(Kreisliste)
a = Kreisliste[1][0]
#print("a",a)
b = Kreisliste[0].index(a)
#print("b",b)
Kreisliste[0] =Kreisliste[0][0:b]+Kreisliste[1]+Kreisliste[0][b+1:]
#print(Kreisliste)
del Kreisliste[1]
Eulertour = Kreisliste[0]
return Eulertour #Eulertour fertig (alle kanten benutzt)
def test():
a=[[1,2,3],[0,2,3],[0,1,3,4],[0,1,2,4],[2,3]]
b=[[1,1],[0,0]]
c=[[1,2,3,4],[0,2,3,4],[0,1,3,4],[0,1,2,4],[0,1,2,3]]
d=[[1,3],[0,3],[],[0,1]]
e=[[1,1],[0,0],[3,3],[2,2]]
f=[[],[2,4],[1,3,6,12],[2,4],[1,3,5,7],[4,8],[2,8],[4,8,10,9],[7,9,10,11,6,5],[7,8,10,11],[7,8,9,11],[8,9,10,12],[2,11]]
g=[[1,3],[0,3],[4],[0,1],[2],[],[]]
h=[[1,3],[0,3],[4],[0,1],[2]]
i=[[],[],[]]
j=[[7,9],[2,4],[1,3],[2,4,5,6],[1,3],[3,10,7,11],[7,3],[0,8,5,6],[7,9],[8,0],[12,5],[5,12],[10,11]]
k=[[7,9,13,4],[2,4],[1,3],[2,4,5,6],[1,3,13,0],[3,10,7,11],[7,3],[0,8,5,6],[7,9],[8,0],[12,5],[5,12],[10,11],[4,0]]
List=[a,b,c,d,e,f,g,h,i,j,k]
for list in List:
print(list)
print(eulertour(list), "\n")