拓扑排序及其实际应用

    public class Node
    {
        /// <summary>
        /// 当前节点ID
        /// </summary>
        public int Key { get; set; }

        /// <summary>
        /// 父级节点ID
        /// </summary>
        public int? Parent { get; set; }
    }

/// <summary>
    /// 递归判断是否存在循环引用
    /// </summary>
    public class RecursionSort
    {
        /// <summary>
        /// 递归判断是否存在循环引用
        /// </summary>
          public  static bool CheckRecursion(List<Node> list)
        {
            foreach (var node in list)
            {
                if (RecursionSort.CheckRecursion(node.Key,node, list))
                {
                    return true;
                }
            }
            return false;
        }

        /// <summary>
        /// 递归判断是否存在循环引用
        /// </summary>
        /// <param name="list"></param>
        /// <returns></returns>
        private static bool CheckRecursion(int key,Node curNode, List<Node> list)
        {
            if (curNode.Parent == key)
            {
                return true;
            }
            //寻找父级节点对应的父级节点信息
            if (curNode.Parent != null)
            {
                Node pNode = list.Where(e => e.Key == curNode.Parent).FirstOrDefault<Node>();
                return CheckRecursion(key,pNode, list);
            }
            return false;
        }
    }

        static void Main(string[] args)
        {
            //递归判断
            List<Node> list = new List<Node>();
            list.Add(new Node { Key=1,Parent=2});
            list.Add(new Node { Key = 2, Parent = 1 });
            list.Add(new Node { Key = 3, Parent = 2 });
            Console.WriteLine(RecursionSort.CheckRecursion(list));
            Console.Read();
        }

    /// <summary>
    /// 拓扑节点类。
    /// </summary>
    public class TopologicNode<T>
    {
        /// <summary>
        /// 获取或设置节点的键值。
        /// </summary>
        public T Key { get; set; }

        /// <summary>
        /// 获取或设置依赖节点的键值列表。
        /// </summary>
        public List<T> Dependences { get; set; }
    }

 /// <summary>
    /// 拓扑排序类。
    /// </summary>
    public class TopologicSort
    {
        /// <summary>
        /// 拓扑顺序。
        /// </summary>
        /// <typeparam name="TKey">节点的键值类型。</typeparam>
        /// <param name="list">一组节点。</param>
        /// <returns>拓扑序列。</returns>
        /// <exception cref="InvalidOperationException">如果存在双向引用或循环引用，则抛出该异常。</exception>
        public static List<T> OrderBy<T>(List<TopologicNode<T>> list)
        {
            if (list == null)
            {
                throw new ArgumentNullException("参数空异常");
            }
            List<T> listResult = new List<T>();
            while (list.Count > 0)
            {
                //查找依赖项为空的节点
                var item = list.FirstOrDefault(c => c.Dependences == null || c.Dependences.Count == 0);
                if (item != null)
                {
                    listResult.Add(item.Key);

                    //移除用过的节点，以及与其相关的依赖关系
                    list.Remove(item);
                    foreach (var otherNode in list)
                    {
                        if (otherNode.Dependences != null)
                        {
                            otherNode.Dependences.Remove(item.Key);
                        }
                    }
                }
                else if (list.Count > 0)
                {
                    //如果发现有向环，则抛出异常
                    throw new InvalidOperationException("存在循环引用");
                }
            }
            return listResult;
        }
    }

 //拓扑排序
            //节点3依赖于2和1节点
            list.Add(new Node { Key = 3, Parent = 1 });

            List<TopologicNode<int>> listTopologicNode = new List<TopologicNode<int>>();
            //构建排序节点

            var group = (from p in list
                         group p by p.Key into g
                         select g);

            foreach (var g in group)
            {
                TopologicNode<int> node = new TopologicNode<int>();
                node.Key = g.Key;
                node.Dependences = new List<int>();
                foreach (Node value in g)
                {
                    if (value.Parent != null)
                    {
                        node.Dependences.Add(value.Parent.GetValueOrDefault());
                    }
                }
                listTopologicNode.Add(node);
            }

            try
            {
                List<int> result = TopologicSort.OrderBy<int>(listTopologicNode);
                result.ForEach(e => {
                    Console.WriteLine(e);
                });
            }
            catch (Exception ex)
            {
                Console.WriteLine(ex.Message);
            }