https://www.cnblogs.com/chen-kh/p/7137565.htmldef find_eulerian_tour(graph):
# your code here
start_edge = graph[0]
tour = [start_edge[0]]
tour_list = []
return find_tour(graph ,tour, tour_list)
def find_tour(graph,tour,tour_list):
if len(graph) == 0:
print tour_list
if len(tour_list) == 1:
return tour_list[0]
for i in range(len(tour_list)):
for j in range(i + 1,len(tour_list)):
uni_list = list(set(tour_list[i]).intersection(set(tour_list[j])))
if len(uni_list) > 0:
index_i = tour_list[i].index(uni_list[0])
index_j = tour_list[j].index(uni_list[0])
tour_list[i][index_i:index_i] = tour_list[j][:index_j]
tour_list[i][index_i:index_i] = tour_list[j][index_j:-1]
tour_list.pop(j)
return find_tour(graph,tour,tour_list)
for edge in graph:
if edge[0] == tour[-1]:
tour.append(edge[1])
graph.remove(edge)
if len(graph) == 0:
tour_list.append(tour)
return find_tour(graph ,tour,tour_list)
elif edge[1] == tour[-1]:
tour.append(edge[0])
graph.remove(edge)
if len(graph) == 0:
tour_list.append(tour)
return find_tour(graph ,tour,tour_list)
tour_list.append(tour)
return find_tour(graph, [graph[0][0]], tour_list)
def test():
#print find_eulerian_tour( [(0, 1), (1, 5), (1, 7), (4, 5),(4, 8), (1, 6), (3, 7), (5, 9),(2, 4), (0, 4), (2, 5), (3, 6), (8, 9)])
print find_eulerian_tour( [(1, 13), (1, 6), (6, 11), (3, 13),(8, 13), (0, 6), (8, 9),(5, 9), (2, 6), (6, 10), (7, 9),(1, 12), (4, 12), (5, 14), (0, 1), (2, 3), (4, 11), (6, 9),(7, 14), (10, 13)])
test()
