-1

给定一个表示社交网络的数据结构，编写一个找到一定程度的朋友的函数。一级好友为会员的直系好友，二级好友为会员好友除一级好友外的好友，以此类推。

例如，如果 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);
    }
}
4

1 回答 1

1

这是一个可以用广度优先搜索算法解决的图问题。您将图表示为邻接列表非常适合实现 BFS 算法。

制作一个队列对(Member, distance)，以及一组访问过的成员。推动距离为零的初始成员。

创建一个从队列中读取的循环，并检查成员是否是访问集的一部分。如果是，请丢弃该对并继续。否则，以 的距离推送当前成员的所有朋友d+1，其中d是您已出队的成员的距离。

当距离达到 的目标距离时degree，将成员收集到结果列表中。继续循环，直到队列为空。

于 2015-08-23T21:19:40.283 回答