linnad={
   "Tallinn" : ["Tapa"],
   "Tapa"    : ["Tallinn", "Tartu", "Rakvere"],
   "Rakvere" : ["Tapa", "Narva"],
   "Narva"   : ["Rakvere"],
   "Tartu"   : ["Tapa", "Valga", "Koidula"],
   "Valga"   : ["Tartu", "Koidula"],
   "Koidula" : ["Tartu", "Valga"],
   "Lavassaare" : []
}

uuritavLinn="Valga" #otsingute algkoht
uuritudLinnad=[]    #pole enam põhjust analüüsida
leitudLinnad=[]     #teada, et olemas, aga edasiteed vaatamata

for linn in linnad[uuritavLinn]:
    if linn not in uuritudLinnad+leitudLinnad:
      leitudLinnad.append(linn)
uuritudLinnad.append(uuritavLinn)

print(leitudLinnad)
while leitudLinnad:
    uuritavLinn=leitudLinnad.pop()
    print()
    print("Uuritakse "+str(uuritavLinn))
    print("Uuritud "+str(uuritudLinnad))
    print("Uurimata "+str(leitudLinnad))
    for linn in linnad[uuritavLinn]:
     if linn not in uuritudLinnad+leitudLinnad:
      leitudLinnad.append(linn)
      print("leiti "+linn)
     else:
      print(linn+" juba teada")
    uuritudLinnad.append(uuritavLinn)