Levels of Friendship

The Degrees of Friendship problem is a prominent topic in graph theory and networking. Essentially, this problem involves determining the "relationships" or connections between various points in a network graph, particularly focusing on the distances between these points (or nodes). In the context of interviews, an algorithmic question related to Degrees of Friendship may ask you to develop a program or function that evaluates the "degree of friendship" between each pair of points in a specified network. For instance, if you are provided with an array of two-element subarrays, each representing a pair of friends, you could be tasked with generating a matrix that indicates the degrees of friendship for all potential pairs of friends.

For this illustration, let's consider that you have been provided with an array representing friendships like this: friends = [ [ 'A' , 'B' ] , [ 'B' , 'C' ] , [ 'C' , 'D' ] , [ 'D' , 'E' ] , [ 'E' , 'F' ] , [ 'F' , 'G' ] ] Initially, I would construct a dictionary where each friend serves as a key, and the corresponding value is a list of their direct friends. Following that, I would implement a function that employs the Breadth-first search (BFS) algorithm to find the shortest connection between two friends. def degrees_of_friendship ( friends ) : graph = { f : [ ] for sub in friends for f in sub } for f1 , f2 in friends : graph [ f1 ] . append ( f2 ) graph [ f2 ] . append ( f1 ) return graph def BFS ( graph , start , end ) : visited = set ( ) queue = [ ( start , [ start ] ) ] while queue : ( vertex , path ) = queue . pop ( 0 ) if vertex not in visited : if vertex == end : return len ( path ) - 1 visited . add ( vertex ) for neighbor in graph [ vertex ] : queue . append ( ( neighbor , path + [ neighbor ] ) ) The BFS function will yield the degree of friendship between any two specified friends.

Let's examine a somewhat intricate situation where we have the following array of friendships: friends = [ [ 'A' , 'B' ] , [ 'A' , 'C' ] , [ 'B' , 'D' ] , [ 'C' , 'D' ] , [ 'D' , 'E' ] , [ 'C' , 'F' ] , [ 'E' , 'F' ] , [ 'E' , 'G' ] , [ 'F' , 'H' ] ] We will utilize the same function as previously, but we will enhance it with a nested loop to determine all pairs of friends. def degrees_of_friendship ( friends ) : graph = { f : [ ] for sub in friends for f in sub } for f1 , f2 in friends : graph [ f1 ] . append ( f2 ) graph [ f2 ] . append ( f1 ) def BFS ( graph , start , end ) : visited = set ( ) queue = [ ("("span>start , [ start )] ) ] while queue : ( vertex , path ) = queue . pop ( 0 ) if vertex not in visited : if vertex == end : return len ( path ) - 1 visited . add ( vertex ) for neighbor in graph [ vertex ] : queue . append ( ( neighbor , path + [ neighbor ]) ) all_friends = list ( graph . keys ( ) ) matrix = [ ] for f1 in all_friends : row = [ ] for f2 in all_friends : row . append ( BFS ( graph , f1 , f2 ) ) matrix . append ( row ) return matrix This function will produce a matrix indicating the degree of friendship among all friends.