program.cs

用C#编写的拓扑排序算法程序（数据结构） 本程序用到了Framework 2.0 里新增的泛型

using System;
using System.Collections.Generic;
using System.Text;

namespace TopologicalSort
{
    class Program
    {
        //求顶点的入度
        static private void FindInDegree(ALGraph G,IList<int> indegree) 
        { 
            int i;
            for (i = 0; i < G.Vexnum; i++) 
            {
                indegree.Add(0);
            }
            for (i = 0; i < G.Vexnum; i++) 
            {
                foreach (ArcNode arcNode in G.Vertices[i].ArcNodeList) 
                {
                    indegree[arcNode.Adjvex]++;
                }
            }
        }

        //有向图G采用邻接表存储结构。若G无回路，则输出G的顶点的一个拓扑序列并返回OK，否则返回ERROR
        static private bool TopologicalSort(ALGraph G) 
        {
            IList<int> indegree = new List<int>();
            FindInDegree(G, indegree);
            Stack<int> s = new Stack<int>();
            for (int i = 0; i < G.Vexnum; ++i) 
            {
                if (indegree[i] == 0) 
                {
                    s.Push(i);//入度为0者进栈
                }
            }
            int count = 0;//对输出顶点计数
            while (s.Count != 0)
            {
                int i = s.Pop();
                Console.Write(G.Vertices[i].Data);//输出i号顶点并计数
                Console.Write(",");
                ++count;
                foreach (ArcNode arcnode in G.Vertices[i].ArcNodeList) 
                {
                    int k = arcnode.Adjvex;
                    if ((--indegree[k]) == 0)
                    {
                        s.Push(k);
                    }
                }
            }

            if (count < G.Vexnum)
            {
                Console.WriteLine("\n此有向图有回路\n");
                return false;
            }
            else
            {
                Console.WriteLine("\n为一个拓扑序列\n");
                return true;
            }
        }
        static void Main(string[] args)
        {
            ALGraph G = new ALGraph();
            bool result = G.CreateGraph();
            if (result)
            {
                Console.WriteLine("拓扑排序结果");
                TopologicalSort(G);
                Console.ReadLine();
            }
        }
    }
}