Tests show that closest pairs heuristic generally performs better than nearest neighbour heuristic.
Here's python implementation for nearest neighbour heuristic:

import random
import matplotlib.pyplot as plot
import matplotlib.cm as cm
import numpy as np
import math

def draw_arrow(axis, p1, p2, linecolor, style='solid', text="", radius=0):
"""draw an arrow connecting point 1 to point 2"""
axis.annotate(text,
xy=p2,
xycoords='data',
xytext=p1,
arrowprops=dict(arrowstyle="-", linestyle=style, linewidth=0.8, color=linecolor,

#nearest neighbour heuristic
def nearest_neighbour(datapoints):
x, y = 0, 1
#pick random starting point and add it to path
i = random.randint(0, len(datapoints) - 1)
path = [datapoints[i]]
del datapoints[i]
i = 0
# while there are points find the closest one to datapoints[i], add it to path
while(len(datapoints) != 0):
minlen = 1e124
minind = -1
for k in range(len(datapoints)):
dist = math.hypot(datapoints[k][x] - path[i][x], datapoints[k][y] - path[i][y])
if minlen > dist:
minlen = dist
minind = k
path.append(datapoints[minind])
del datapoints[minind]
i += 1
return path

# MAIN SCRIPT
random.seed()
figure = plot.figure()

n = 6
points = [(random.uniform(0.01, 0.99), random.uniform(0.01, 0.99)) for i in range(n)]
# points for line
points = [(0.3, 0.2), (0.25, 0.2), (0.5, 0.2), (0.7, 0.2), (0.6, 0.2), (0.8, 0.2)]

# find shortest path
path_points = nearest_neighbour(points)

# draw path
colors = cm.rainbow(np.linspace(0, 1, len(path_points)))
plot.scatter([i for i in path_points], [i for i in path_points], color=colors)
# draw shortest path from point to point[n-1]:
draw_arrow(axis, path_points, path_points, colors, style='solid', radius=0.3)
for i in range(1, len(path_points)-1):
draw_arrow(axis, path_points[i], path_points[i + 1], colors[i], radius=0.3)
draw_arrow(axis, path_points[n - 1], path_points, colors[n-1], style='dashed', radius=0.3)

plot.show()


Python implementation of closest pair heuristic

import random
import matplotlib.pyplot as plot
import matplotlib.cm as cm
import numpy as np
import math

def draw_arrow(axis, p1, p2, linecolor, style='solid', text = "", radius = 0):
"""draw an arrow connecting point 1 to point 2"""
axis.annotate(text,
xy=p2,
xycoords='data',
xytext=p1,
arrowprops=dict(arrowstyle="-", linestyle=style, linewidth=0.8, color=linecolor,

#closest pair heuristic
def closest_pair(points):
distance = lambda c1p, c2p:  math.hypot(c1p - c2p, c1p - c2p)
chains = [[points[i]] for i in range(len(points))]
edges = []
for i in range(len(points)-1):
dmin = float("inf")  # infinitely big distance
# test each chain against each other chain
for chain1 in chains:
for chain2 in [item for item in chains if item is not chain1]:
# test each chain1 endpoint against each of chain2 endpoints
for c1ind in [0, len(chain1) - 1]:
for c2ind in [0, len(chain2) - 1]:
dist = distance(chain1[c1ind], chain2[c2ind])
if dist < dmin:
dmin = dist
# remember endpoints as closest pair
point1, point2 = chain1[c1ind], chain2[c2ind]
# connect two closest points
edges.append((point1, point2))

# connect first endpoint to last one
edges.append((chains, chains[len(chains)-1]))
return chains, edges

# MAIN SCRIPT
random.seed()
figure = plot.figure()

n = 6
points = [(random.uniform(0.01, 0.99), random.uniform(0.01, 0.99)) for i in range(n)]
# six points for a rectangle
points = [(0.3, 0.2), (0.3, 0.4), (0.501, 0.4), (0.501, 0.2), (0.702, 0.4), (0.702, 0.2)]

#find shortest path
path_points, edges = closest_pair(points)

#draw path
colors = cm.rainbow(np.linspace(0, 1, len(path_points)))
plot.scatter([i for i in points], [i for i in points], color=colors)
# draw shortest path from point to point[n-1]:
for i in range(len(edges)):

plot.show()

The minimum angle with randomised centroid heuristic solves both cases closest pair and nearest neighbour can't handle.
1. Calculate the centroid (geometric mean of x and y coordinates) of all points given. Add a little offset to centroid, that allows to solve cases when points form a line.
2. Find the point that is furthermost from centroid. Let's call it point1
3. Find point2 that comprises the smallest angle point1-centroid-point2
4. Connect point1 and point2 with an edge.
5. Repeat from step 3 with point2.

import random
import matplotlib.pyplot as plot
import matplotlib.cm as cm
import numpy as np
import math

def draw_arrow(axis, p1, p2, linecolor, style='solid', text = "", radius = 0):
"""draw an arrow connecting point 1 to point 2"""
axis.annotate(text,
xy=p2,
xycoords='data',
xytext=p1,
arrowprops=dict(arrowstyle="-", linestyle=style, linewidth=0.8, color=linecolor,

def angle_degrees(p1, center, p2):
distance = lambda c1p, c2p:  math.hypot(c1p - c2p, c1p - c2p)
a = distance(center, p1)
b = distance(center, p2)
c = distance(p2, p1)
cosine = (a**2 + b**2 - c**2) / (2*a*b)
return math.acos(min(max(cosine, -1), 1))

def centroid(points):
center = (sum([point for point in points])/len(points) + random.uniform(0.010, 0.015),
sum([point for point in points])/len(points) + random.uniform(0.010, 0.015))
edges = []
# remember how many connections a point has. start with 0 connections
uses = dict([(point, 0) for point in points])
point1 = points
longest = math.hypot(center - point1, center - point1)
for pt in points:
dist = math.hypot(center - pt, center - pt)
if dist > longest:
longest = dist
point1 = pt
# for every point find the other one that comprises the SMALLEST angle poin1-center-point2
while True:
if uses[point1] < 2:
min_angle = 1e34
point_to_connect = None
# point must not be used more than twice!
for point2 in [item for item in points if item is not point1]:
angle = angle_degrees(point1, center, point2)
if not (point1, point2) in edges and not (point2, point1) in edges and uses[point2] < 1 and\
angle < min_angle:
min_angle = angle
point_to_connect = point2
if point_to_connect is not None:
edges.append((point1, point_to_connect))
uses[point1] += 1
uses[point_to_connect] += 1
point1 = point_to_connect
else:
break
else:
break
# connect the last two points
last_points = [k for k, v in uses.iteritems() if v == 1]
assert(len(last_points) == 2)
edges.append((last_points, last_points))

return edges, center

# MAIN SCRIPT
random.seed()
figure = plot.figure()

n = random.randint(6, 10)
points = [(random.uniform(0.01, 0.99), random.uniform(0.01, 0.99)) for i in range(n)]
# points for line
#points = [(0.3, 0.2), (0.4, 0.2), (0.5, 0.2), (0.7, 0.2), (0.6, 0.2), (0.86, 0.2)]
# six points for a rectangle
#points = [(0.3, 0.2), (0.3, 0.4), (0.501, 0.4), (0.501, 0.2), (0.702, 0.4), (0.702, 0.2)]

edges, center = centroid(points)

# draw points
colors = cm.rainbow(np.linspace(0, 1, len(points)))
plot.scatter([i for i in points], [i for i in points], color=colors)

# draw lines from centroid to points
plot.scatter(center, center, color='green')
for point in points:
plot.show()