c# - Farmer 需要循环遍历自引用动物表的算法

Question

问题:农场里有很多动物。每个动物都可以有任意数量的动物 friend ，反社会动物除外——它们没有属于它们的 friend ，但它们属于其他正常动物的 friend 。每只动物都和它最不快乐的动物 friend 一样快乐，当然，反社会动物除外。反社会动物的幸福水平可以是任何东西。

一天早上，所有的动物都醒来，发现一些反社会动物的情绪发生了变化。农民如何计算出每只动物的幸福度？

这是牧场 worker 的情况(他们没有上过农民学校):

DataTable animals = Select_All_Animals();
foreach (DataRow animal in animals.Rows)
{
    int worstMood = 10; //Super Happy!
    DataTable friendRecords = Select_Comp_Animal_AnimalFriend((int)animal["AnimalID"]);
    foreach (DataRow friend in friendRecords.Rows)
    {
        DataTable animalFriends = Select_AnimalFriend((int)friend["AnimalID_Friend"]);
        foreach (DataRow animalFriend in animalFriends.Rows)
        {
            int animalMood = Get_Animal_Mood((int)animalFriend["Mood"]);
            if (animalMood < worstMood)
            {
                worstMood = animalMood;
            }
        }
    }
}

但这行不通，因为动物表并不按顺序遵循已形成的动物 friend 层次结构。动物可以随时交 friend !所以 Animal(1) 可能有 Animal(4000) 作为 friend 。 Animal(1) 不会显示准确的心情，因为它会在 Animal(4000) 的心情更新之前检查 Animal(4000) 的心情。每天都有新动物掉落。我认为解决方案可能是一种常见的算法设计，但我一直没能找到它。我不相信我有正确的术语来准确地搜索它。

非常感谢，如果这个问题已经得到解答，我们深表歉意!

添加:

这是可能关系的 ghetto Paint 图表:

反社会动物处于底层，没有属于他们的 friend 。正常的动物在上面的其他地方。正常的动物友谊没有确切的结构，除了(正如塞巴斯蒂安指出的那样)不能有一个闭环(如果设计正确)。

每周将添加数十万只动物，处理速度是一个关键因素。

Answer 1

首先抓取所有反社会动物，并按照从最不快乐到最快乐的顺序排列它们。将所有群居动物的幸福度初始化为最大(这使一切变得更容易，因为您不必检测以前不快乐的动物何时变得更快乐)。然后遍历列表并将幸福水平传播到友谊链上:

void UpdateFarm()
{
    // Start with a list of antisocial animals from least to most happy.
    var antisocialAnimals = GetAntisocialAnimals().OrderBy(x => x.Happiness);

    // Initialise the social animals to the global maximum. Note the
    // global maximum is the happiest antisocial animal. This is done to
    // avoid the case where an antisocial animal's happiness has increased,
    // so some of the social animals are too unhappy.
    var maxHappiness = antisocialAnimals.Last().Happiness;
    var socialAnimals = GetSocialAnimals();
    foreach (var socialAnimal in socialAnimals)
        socialAnimal.Happiness = maxHappiness;

    // Now iterate from least to most happy, propagating up the friend chain.
    foreach (var antisocialAnimal in antisocialAnimals)
        UpdateFriends(antisocialAnimal);
}

// To propagate a happiness change, we just find all friends with a higher
// happiness and then lower them, then find their friends and so on.
void UpdateFriends(Animal animal)
{
    var friends = GetFriends(animal); // Friends with this animal, not friends of.

    foreach (var friend in friends.Where(x => x.Happiness > animal.Happiness))
    {
        friend.Happiness = animal.Happiness;

        // Since this friend's happiness has changed, we now need to update
        // its friends too.
        UpdateFriends(friend);
    }
}