• 拓扑排序算法

    拓扑排序算法

    1. #include <stdio.h>
    2. #include <malloc.h>
    3. #include <string.h>
    4. #define MAXVEX 100
    6. typedef char VertexType[3];        /*定义VertexType为char数组类型*/
    8. typedef struct vertex
    9. {
    10.     int adjvex;
    11.     VertexType data;
    12. } VType;
    14. typedef struct graph
    15. {    
    16.     int n,e;                    /*n为实际顶点数,e为实际边数*/
    17.     VType vexs[MAXVEX];            /*顶点集合*/
    18.     int edges[MAXVEX][MAXVEX];    /*边的集合*/
    19. } AdjMatix;                        /*图的邻接矩阵类型*/
    21. typedef struct edgenode
    22. {    
    23.     int adjvex;                  /*邻接点序号*/
    24.     int value;                  /*边的权值*/
    25.     struct edgenode *next;        /*下一条边的顶点*/
    26. } ArcNode;                        /*每个顶点建立的单链表中结点的类型*/
    28. typedef struct vexnode
    29. {
    30.     VertexType data;               /*结点信息*/
    31.     int count;                     /*存放顶点入度,新增用于拓扑排序*/
    32.     ArcNode *firstarc;             /*指向第一条边结点*/
    33. } VHeadNode;                    /*单链表的头结点类型*/
    35. typedef struct 
    36. {
    37.     int n,e;                    /*n为实际顶点数,e为实际边数*/
    38.     VHeadNode adjlist[MAXVEX];    /*单链表头结点数组*/
    39. } AdjList;                         /*图的邻接表类型*/
    41. void DispAdjList(AdjList *G)    /*显示邻接表(含顶点入度)*/
    42. {
    43.     int i;
    44.     ArcNode *p;
    45.     printf("图的邻接表表示如下:\n");
    46.     for (i=0;i<G->n;i++)
    47.     {    
    48.         printf("  [%d,%3s:]=>",i,G->adjlist[i].data,G->adjlist[i].count);
    49.         p=G->adjlist[i].firstarc;
    50.         while (p!=NULL)
    51.         {    
    52.             printf("(%d,%d)->",p->adjvex,p->value);
    53.             p=p->next;
    54.         }
    55.         printf("∧\n");
    56.     }
    57. }
    59. void MatToList(AdjMatix g,AdjList *&G)  /*例6.3算法:将邻接矩阵g转换成邻接表G*/
    60. {
    61.     int i,j;
    62.     ArcNode *p;
    63.     G=(AdjList *)malloc(sizeof(AdjList));
    64.     for (i=0;i<g.n;i++)                    /*给邻接表中所有头结点的指针域置初值*/
    65.     {    
    66.         G->adjlist[i].firstarc=NULL;
    67.         strcpy(G->adjlist[i].data,g.vexs[i].data);
    68.     }
    69.     for (i=0;i<g.n;i++)                    /*检查邻接矩阵中每个元素*/
    70.         for (j=g.n-1;j>=0;j--)
    71.             if (g.edges[i][j]!=0)        /*邻接矩阵的当前元素不为0*/
    72.             {
    73.                 p=(ArcNode *)malloc(sizeof(ArcNode));/*创建一个结点*p*/
    74.                 p->value=g.edges[i][j];p->adjvex=j;
    75.                 p->next=G->adjlist[i].firstarc;          /*将*p链到链表后*/
    76.                 G->adjlist[i].firstarc=p;
    77.             }
    78.     G->n=g.n;G->e=g.e;
    79. }
    81. void TopSort(AdjList *G)
    82. {
    83.     int i,j;
    84.     int St[MAXV],top=-1;              /*栈St的指针为top*/
    85.     ArcNode *p;
    86.     for (i=0;i<n;i++)
    87.         if (adj[i].count==0)           /*入度为0的顶点入栈*/
    88.         {
    89.             top++; 
    90.             St[top]=i;  
    91.         }
    92.         while (top>-1)                 /*栈不为空时循环*/
    93.         {
    94.             i=St[top];top--;          /*出栈*/
    95.             printf("%d ",i);          /*输出顶点*/
    96.             p=adj[i].firstarc;         /*找第一个相邻顶点*/
    97.             while (p!=NULL) 
    98.             {
    99.                 j=p->adjvex;
    100.                 adj[j].count--; 
    101.                 if (adj[j].count==0)/*入度为0的相邻顶点入栈*/
    102.                 {
    103.                     top++;
    104.                     St[top]=j;
    105.                 }
    106.                 p=p->nextarc;        /*找下一个相邻顶点*/
    107.             }
    108.         }
    109. }
    111. void main()
    112. {
    113.     int i,j;
    114.     AdjMatix g;
    115.     AdjList *G;
    116.     int a[6][6]={ {0,1,0,10},{1,0,1,0,0},{0,1,0,1,1},{1,0,1,0,1},{0,0,1,1,0} };
    117.     char *vname[MAXVEX]={"a","b","c","d","e"};
    118.     g.n=5;g.e=12;    /*建立图6.1(a)的无向图,每1条无向边算为2条有向边*/
    119.     for (i=0;i<g.n;i++)
    120.         strcpy(g.vexs[i].data,vname[i]);
    121.     for (i=0;i<g.n;i++)
    122.         for (j=0;j<g.n;j++)
    123.             g.edges[i][j]=a[i][j];
    124.     MatToList(g,G);        /*生成邻接表*/
    125.     DispAdjList(G);        /*输出邻接表*/
    126.     for (i=0;i<g.n;i++)    visited[i]=0; /*顶点标识置初值*/
    127.     printf("从顶点0的深度优先遍历序列:\n");
    128.     printf("  递归算法:");DFS(G,0);printf("\n");
    129.     for (i=0;i<g.n;i++)    visited[i]=0; /*顶点标识置初值*/
    130.     printf("  非递归算法:");DFS1(G,0);printf("\n");
    131. }