Sep-25-2019, 01:56 AM
(This post was last modified: Sep-25-2019, 01:56 AM by ichabod801.)
Look at the first wrong edge in the output: (3, 4). There is no such edge in your graph. How did it get that? When you add (1, 3), you change w to 3, but your for loop is still looping over the edges from 1. The next edge is (1, 4), but since you've changed w to 3, it stores it as (1, 4).
I don't understand how this algorithm is supposed to be working. I skipped that chapter when I read Discrete Mathematics because I'd done it with Introduction to Algorithms. That book uses a recursive search, which was my first instinct. I think to get it working without recursion you are going to have to reset your tracking variables a lot. When you change w, you have to change the list of edges you are going through. And when you go back after hitting a dead end I think you will need to reset i as well.
Edit: This gets the correct list of edges, just in a different order, and without recursion. It could probably be more efficient.
I don't understand how this algorithm is supposed to be working. I skipped that chapter when I read Discrete Mathematics because I'd done it with Introduction to Algorithms. That book uses a recursive search, which was my first instinct. I think to get it working without recursion you are going to have to reset your tracking variables a lot. When you change w, you have to change the list of edges you are going through. And when you go back after hitting a dead end I think you will need to reset i as well.
Edit: This gets the correct list of edges, just in a different order, and without recursion. It could probably be more efficient.
input_graph = {1:[3,4,8,9,11], 2:[3,8,12], 3:[1,2,5,11], 4:[1,6,9,10], 5:[3,12], 6:[4,10], 7:[8,12], 8:[1,2,7,10], 9:[1,4,11], 10:[4,6,8], 11:[1,3,9], 12:[2,5,7]} def DFS(graph, root): visited = set([root]) current = root edges = [] while len(visited) < len(graph): possible = [node for node in graph[current] if node not in visited] if possible: edges.append((current, possible[0])) visited.add(possible[0]) current = possible[0] else: current = [start for start, end in edges if end == current][0] return edges print(DFS(input_graph, 1))
Craig "Ichabod" O'Brien - xenomind.com
I wish you happiness.
Recommended Tutorials: BBCode, functions, classes, text adventures
I wish you happiness.
Recommended Tutorials: BBCode, functions, classes, text adventures