1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
|
from graph import distance
from queue import PriorityQueue
from copy import deepcopy
def greedy(graph: list):
route = []
q = PriorityQueue()
for i, town1 in enumerate(graph):
for town2 in graph[i:]:
if town1 != town2:
q.put((distance(town1, town2), town1, town2))
def detect_cycle(start, end, target, gr, seen):
if start == target:
gr = deepcopy(gr)
gr[start].append(end)
gr[end].append(start)
if end == target or start in seen:
return True
seen.add(start)
for x in gr[end]:
if x != start:
t = detect_cycle(end, x, target, gr, seen)
if t:
return t
return False
g = {town: [] for town in graph}
while not q.empty() and len(route) < len(graph):
d, start, end = q.get()
if len(g[start]) >= 2 or len(g[end]) >= 2:
continue
if len(route) < len(graph)-1 and detect_cycle(start, end, start, g, set()):
continue
route.append((start, end))
g[start].append(end)
g[end].append(start)
return route
|
