[Solved]Goal Module 6 Discussed Graph Data Structure Since Graph Non Linear Structure Unique Trave Q37202802
Goal: In Module 6, we discussed the Graph data structure. Sincethe graph is a non-linear structure, there is no unique traversal.Nodes can be found using Breadth-First Search (visit the siblingnodes before visiting the child nodes) and Depth-first search(visit the child nodes before visiting the sibling nodes). Based onthe implementation of the Graph data structure discussed during ourlecture (provided in the starter code):
1. Create the method bfs(start). This method takes the key ofthe starting node and performs Breadth-first search in an instanceof the class Graph. This method must return a list that containsthe order in which the nodes where accessed during the search(following alphabetical order when discovering nodes). You must useyour queue code from LAB 11 in order to produce your result. If youdon’t use the queue, your will not receive credit for theassignment
2. Create the method dfs(start). This method takes the key ofthe starting node and performs Depth-first search in an instance ofthe class Graph. This method must return a list that contains theorder in which the nodes where accessed during the search(following alphabetical order when discovering nodes). You must useyour stack code from LAB 10 in order to produce your result. If youdon’t use the stack, your will not receive credit for theassignment
Grading Notes:
– A random instance of the Graph class (directed or undirected,weighted or unweighted) will be created and the bfs and dfs methodswill be called on 4 different starting nodes for 12.5 pts each.Make sure you use the Graph data structure provided in the startercode, otherwise, no credit will be given.
– Vertices and edges will be provided in random order(non-alphabetical order). The final result should be only the oneprovided by following alphabetical order.
EXAMPLE: Note that this is only an example, the fact that youcode produces the example’s output does not ensure your code worksproperly. Test your code with several examples!
g1 = {‘A’: [‘B’,’D’,’G’], ‘B’: [‘A’,’E’,’F’], ‘C’: [‘F’], ‘D’:[‘A’,’F’], ‘E’: [‘B’,’G’], ‘F’: [‘B’,’C’,’D’], ‘G’: [‘A’,’E’]}
>>> g=Graph(g1)
>>> g.bfs(‘A’)
[‘A’, ‘B’, ‘D’, ‘G’, ‘E’, ‘F’, ‘C’]
>>> g.dfs(‘A’)
[‘A’, ‘B’, ‘E’, ‘G’, ‘F’, ‘C’, ‘D’]
g2 = {‘F’: [‘D’,’C’,’B’], ‘A’: [‘G’,’D’,’B’], ‘B’: [‘F’,’A’,’E’],’E’: [‘G’,’B’], ‘C’: [‘F’], ‘D’: [‘F’,’A’], ‘G’: [‘A’,’E’]}
>>> g=Graph(g2)
>>> g.bfs(‘A’)
[‘A’, ‘B’, ‘D’, ‘G’, ‘E’, ‘F’, ‘C’]
>>> g.dfs(‘A’)
[‘A’, ‘B’, ‘E’, ‘G’, ‘F’, ‘C’, ‘D’]
g3 = {‘B’: [(‘E’,3),(‘C’,5)], ‘F’: [], ‘C’: [(‘F’,2)], ‘A’:[(‘D’,3),(‘B’,2),], ‘D’: [(‘C’,1)], ‘E’: [(‘F’,4)]}
>>> g=Graph(g3)
>>> g.bfs(‘A’)
[‘A’, ‘B’, ‘D’, ‘C’, ‘E’, ‘F’]
>>> g.dfs(‘A’)
[‘A’, ‘B’, ‘C’, ‘F’, ‘E’, ‘D’]
starter code:
actual code needed to be written: bfs, dfs, and dijkstramethods
# copy your code from abs 1e and 11 here (you can remove their com #1a610 code class Node: def_init_(self, value): self.value value self.nextNone def_str(self): return “Node()”.format (self.value) str repr class Stack: def_init_(self): self.top None def_str(self): temp-self.top out- while temp: out.append (str(temp.value)) temp-temp.next out-‘In’.join(out) return (‘Top:(InStack:Inf’.format(self.top,out)) repr str def isEmpty (self): return self.topNone def_len_(self): if self.isEmpty(): return else: temp self.top count- while(temp): count+-1 def_len_(self): if self.isEmpty(): return else: temp self.top count- while(temp): count+-1 temp temp.next return count def peek (self): return self.top.value ef push (self, value): newNodeNode (value) if self.isEmpty(): self.top-newNode else: newNode.nextself.top self.topnewNode def pop(self): if self.isEmpty) return ‘Stack is empty else: removed_valueself.top.value self.top self.top.next return removed value #1a611 code class Queue: def_init_(self): self.head-None self.tail-None def_str(self): temp-self.head out- while temp: out.append (str(temp.value)) class Queue: def_init_(self): self.head-None self.tail-None def_str(self): temp-self.head out- while temp: out.append (str(temp.value)) temp-temp.next out-‘ ‘.join(out) return (‘Head:(nTail:nQueue:(.format (self.head,self.tai repr str def isEmpty (self): if self.head is None: return True return False def_len_(self): if self.isEmpty) return else: temp self.head count while(temp): count+-1 temp temp.next return count ef enqueue (self, value): newNodeNode (value) if self.isEmpty) self.headnewNode self.tail -newNode else: self.tail.next newNode self.tail – newNode #Due Date: 04/26/2019, 11:59PM # Name: # Collaboration Statement # Copy your code from labs 10 and 11 here [you can remove their comments) # Hi/6Graph code lass Graph , def init(self, graph_repr) self.veroListgraphrepr def bfsself, sart): # Your code starts here def dfsself, seart) # Your code starts here ### EXTRA CREDIT, uncomment method definition if submitting extra credit #def dijkstra(self,start): # Your code starts here Show transcribed image text # copy your code from abs 1e and 11 here (you can remove their com #1a610 code class Node: def_init_(self, value): self.value value self.nextNone def_str(self): return “Node()”.format (self.value) str repr class Stack: def_init_(self): self.top None def_str(self): temp-self.top out- while temp: out.append (str(temp.value)) temp-temp.next out-‘In’.join(out) return (‘Top:(InStack:Inf’.format(self.top,out)) repr str def isEmpty (self): return self.topNone def_len_(self): if self.isEmpty(): return else: temp self.top count- while(temp): count+-1
def_len_(self): if self.isEmpty(): return else: temp self.top count- while(temp): count+-1 temp temp.next return count def peek (self): return self.top.value ef push (self, value): newNodeNode (value) if self.isEmpty(): self.top-newNode else: newNode.nextself.top self.topnewNode def pop(self): if self.isEmpty) return ‘Stack is empty else: removed_valueself.top.value self.top self.top.next return removed value #1a611 code class Queue: def_init_(self): self.head-None self.tail-None def_str(self): temp-self.head out- while temp: out.append (str(temp.value))
class Queue: def_init_(self): self.head-None self.tail-None def_str(self): temp-self.head out- while temp: out.append (str(temp.value)) temp-temp.next out-‘ ‘.join(out) return (‘Head:(nTail:nQueue:(.format (self.head,self.tai repr str def isEmpty (self): if self.head is None: return True return False def_len_(self): if self.isEmpty) return else: temp self.head count while(temp): count+-1 temp temp.next return count ef enqueue (self, value): newNodeNode (value) if self.isEmpty) self.headnewNode self.tail -newNode else: self.tail.next newNode self.tail – newNode
#Due Date: 04/26/2019, 11:59PM # Name: # Collaboration Statement # Copy your code from labs 10 and 11 here [you can remove their comments) # Hi/6Graph code lass Graph , def init(self, graph_repr) self.veroListgraphrepr def bfsself, sart): # Your code starts here def dfsself, seart) # Your code starts here ### EXTRA CREDIT, uncomment method definition if submitting extra credit #def dijkstra(self,start): # Your code starts here
Expert Answer
Answer to Goal: In Module 6, we discussed the Graph data structure. Since the graph is a non-linear structure, there is no unique … . . .
OR
