Problem with arrays in a recursive class function

[Aaron Scott]

I have a list of nodes, and I need to find a path from one node to
another. The nodes each have a list of nodes they are connected to,
set up like this:



class Node(object):
	def __init__(self, connectedNodes):
		self.connectedNodes = connectedNodes

nodes = {
	1: Node([4]),
	2: Node([3]),
	3: Node([2, 4, 5]),
	4: Node([1, 6, 3]),
	5: Node([3, 7]),
	6: Node([4, 9]),
	7: Node([5, 8]),
	8: Node([7, 9]),
	9: Node([6, 8])
}



I made a quick brute-force pathfinder to solve it (in this case, a
path from node 1 to node 9). Here it is:



class PathFind(object):
	def __init__(self, source, destination):
		self.source = source
		self.destination = destination
		self.solved = []
	def Search(self):
		self.PathFind([self.source])
		if self.solved:
			print "Solutions: "
			for i in self.solved:
				print "\t" + str(i)
		else:
			print "Couldn't solve."
	def PathFind(self, trail):
		location = trail[-1]
		if location == self.destination:
			self.solved.append(trail)
			print "Solution found: " + str(trail)
		else:
			possibilities = []
			for i in nodes[location].connectedNodes:
				if not i in trail: possibilities.append(i)
			for i in possibilities:
				trail.append(i)
				self.PathFind(trail[:])
			if not possibilities:
				print "Dead end: " + str(trail)

finder = PathFind(1, 9)
finder.Search()



Unfortunately, it doesn't seem to be giving me the result I was after.
This is the output:



Solution found: [1, 4, 6, 9]
Dead end: [1, 4, 6, 3, 2]
Solution found: [1, 4, 6, 3, 2, 5, 7, 8, 9]
Solutions:
        [1, 4, 6, 9]
        [1, 4, 6, 3, 2, 5, 7, 8, 9]



The problem is the array trail[], which seems to survive from instance
to instance of PathFind(). I thought that by calling self.PathFind
(trail[:]), I was creating a new copy of trail[], but obviously
something isn't running like I expected. Is there something I'm
misunderstanding here, or is there just a stupid bug in my code I
haven't caught?