# HW #4 Implement the Graph DFS Data Structure using STACK PYTHON # Name: class
ID: 3917360 • Letter: #
Question
# HW #4 Implement the Graph DFS Data Structure using STACK PYTHON # Name: class Node: def __init__(self, value): self.value = value self.next = None def __str__(self): return "Node({})".format(self.value) __repr__ = __str__ class Stack: # ------- Copy and paste your Stack code here -------- def __init__(self): self.top = None self.next = next self.count = 0 def __str__(self): temp = self.top out = '' while temp: out += str(temp.value) + ' ' temp = temp.next return ('Top:{} Stack: {}'.format(self.top, out)) __repr__ = __str__ def isEmpty(self): # write your code here return self.top == None def size(self): # write your code here return self.count def peek(self): # write your code here if self.top == None: return "Stack is Empty" else: return self.top.value def push(self, value): # write your code here new_node = Node(value) new_node.next = self.top self.top = new_node self.count += 1 def pop(self): # write your code here if self.isEmpty(): return "Stack is Empty" else: previous = self.top self.top = self.top.next self.count -= 1 return previous.value # ------- Stack code ends here -------- class Vertex: def __init__(self, value): self.value = value self.connectedTo = {} def addNeighbor(self, node, weight=1): self.connectedTo[node] = weight def __str__(self): return str(self.value) + ': ' + str([x.value for x in self.connectedTo]) class Graph: def __init__(self): self.vertList = {} def __iter__(self): return iter(self.vertList.values()) def getVertex(self, key): if key in self.vertList: return self.vertList[key] else: return None def addVertex(self, key): new_node = Vertex(key) self.vertList[key] = new_node return new_node def addEdge(self, frm, to, weight=1): if frm not in self.vertList: new_node = self.addVertex(frm) if to not in self.vertList: new_node = self.addVertex(to) self.vertList[frm].addNeighbor(self.vertList[to], weight) def dfs(self, start): # ---- Write your code here
Explanation / Answer
def dfs_rec(graph, ver, path=[]): path += [ver] for neigh in graph[ver]: if neigh not in path: path = dfs_rec(graph, neigh, path) return path adj_mat = {1: [2, 3], 2: [4, 5], 3: [5], 4: [6], 5: [6], 6: [7], 7: []} print(dfs_rec(adj_mat, 1)) # [1, 2, 4, 6, 7, 5, 3]
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.