Каков наилучший способ реализовать это с помощью некоторого шаблона в C#?

Question

Учитывая структуру данных, представляющую социальную сеть, напишите функцию, которая находит друзей определенной степени. Друзья первой степени являются ближайшими друзьями, друзьями второй степени являются друзья друзей члена, за исключением друзей первой степени и т. Д.

Например, если A является другом с B и B, является другом с C , то GetFriendsOfDegree (A, 2) должен возвращать C, так как C является единственным другом второй степени A (B - друг первой степени A).

Method name: GetFriendsOfDegree 

using System; 
using System.Collections.Generic; 

public class Member 
{ 
    public string Email { get; private set; } 

    public ICollection<Member> Friends { get; private set; } 

    public Member(string email) : this(email, new List<Member>()) 
    { 
    } 

    public Member(string email, ICollection<Member> friends) 
    { 
     this.Email = email; 
     this.Friends = friends; 
    } 

    public void AddFriends(ICollection<Member> friends) 
    { 
     foreach (Member friend in friends) 
      this.Friends.Add(friend); 
    } 

    public void AddFriend(Member friend) 
    { 
     this.Friends.Add(friend); 
    } 
} 

public class Friends 
{ 
    public static List<Member> GetFriendsOfDegree(Member member, int degree) 
    { 
     throw new NotImplementedException("Waiting to be implemented."); 
    } 

    public static void Main(string[] args) 
    { 
     Member a = new Member("A"); 
     Member b = new Member("B"); 
     Member c = new Member("C"); 

     a.AddFriend(b); 
     b.AddFriend(c); 

     foreach (Member friend in GetFriendsOfDegree(a, 2)) 
      Console.WriteLine(friend.Email); 
    } 
} 

Answer 1

Это проблема графа, которая может быть решена с помощью алгоритма breadth-first search. Ваше представление графика как adjacency list хорошо подходит для реализации алгоритма BFS.

Сделать очередь пар (Member, distance) и набор посещенных членов. Нажмите начальный элемент с нулевым расстоянием.

Сделать цикл, который читается из очереди, и проверяет, является ли элемент частью посещенного набора. Если это так, отбросьте пару и продолжайте. В противном случае нажмите всех друзей текущего участника с расстоянием d+1, где d - это расстояние от участника, которого вы удалили.

Когда расстояние достигает целевого расстояния degree, соберите его в список результатов. Продолжайте цикл до тех пор, пока очередь не будет пуста.