-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathdfs.py
More file actions
65 lines (54 loc) · 1.64 KB
/
Copy pathdfs.py
File metadata and controls
65 lines (54 loc) · 1.64 KB
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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
"""Depth First Search on a graph"""
from sets import Set
from linked_list import Node
class lightStack(object):
"""Simple stack"""
def __init__(self):
self.head = None
def push(self, lst):
"""Push a list of nodes"""
for obj in lst:
new = Node(obj)
new.nextn = self.head
self.head = new
def pop(self):
"""Returns the top of the stack and then removes it"""
if self.head:
popped = self.head
self.head = popped.nextn
return popped.data
else:
raise IndexError('Popping from empty stack')
def top(self):
"""Returns the top of the stack"""
if self.head:
return self.head.data
else:
raise IndexError('Stack is empty')
def isEmpty(self):
"""Returns True if the the stack is empty, False otherwise"""
if self.head:
return False
else:
return True
def dfsTraverse(graphDict, start):
"""Returns a tuple with the nodes traversed in DFS order"""
stack = lightStack()
notVisited = Set(graphDict.keys())
stack.push([start])
notVisited.remove(start)
result = [start]
while not stack.isEmpty():
curNode = stack.top()
neighbours = graphDict[curNode]
nextNode = 'z'
for node in neighbours:
if node < nextNode and node in notVisited:
nextNode = node
if nextNode != 'z':
stack.push(nextNode)
result.append(nextNode)
notVisited.remove(nextNode)
else:
stack.pop()
return tuple(result)