algraph.cs

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

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

namespace TopologicalSort
{
    enum GraphKind { DG, DN, UDG, UDN };//{有向图,有向网,无向图,无向网}

    //邻接表结点
    class ArcNode
    {
        int adjvex; //该弧所指向的顶点的位置       
        string info; //权值指针

        public int Adjvex
        {
            get { return adjvex; }
            set { adjvex = value; }
        }
        public string Info
        {
            get { return info; }
            set { info = value; }
        }
    }

    //头结点
    class VNode
    {
        string data; //顶点信息
        IList<ArcNode> arcNodeList;

        public string Data
        {
            get { return data; }
            set { data = value; }
        }
        public IList<ArcNode> ArcNodeList
        {
            get { return arcNodeList; }
            set { arcNodeList = value; }
        }

        public VNode()
        {
            this.arcNodeList = new List<ArcNode>();
        }
    }

    //图的邻接表表示
    class ALGraph
    {
        IList<VNode> vertices = new List<VNode>();
        int vexnum, arcnum; //图的顶点数和弧数
        GraphKind kind; //图的种类

        public IList<VNode> Vertices
        {
            get { return vertices; }
            set { vertices = value; }
        }
        public int Arcnum
        {
            get { return arcnum; }
            set { arcnum = value; }
        }
        public int Vexnum
        {
            get { return vexnum; }
            set { vexnum = value; }
        }

        public bool CreateGraph()
        {
            int w;//权值
            string va, vb;
            Console.WriteLine("请输入图的顶点数:");
            this.vexnum = Convert.ToInt32(Console.ReadLine());
            Console.WriteLine("请输入图的边数:");
            this.arcnum = Convert.ToInt32(Console.ReadLine());
            Console.WriteLine("请输入所有顶点的值:");
            for (int i = 0; i < this.vexnum; ++i)
            {
                VNode vnode = new VNode();
                vnode.Data = Console.ReadLine();
                this.vertices.Add(vnode);
            }
            Console.WriteLine("请顺序输入每条弧(边)的弧尾和弧头(以空格作为间隔):");
            //构造表结点链表
            for (int k = 0; k < this.arcnum; ++k)
            {
                string str = Console.ReadLine();
                string[] vals = str.Split(new char[] { ' ' });
                va = vals[0];
                vb = vals[1];
                int i = this.LocateVex(va);
                int j = this.LocateVex(vb);
                ArcNode p = new ArcNode();
                p.Adjvex = j;
                p.Info = null;
                this.vertices[i].ArcNodeList.Insert(0, p);//插在表头
            }

            return true;
        }

        private int LocateVex(string u)
        {
            for (int i = 0; i < this.vexnum; ++i)
            {
                if (u == this.vertices[i].Data)
                {
                    return i;
                }
            }
            return -1;
        }
    }
}