algorithm - 对象中循环引用的最佳检测(目前是暴力破解)

Question

我有一个 Product对象，它可以依赖于其他产品。

此依赖信息存储在 ServiceTemplate 中对象。

这些依赖关系可以被链接起来(我用箭头表示3依赖2，2依赖1):

1 <= 2 <= 3

我需要防止循环引用，上面的 1 可以设置为依赖于 3，这会导致循环。

这是根据我认为它可能工作的方式进行的散列，但它是暴力强制解决方案 - 最佳算法方法是什么，或者这已经是最好的方法了吗？

class Program
{
    class Product
    {
        public Product(int id)
        {
            this.id = id;
        }

        private readonly int id;

        public int Id { get { return this.id; } }
    }

    class ServiceTemplate
    {
    // stores the list of other products that a product depends on
        Dictionary<int, List<int>> relationships = new Dictionary<int, List<int>>();

        public void SetRequires(Product on, Product requires)
        {
            if (WouldCauseCircularDepdndency(on.Id, requires.Id) == true)
                throw new ArgumentException("circular dependencies not allowed");

            List<int> list = null;
            this.relationships.TryGetValue(on.Id, out list);

            if(list==null)
            {
                list = new List<int>();
                this.relationships.Add(on.Id, list);
            }

            list.Add(requires.Id);
        }

        private bool WouldCauseCircularDepdndency(int on, int requires)
        {
            // get relationships of product we will depend on
            List<int> list = null;                    
            this.relationships.TryGetValue(requires, out list);

            if (list == null)
            {
                return false;
            }
            else if (list.Contains(on))
            {
                return true;
            }
            else
            {
                foreach (var id in list)
                {
                    // traverse each child recursively
                    if (WouldCauseCircularDepdndency(on, id))
                        return true;
                }
            }

            return false; // if we got this far, no circular references detected
        }
    }

    static void Main(string[] args)
    {
        var windows = new Product(1);
        var linux = new Product(2);
        var mySql = new Product(3);
        var ms_sql = new Product(4);
        var cluster = new Product(5);
        var other = new Product(6);

        var config = new ServiceTemplate();
        config.SetRequires(mySql, windows); // mySql requires windows
        config.SetRequires(mySql, linux); // mySql requires linux
        config.SetRequires(ms_sql, windows); // microsoft sql requires windows
        config.SetRequires(cluster, ms_sql); // cluster requires microsoft sql
        config.SetRequires(other, cluster);

        // this should throw an exception due to circular dependency
        config.SetRequires(windows, other);

        /* at this point the config relationships dictionary is as follows:

        3 => 1,2
        4 => 1
        5 => 4
        5 => 6
        1 => 6

        */
    }
}

Answer 1

你可以试试 topological sorting .如果它可以构造，你就没有循环依赖。否则，你有一个循环。