拓扑排序——AOV网

ゞ浴缸里的玫瑰 2021-11-14 00:26 273阅读 0赞

> **特点：**
> 
>  *  **顶点表示活动**
>  *  **边表示活动的先后次序，边没有权值**
>  *  **没有回路的有向图**

>  **结构体定义：**
> 
>     typedef struct node        //边表
>     {
>         int adjvex;
>         struct node* next;
>     }ArcNode;
>     typedef struct            //顶点表
>     {
>         int data;
>         int count;            //记录顶点的入度
>         ArcNode* first;
>     }VerNode;
>     typedef struct            //邻接表
>     {
>         VerNode adjList[MaxVertices];
>         int n,e;
>     }AdjList;
> 
>

**AOV拓扑排序代码：**

void Topsort(AdjList *G)
    {
        int i,j;
        int Stack[MaxVertices],top = -1;
        ArcNode *p;
        for(i=0;i<G->n;i++)             //让所有入度为0的顶点入栈
        {
            if(G->adjList[i].count == 0)
                Stack[++top] = G->adjList[i].data;
        }
        while(top!=-1)
        {
            i = Stack[top--];           //顶点出栈
            printf("%d\t",i);           //输出当前顶点
            p = G->adjList[i].first;    //p指向当前顶点的第一条边
            while(p)
            {
                j = p->adjvex;          //j保存出栈顶点后连接的边的顶点
                --(G->adjList[j].count);    //所有与出栈顶点相连的顶点的入度-1
                if(G->adjList[j].count == 0)    //若当前j顶点入度为0，则让j入栈
                    Stack[++top] = j;
                p = p->next;                        //p指向j的下一条边
            }
        }
    }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDgxOTI0_size_16_color_FFFFFF_t_70][]

**运行结果：**

**输入数据：**

7 11  
0 1 2 3 4 5 6  
0 1  
0 2  
0 3  
1 2  
1 4  
2 4  
2 5  
3 5  
4 6  
5 4  
5 6

**1.尾插法创建邻接表**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDgxOTI0_size_16_color_FFFFFF_t_70 1][]

**2.头插法创建邻接表**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDgxOTI0_size_16_color_FFFFFF_t_70 2][]

## **完整代码：** ##

#include <stdio.h>
    #include <stdlib.h>
    #define MaxVertices 20
    typedef struct node
    {
        int adjvex;
        struct node* next;
    } ArcNode;
    typedef struct
    {
        int data;
        int count;          //记录顶点的入度
        ArcNode* first;
    } VerNode;
    typedef struct
    {
        VerNode adjList[MaxVertices];
        int n,e;
    } AdjList;
    void CreateGraph(AdjList *G)
    {
        int i,a,b;
        ArcNode *s,*p;
        printf("请输入总顶点数和边数:\n");
        scanf("%d %d",&G->n,&G->e);
        printf("创建顶点表:\n");
        for(i=0; i<G->n; i++)
        {
            scanf("%d",&G->adjList[i].data);
            G->adjList[i].first = NULL;
            G->adjList[i].count = 0;      //所有顶点的入度初始化为0
        }
        printf("创建边表:\n");
        for(i=0; i<G->e; i++)
        {
            scanf("%d %d",&a,&b);
            //头插法创建邻接表
            s = (ArcNode*)malloc(sizeof(ArcNode));
            s->adjvex = b;
            s->next = G->adjList[a].first;
            G->adjList[a].first = s;
            G->adjList[b].count++;
            //尾插法创建邻接表
    //        s = (ArcNode*)malloc(sizeof(ArcNode));
    //        s->adjvex = b;
    //        s->next = NULL;
    //        p = G->adjList[a].first;
    //        if(!p)
    //        {
    //            G->adjList[a].first = s;
    //            G->adjList[b].count++;       //a顶点的下一条边b的入度+1
    //        }
    //        else
    //        {
    //            while(p->next)
    //            {
    //                p = p->next;
    //            }
    //            p->next = s;
    //            G->adjList[b].count++;       //a顶点的下一条边b的入度+1
    //        }
        }
    }
    void Topsort(AdjList *G)
    {
        int i,j;
        int Stack[MaxVertices],top = -1;
        ArcNode *p;
        for(i=0; i<G->n; i++)           //让所有入度为0的顶点入栈
        {
            if(G->adjList[i].count == 0)
                Stack[++top] = G->adjList[i].data;
        }
        while(top!=-1)
        {
            i = Stack[top--];           //顶点出栈
            printf("%d\t",i);           //输出当前顶点
            p = G->adjList[i].first;    //p指向当前顶点的第一条边
            while(p)
            {
                j = p->adjvex;          //j保存出栈顶点后连接的边的顶点
                --(G->adjList[j].count);    //所有与出栈顶点相连的顶点的入度-1
                if(G->adjList[j].count == 0)    //若当前j顶点入度为0，则让j入栈
                    Stack[++top] = j;
                p = p->next;                        //p指向j的下一条边
            }
        }
    }
    int main()
    {
        AdjList *G = (AdjList*)malloc(sizeof(AdjList));
        CreateGraph(G);
        Topsort(G);
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDgxOTI0_size_16_color_FFFFFF_t_70]: /images/20211113/f0757e73a34f419cbb601a41d0f146c3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDgxOTI0_size_16_color_FFFFFF_t_70 1]: /images/20211113/9f80e3dd260d4ed58822ee9f6b0b7d81.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDgxOTI0_size_16_color_FFFFFF_t_70 2]: /images/20211113/512ebc527db94241a1af79fd04947e6f.png