Dec-01-2018, 08:38 PM
Hello Python-Forum,
I'm new to this Forum and very new to Python and programming itself.
We got a homework in our course where we have to implement the breadth-first-search in Python. We also got a script which we have to fill. We have to use classes.
My fellow students and my have got some really big problems with this homework :(
I hope you can help us to solve this task.
Here is the code we got to fill:
I'm new to this Forum and very new to Python and programming itself.
We got a homework in our course where we have to implement the breadth-first-search in Python. We also got a script which we have to fill. We have to use classes.
My fellow students and my have got some really big problems with this homework :(
I hope you can help us to solve this task.
Here is the code we got to fill:
import math, queue class Graph: ''' Class Graph. Implements an undirected graph, in the form {v: [w1,w2]} for edges (v,w1), (v,w2), i.e., adjacency lists. Provides a dict "node", with the nodes as keys, to save additional attributes.''' def __init__(self): self.graph = {} self.node = {} def __iter__(self): '''allows to iterate over nodes by "for v in class instances".''' return iter(self.graph) def __len__(self): '''returns the number of nodes as len(class instance)''' return(len(self.graph)) def add_nodes(self, L): '''adds all nodes in list L to graph and intializes their node dict''' #TODO pass def has_edge(self, e): '''returns True if the tuple e is an edge, False otherwise''' #TODO pass def add_edges(self, L): '''adds all edge-tuples in the list L to the graph''' #TODO pass def number_of_edges(self): '''returns the number of edges in the graph''' #TODO pass def neighbours(self,v): '''returns a list of all neighbours of v''' #TODO pass def BFS_init(G, s): '''Initializes node dicts in graph class G for color, distance, and predecessor.''' for v in G: G.node[v]['color'] = 'white' G.node[v]['dist'] = float('inf') G.node[v]['pi'] = None G.node[s]['color'] = 'gray' G.node[s]['dist'] = 0 def BFS(G, s): '''Function BFS. Expects a graph class with node attributes and starting node s. Implements BFS and saves distances in corresponding node dicts.''' BFS_init(G, s) #TODOBest regards