[数据结构与算法]数据结构---图---拓扑排序---6

拓扑排序主要解决一个工程能否顺序进行的问题。

无环图：图中没有回路

在一个表示工程的有向图中，用顶点表示活动，用弧表示活动之间的优先关系，这样的有向图为顶点表示活动的网，我们称为AOV网（Activity On Vertex Network）。

AOV网中的弧表示活动之间存在的某种制约关系(也可以理解活动要分先后顺序)，AOV网中不能有回路。

设G=(V,E)是一个具有n个顶点的有向图，V中的顶点序列v1，v2，…vn,满足若从顶点vi到vj有一条路径，则在顶点序列中顶点vi必在顶点vj之前。则我们称这样的顶点序列为一个拓扑序列。

拓扑排序：就是对一个有向图构造拓扑序列的过程。

构造时会有两个结果，如果此网的全部顶点都被输出，则说明它是不存在环（回路）的AOV网；如果输出顶点数少了，哪怕少了一个，也说明这个网存在环（回路），不是AOV网。

一个不存在回路的AOV网，我们可以将它应用在各种各样的工程或项目的流程图中，满足各种应用场景的需要，所以实现拓扑排序的算法就很有价值了。

拓扑排序算法：

对AOV网进行拓扑排序的基本思路是：从AOV网中选择一个入度为0的顶点输出，然后删去此顶点，并删除以此顶点为尾的弧，继续重复此步骤，直到输出全部顶点或者AOV网中不存在入度为0的顶点为止。

C# 代码：可以只看最后的拓扑排序部分

/// <summary>
/// 邻接表
/// </summary>
public class AdjacencyList
{
    /// <summary>
    /// 边表结点
    /// </summary>
    public class EdgeNode
    {
        public int adjvex;      //邻接点域,存储该顶点对应的下标
        public int weight;      //用于存储权值，对于非网图可以不需要
        public EdgeNode next;   //链域，指向下一个邻接点
    }

    /// <summary>
    /// 顶点表结点
    /// </summary>
    public class VertexNode
    {
        public int inDegree;            //入度：拓扑排序用
        public int data;                //顶点域，存储顶点信息
        public EdgeNode firstEdge;      //边表头指针
    }

    public int numVertexes;             //顶点数
    public int numEdges;                //边数
    public VertexNode[] adjacencyArr;   //顶点表

    /// <summary>
    /// 说明：没有按书上写，需要的数据自行提供，包括顶点数据和边表数据
    /// 这里也只是大概的思路
    /// </summary>
    /// <param name="numVertexes"></param>
    /// <param name="numEdges"></param>
    /// <param name="datas"></param>
    /// <param name="edgeData"></param>
    public AdjacencyList(int numVertexes, int numEdges, int[] datas, EdgeNode[] edgeData)
    {
        this.numEdges = numEdges;
        this.numVertexes = numVertexes;

        adjacencyArr = new VertexNode[numVertexes];

        for (int i = 0; i < this.numVertexes; i++)      //建立顶点表
        {
            adjacencyArr[i].data = datas[i];            //顶点数据
            adjacencyArr[i].firstEdge = edgeData[i];    //建立边表
        }
    }

    private bool[] visited;

    /// <summary>
    /// 邻接表的深度优先遍历
    /// </summary>
    /// <param name="gl"></param>
    public void DFSTraverse(AdjacencyList gl)
    {
        for (int i = 0; i < gl.numVertexes; i++)
        {
            visited[i] = false; //初始化所有顶点都是未访问的状态
        }

        for (int i = 0; i < gl.numVertexes; i++)
        {
            //对未访问过的顶点调用DFS，若是连通图，只会执行一次
            if (!visited[i])
            {
                DFS(gl, i);
            }
        }
    }

    /// <summary>
    /// 邻接表的深度优先递归算法
    /// </summary>
    /// <param name="gl"></param>
    /// <param name="i"></param>
    private void DFS(AdjacencyList gl, int i)
    {
        visited[i] = true;

        //这里对顶点的操作,这里简单的打印
        Debug.Log(gl.adjacencyArr[i].data);

        EdgeNode temp = gl.adjacencyArr[i].firstEdge;

        while (temp != null)
        {
            if (!visited[temp.adjvex])
                DFS(gl, temp.adjvex);
            temp = temp.next;
        }
    }

    /// <summary>
    /// 邻接表：广度优先遍历
    /// </summary>
    /// <param name="gl"></param>
    public void BFSTraverse(AdjacencyList gl)
    {
        Queue<int> queue = new Queue<int>();  //初始化辅助队列

        EdgeNode p;

        for (int i = 0; i < gl.numVertexes; i++)
        {
            visited[i] = false;
        }

        for (int i = 0; i < gl.numVertexes; i++)   //对每一个顶点做循环
        {
            if (!visited[i])            //若是未访问过就处理
            {
                visited[i] = true;      //设置当前顶点访问过

                //这里对顶点的操作,这里简单的打印
                Debug.Log(gl.adjacencyArr[i].data);

                queue.Enqueue(i);       //将此顶点入队列

                while (queue.Count > 0) //当前队列有元素
                {
                    i = queue.Dequeue();    //出队列

                    p = gl.adjacencyArr[i].firstEdge;   //找到当前顶点边表链表头指针

                    while (p != null)
                    {
                        //此顶点未访问过
                        if (!visited[p.adjvex])
                        {
                            visited[p.adjvex] = true;

                            //这里对顶点的操作,这里简单的打印
                            Debug.Log(gl.adjacencyArr[p.adjvex].data);

                            queue.Enqueue(p.adjvex);        //将此顶点入队列
                        }

                        p = p.next;     //指针指向下一个邻接点
                    }
                }
            }
        }
    }

    /// <summary>
    /// 普里姆算法：最小生成树
    /// </summary>
    /// <param name="graph"></param>
    public void MiniSpanTree_Prim(Graph graph)
    {
        int minCost, i, j, minCostIndex;
        int[] adjvex = new int[graph.numVertex];    //保存相关顶点下标
        int[] lowCost = new int[graph.numVertex];   //保存相关顶点间边的权值
        lowCost[0] = 0;     //初始化第一个权值为0，即V0加入生成树，lowCost的值为0，在这里就是此下标的顶点已经加入生成树
        adjvex[0] = 0;      //初始化第一个顶点下标为0，从顶点V0开始

        //读取第一行，初始化
        for (i = 1; i < graph.numVertex; i++)   //循环除下标为0外的全部顶点
        {
            lowCost[i] = graph.arcs[0, i];  //将V0顶点与之有边的权值存入数组
            adjvex[i] = 0;                  //初始化都为V0的下标
        }

        //构造最小生成树
        for (i = 1; i < graph.numVertex; i++)
        {
            minCost = int.MaxValue; //初始化最小权值为极大值，通常设置为不可能的大数字，如：32765、65535等
            j = 1;                  //顶点下标循环变量
            minCostIndex = 0;       //用来存储最小权值的顶点下标

            //遍历每一行的数据
            while (j < graph.numVertex)
            {
                if (lowCost[j] != 0 && lowCost[j] < minCost)
                {
                    minCost = lowCost[j];       //让当前权值成为最小值
                    minCostIndex = j;           //将当前最小值的下标存入k
                }
                j++;
            }

            Debug.Log("打印当前顶点边中权值最小边：" + adjvex[minCostIndex] + "---" + minCostIndex);

            lowCost[minCostIndex] = 0;     //将当前顶点的权值设置为0，表示此顶点已经完成任务

            for (j = 1; j < graph.numVertex; j++)       //循环所有顶点
            {
                if (lowCost[j] != 0 && graph.arcs[minCostIndex, j] < lowCost[j])
                {
                    //若下标为k顶点各边权值小于此前这些顶点未被加入生成树权值
                    lowCost[j] = graph.arcs[minCostIndex, j];      //将较小权值存入lowCost
                    adjvex[j] = minCostIndex;                      //将下标为k的顶点存入adjvex
                }
            }
        }
    }

    /// <summary>
    /// 拓扑排序：需要一个栈辅助，存储处理过程中入度为0的顶点
    /// 目的是为了避免么个查找时都要去遍历顶点表找有没有入度为0的顶点
    /// </summary>
    /// <param name="gl">邻接表</param>
    /// <returns>无回路返回true,有回路返回false</returns>
    public bool TopologicalSort(AdjacencyList gl)
    {
        EdgeNode node;
        int k, topIndex;
        int count = 0;          //用于统计输出顶点的个数                     
        Stack<int> stack = new Stack<int>(gl.numVertexes);  //建栈存储入度为0的顶点
        for (int i = 0; i < gl.numVertexes; i++)
        {
            if (gl.adjacencyArr[i].inDegree == 0)
            {
                stack.Push(i);
            }
        }

        while (stack.Count != 0)
        {
            topIndex = stack.Pop();       //出栈
            Debug.Log("->" + gl.adjacencyArr[topIndex].data);   //打印此顶点
            count++;        //统计输出顶点数

            for (node = gl.adjacencyArr[topIndex].firstEdge; node != null; node = node.next)
            {
                //对此顶点弧表遍历
                k = node.adjvex;
                if ((--gl.adjacencyArr[k].inDegree) == 0)   //将k号顶点邻接点的入度减1
                {
                    stack.Push(k);          //若为0则入栈，以便下次循环输出
                }
            }
        }

        if (count < gl.numVertexes) return false;     //如果count小于顶点数，说明存在环
        else return true;
    }
}