Minimum number of edges between two vertices of a Graph | Python3 program to find minimum edge between given two vertex of Graph ; function for finding minimum no . of edge using BFS ; visited [ n ] for keeping track of visited node in BFS ; Initialize distances as 0 ; queue to do BFS . ; update distance for i ; function for addition of edge ; Driver Code ; To store adjacency list of graph
import queue NEW_LINE def minEdgeBFS ( edges , u , v , n ) : NEW_LINE INDENT visited = [ 0 ] * n NEW_LINE distance = [ 0 ] * n NEW_LINE Q = queue . Queue ( ) NEW_LINE distance [ u ] = 0 NEW_LINE Q . put ( u ) NEW_LINE visited [ u ] = True NEW_LINE while ( not Q . empty ( ) ) : NEW_LINE INDENT x = Q . get ( ) NEW_LINE for i in range ( len ( edges [ x ] ) ) : NEW_LINE INDENT if ( visited [ edges [ x ] [ i ] ] ) : NEW_LINE INDENT continue NEW_LINE DEDENT distance [ edges [ x ] [ i ] ] = distance [ x ] + 1 NEW_LINE Q . put ( edges [ x ] [ i ] ) NEW_LINE visited [ edges [ x ] [ i ] ] = 1 NEW_LINE DEDENT DEDENT return distance [ v ] NEW_LINE DEDENT def addEdge ( edges , u , v ) : NEW_LINE INDENT edges [ u ] . append ( v ) NEW_LINE edges [ v ] . append ( u ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT n = 9 NEW_LINE edges = [ [ ] for i in range ( n ) ] NEW_LINE addEdge ( edges , 0 , 1 ) NEW_LINE addEdge ( edges , 0 , 7 ) NEW_LINE addEdge ( edges , 1 , 7 ) NEW_LINE addEdge ( edges , 1 , 2 ) NEW_LINE addEdge ( edges , 2 , 3 ) NEW_LINE addEdge ( edges , 2 , 5 ) NEW_LINE addEdge ( edges , 2 , 8 ) NEW_LINE addEdge ( edges , 3 , 4 ) NEW_LINE addEdge ( edges , 3 , 5 ) NEW_LINE addEdge ( edges , 4 , 5 ) NEW_LINE addEdge ( edges , 5 , 6 ) NEW_LINE addEdge ( edges , 6 , 7 ) NEW_LINE addEdge ( edges , 7 , 8 ) NEW_LINE u = 0 NEW_LINE v = 5 NEW_LINE print ( minEdgeBFS ( edges , u , v , n ) ) NEW_LINE DEDENT