C#有向图拓扑排序

    /// <summary>

    /// 图的节点类

    /// </summary>

    public class GraphNode

    {

        private int inDegree;

        private int outDegree;

        private string nodeName;

        /// <summary>

        /// 节点入度

        /// </summary>

        public int InDegree

        {

            set { inDegree = value; }

            get { return inDegree; }

        }

        /// <summary>

        /// 节点出度

        /// </summary>

        public int OutDegree

        {

            set { outDegree = value; }

            get { return outDegree; }

        }

        /// <summary>

        /// 节点名称

        /// </summary>

        public string NodeName

        {

            get { return nodeName; }

        }

        /// <summary>

        /// 构造函数

        /// </summary>

        public GraphNode()

        {

        }

        /// <summary>

        /// 构造函数

        /// </summary>

        /// <param name='nodeName'>节点名称</param>

        public GraphNode(string nodeName)

        {

            this.nodeName = nodeName;

        }

    }

    /// <summary>

    /// 有向图的排序算法类

    /// </summary>

    public class GraphDirecTopoSorted

    {

        private List<GraphNode> nodeList;   //节点链表

        private List<KeyValuePair<GraphNode, GraphNode>> edgeList;  //边链表

        /// <summary>

        /// 构造函数

        /// </summary>

        /// <param name='node'>节点链表</param>

        /// <param name='edge'>边链表</param>

        public GraphDirecTopoSorted(List<GraphNode> node, List<KeyValuePair<GraphNode, GraphNode>> edge)

        {

            this.nodeList = node;

            this.edgeList = edge;

        }

        /// <summary>

        /// 计算节点的入度出度

        /// </summary>

        private void NodeInOutDegree()

        {

            foreach (GraphNode node in nodeList)

            {

                int inDegree = 0;

                int outDegree = 0;

                foreach (KeyValuePair<GraphNode, GraphNode> edge in edgeList)

                {

                    if (edge.Value.NodeName == node.NodeName)

                    {

                        inDegree++;

                    }

                    if (edge.Key.NodeName == node.NodeName)

                    {

                        outDegree++;

                    }

                }

                node.InDegree = inDegree;

                node.OutDegree = outDegree;

            }

        }

        /// <summary>

        /// 是否有环路，有则返回NULL，否则返回入度为零的节点

        /// </summary>

        /// <returns>入度为零的节点</returns>

        private GraphNode HaveCycle()

        {

            GraphNode tempNode = new GraphNode();

            NodeInOutDegree();

            foreach (GraphNode node in nodeList)

            {

                if (node.InDegree == 0)

                {

                    tempNode = node;

                }

            }

            return tempNode;

        }

        /// <summary>

        /// 删除节点对应的边

        /// </summary>

        /// <param name='node'>节点</param>

        private void RemoveGraphEdge(GraphNode node)

        {

            for (int i = 0; i < edgeList.Count; )

            {

                if (edgeList[i].Key == node)

                {

                    edgeList.RemoveAt(i);

                }

                else

                {

                    i++;

                }

            }

        }

        /// <summary>

        /// 有向图的排序

        /// </summary>

        /// <returns>排序后的节点链表</returns>

        public List<GraphNode> TopoSorted()

        {

            List<GraphNode> sortResult = new List<GraphNode>();

            while (nodeList.Count > 0)

            {

                GraphNode tempNode = HaveCycle();

                if (tempNode != null)

                {

                    sortResult.Add(tempNode);

                    nodeList.Remove(tempNode);

                    RemoveGraphEdge(tempNode);

                }

            }

            return sortResult;

        }

    }