Find number of connections of person till nth level

This is typical social network problem, where one has to find all friends of a person who are at max n distance away from person. In other words, friends of person are at 1st level, friends of friends of p are at 2nd level and so on. This question was asked recently in Microsoft interview.

For example, in below graph, if we have to find connections of node 1 till 3rd level, result will :

connections till nth level

Level 1 : 2,3,4 (friends)
Level 2 : 5,6,7,8 (friends of friends)
Level 3 : 9,10,11

Find friends of a person till Kth level

The standard way to find connections or friends in graphs is to do breadth first search on graph. Start BSF from the person given, till you have visited nodes with max k distance from starting node. Only extra thing needs to be done other than standard breadth first search is to keep track of number of levels we have moved.

Implementation is quite simple.

Complexity of algorithm to find friends of person till nth level is O( |V| + |E|) where V are number of vertices and E is number of edges in graph representation of person’s social network.