TheAlgorithms
Bug in `graphs/breadth_first_search.py`
As you can see in the code below:
https://github.com/TheAlgorithms/Python/blob/f31fa4ea7e26d8721be7e966ecf92fcbd87af65f/graphs/breadth_first_search.py#L25-L38
this code only works for directed graphs and the BFS algorithm is wrong. For example in this minimal example:
g = Graph()
g.add_edge(0, 1)
print(g.bfs(1))
You will get a KeyError: 1 because the node number 1 has not been added to the self.verices.
If you look closer, this code will raise a error too even when the graph is not directed:
g = Graph()
g.add_edge(0, 1)
print(g.bfs(0))
Cause in the BFS algorithm, when it reaches to node number 1, the previous problem appears here too.
This code is a little bugy and It should have stronger tests. Also the graphs/breadth_first_search_2.py file can be merged with this one too.
Please assign fixing this issue to me if I'm right about this problem.
You can work with both directed and undirected graphs (if an undirected graph has edge(a,b) then simply puts edge(b, a)) using same code. So why does this code need to be fixed ?
In the second example, beside the graph is directed or not, You will get an error.
Also in the common algorithms, adding edge means bidirectional edge so maybe a just renaming the class to DirectedGraph is enough.
I just added support for the non-directed graph by editing the add-edge function and adding a new function to carry out non-directional graphs routines.
class Graph:
def __init__(self, directed=True):
# ...
def operation_for_nondirected(self, possibly_mono_connected_vertex: int) -> None:
"""
>>> g = Graph(directed=False)
>>> g.add_edge(0, 1)
>>> g.print_graph()
0 : 1
"""
if self._directed is False:
if possibly_mono_connected_vertex not in self.vertices:
self.vertices[possibly_mono_connected_vertex] = []
def add_edge(self, from_vertex: int, to_vertex: int) -> None:
"""
adding the edge between two vertices
>>> g = Graph()
>>> g.print_graph()
>>> g.add_edge(0, 1)
>>> g.print_graph()
0 : 1
"""
# minor change here
from_v = self.vertices[from_vertex] = self.vertices.get(from_vertex, [])
from_v.append(to_vertex)
# what to do if the graph itself is non-directed
self.operation_for_nondirected(to_vertex)
@itsamirhn
If multiple contributors submit solutions to the same algorithm, it is usually a learning experience for all parties. Therefore, we review pull requests and do not assign or reserve algorithms.
