[PYTHON] - GRAPHS ALGORITHMS STACKS SEARCH Instructions: In class, we discussed

Question

[PYTHON] - GRAPHS ALGORITHMS STACKS SEARCH

Instructions: In class, we discussed the Graph data structure. Since the graph is a non-linear structure, there is no unique traversal. Nodes can be found using Breadth-First Search (visit the sibling nodes before visiting the child nodes) and Depth-first search (visit the child nodes before visiting the sibling nodes). We also discussed how a graph implementation can be used to compute the shortest path using Dijkstra's algorithm Based on the code we did in class (provided in the starter code): 1. Create the method dfs(start). This method takes the key of the starting node and performs Depth-first search in an instance of the class Graph. This method must return a list that contains the order in which the nodes where access during the search 2. You must ensure your stack from LAB 10 works properly, as you must use that stack to produce your result (refer to the slides on how the stack helps you to keep track of the nodes during the traversal) 3. Create the method dijkstra(start). This method takes the key of the starting node and runs Dijkstra's algorithm in an instance of the class Graph. The method returns a dictionary with the value of the shortest path from the starting node to every other node reachable from start Notes: To you follow the alphabetical convention for DFS, you have two options: 1) provide the vertices in alphabetical order and add the edges in alphabetical order or 2) provide vertices and edges in random order and sort them in your method. You are free to add method that might help you to achieved the stated goal - -

Explanation / Answer

def dfs(self,start) :
begin=self.getvertex(start)
seen=[begin]
visited=[]
stack=[begin]
while stack :
vertex=stack.pop()
if vertex not in seen :
visited.append(vertex.value)
for v in vertex.connectedto :
if v is not in seen :
seen.append(v)
stack.append(v)
return visited
def dijkastra(self,graph) :
start=self.getvertex(start)
isvisited = {initial: 0}
path = {}
nds = set(graph.Node)
while nds:
minnds = None
for node in nds:
if node in visited:
if mnode is None:
mnode = node
elif isvisited[node] < isvisited[mnode]:
mnode = node
if mnode is None:
break
nds.remove(mnode)
curr_w = isvisited[mnode]
for edge in graph.edges[mnode]:
weight = curr_w + graph.distance[(mnode, edge)]
if edge not in isvisited or weight < isvisited[edge]:
isvisited[edge] = weight
path[edge] = min_node
return path

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.