有向图的拓扑排序

柔光的暖阳◎ 2022-08-21 04:45 186阅读 0赞

**有向图的拓扑排序**

本文取自《数据结构与算法》(C语言版)(第三版)，出版社是清华大学出版社。

本博文作为学习资料整理。源代码是VC++ 6.0上可执行程序，我挪到了VS2010中执行。

在VS2010中新建C++ Win32 控制台应用程序项目，创建结果截图：

![Center][]

有向图的拓扑排序的基本思想是：首先在有向图中选取一个没有前驱的顶点，将其输出，从有向图中删除该顶点，并且删除以该顶点为尾的所有有向图的边。重复以上的步骤，直到图中的所有顶点均输出或是图中的顶点均没有前驱为止。对于后者，说明有向图中存在环，不能进行拓扑排序。

以下以AOV(Activity On Vertex Network)网为例，演示求解拓扑排序的步骤：

![SouthEast][]

C++ Win32 控制台应用程序，代码如下：topSort.cpp

#include "stdafx.h"
      #include<stdio.h>
      #include<string.h>
      #define MAXNODE 20
      typedef struct
      {
        char vertex;
      }VerNode;
    
      typedef struct
      {
        int adj;
      }Arc;
    
      typedef struct
      {
        VerNode vexs[MAXNODE];
        Arc arcs[MAXNODE][MAXNODE];
        int m_numOfVexs;
      }Graph;
    
      int mFind(char aim, VerNode* arry)
      {
        int pos=-1;
        int i=0;
        for(i=0; i<MAXNODE; i++)
        {
          if(aim==arry[i].vertex)
          {
            pos=i;
            return pos;
          }
        }
        return pos;
      }
    
      void showGraph(Graph aGraph, int num)
      {
        int i=0;
        int j=0;
        printf("\n NODES:\n");
        for(i=0; i<num; i++)
        {
          printf(" %c", aGraph.vexs[i].vertex);
        }
        printf("\n ARCS:\n");
        for(i=0; i<num; i++)
        {
          for(j=0; j<num; j++)
          {
            printf(" %d", aGraph.arcs[i][j].adj);
          }
          printf(" \n");
        }
      }
    
      //添加顶点
      void addVexs(Graph* aGraph, char vex)
      {
        aGraph->m_numOfVexs++;
        aGraph->vexs[aGraph->m_numOfVexs].vertex=vex;
      }
    
      //添加边
      void addArcs(Graph* aGraph, char aStart, char aEnd)
      {
        int p_x=mFind(aStart,aGraph->vexs);
        int p_y=mFind(aEnd,aGraph->vexs);
        aGraph->arcs[p_x][p_y].adj=1;
      }
    
      //图的初始化
      void initGraph(Graph* aGraph)
      {
        int i=0;
        int j=0;
        aGraph->m_numOfVexs=-1;
        for(i=0; i<MAXNODE; i++)
        {
          for(j=0; j<MAXNODE; j++)
            aGraph->arcs[i][j].adj=0;
        }
      }
    
      int getInDegree(int i, Graph* aGraph)
      {
        int InDegree=0;
        int j=0;
        for(j=0; j<aGraph->m_numOfVexs; j++)
          InDegree+=aGraph->arcs[j][i].adj;
        return InDegree;
      }
    
      int topSort(Graph* aGraph)
      {
        int i;
        int isOK=1;
        int vexsIsOut[MAXNODE];
        for(i=0; i<aGraph->m_numOfVexs; i++)
        {
          vexsIsOut[i]=0;
        }
        while(isOK==1)
        {
          isOK=0;
          for(i=0; i<aGraph->m_numOfVexs; i++)
          {
            if(vexsIsOut[i]==0&&getInDegree(i,aGraph)==0)
            {
              int j;
              printf("%c ",aGraph->vexs[i].vertex);
              vexsIsOut[i]=1;
              for(j=0; j<aGraph->m_numOfVexs; j++)
              {
                aGraph->arcs[i][j].adj=0;
              }
              isOK=1;
            }
          }
        }
        for(i=0; i<aGraph->m_numOfVexs; i++)
        {
          if(vexsIsOut[i]==0)
            return 0;
        }
        return 1;
      }
    
      int main(void)
      {
        char node='a';
        char input1='a';
        char input2='a';
        //将图初始化
        Graph g_graph;
        initGraph(&g_graph);
    
        //根据用户的输入添加顶点
        printf("Please input the vexs( end with #):\n");
        while(1)
        {
          if(node=='#')
            break;
          if(scanf("%c,",&node)==1)
          {
            if(node=='\n')
              continue;
            addVexs(&g_graph,node);
          }
        }
    
        //根据用户的输入添加边
        printf("Please input arcs, just like this \"startNod,endNode\" \n");
        while(1)
        {
          if(input1=='#')
            break;
          if(scanf("%c,%c",&input1, &input2)==2)
          {
            if(input1=='\n'||input2=='\n')
              continue;
            addArcs(&g_graph, input1, input2);
          }
        }
    
        //输出图
        showGraph(g_graph, g_graph.m_numOfVexs);
    
        printf("The topsort is: \n");
        if(topSort(&g_graph)==0)
          printf("There is a circle in the graph!! \n");
        return 0;
      }

Ctrl+F5执行topSort.cpp代码，结果如下图：

![Center 1][]

[Center]: /images/20220731/249f77e4a9c64a8485f68a1a05d989dc.png
[SouthEast]: /images/20220731/35f135ea5c944f2b9add5d9a72d1040a.png
[Center 1]: /images/20220731/680c42eb74c34a688bfd46a7dc77903a.png