刘凡 3282579ec1 first commit | 2 tahun lalu | |
---|---|---|
.. | ||
README.md | 2 tahun lalu | |
bfs.py | 2 tahun lalu | |
input.txt | 2 tahun lalu |
Input is taken from the file
Sample input
4
0 5 10 5
0 0 5 0
0 10 0 0
0 0 10 0
0
First line contains the number of nodes,say n.(Nodes are numbered as 0,1,2,...(n-1) ) Followed by n*n weighted matrix. Disconnected egdes are represented by negative weight. Last line contains the source node.(i.e, the node from which the BFS should begin)
Graph is first drawn from the weighted matrix input from the user with weights shown. Edges are marked with black. visualization of the input graph-
Iterative BFS is performed, using a queue. Each time an edge is encountered, it is marked with red on the graph through the line -
nx.draw_networkx_edges(G,pos,edgelist=[(curr_node,i)],width=2.5,alpha=0.6,edge_color='r')
Time: 0(m+n)
where m - number of edges
n - number of nodes