c语言计算拓扑排序

1.源码实现

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <malloc.h>

struct List {
    int w;
    struct List *next;
    struct List *last;
};

struct Queue {
    int v;
    struct Queue *next;
    struct Queue *last;
};

void ListPush(struct List **list, int w)
{
    struct List *last = (struct List *)malloc(sizeof(struct List));

    memset(last, 0x00, sizeof(struct List));

    last->w = w;

    if((*list) == NULL)
    {
        *list = last;

        (*list)->next = NULL;
        (*list)->last = last;

        return;
    }

    if((*list)->next == NULL)
    {
        (*list)->next = last;
    }

    (*list)->last->next = last;
    (*list)->last = last;
}

void ListPop(struct List **list)
{
    struct List *top = (*list);

    if(list == NULL || *list == NULL)
    {
        return;
    }

    if((*list)->next == NULL)
    {
        free(*list);

        *list = NULL;

        return;
    }

    (*list) = (*list)->next;

    (*list)->last = top->last;

    free(top);
}

int ListFront(const struct List *list)
{
    if(list == NULL)
    {
        return -1;
    }

    return list->w;
}

char ListIsEmpty(const struct List *list)
{
    if(list == NULL)
    {
        return 1;
    }

    return 0;
}

void ListFree(struct List **list)
{
    if(!list)
    {
        return;
    }

    while(!ListIsEmpty(*list))
    {
        ListPop(list);
    }
}

void QueuePush(struct Queue **queue, int v)
{
    struct Queue *last = NULL;

    last = (struct Queue *)malloc(sizeof(struct Queue));

    memset(last, 0x00, sizeof(struct Queue));

    last->v = v;

    if((*queue) == NULL)
    {
        *queue = last;

        (*queue)->next = NULL;
        (*queue)->last = last;

        return;
    }

    if((*queue)->next == NULL)
    {
        (*queue)->next = last;
    }

    (*queue)->last->next = last;
    (*queue)->last = last;
}

void QueuePop(struct Queue **queue)
{
    struct Queue *top = NULL;

    if(queue == NULL || *queue == NULL)
    {
        return;
    }

    top = (*queue);

    if((*queue)->next == NULL)
    {
        free(*queue);

        *queue = NULL;

        return;
    }

    (*queue) = (*queue)->next;

    (*queue)->last = top->last;

    free(top);
}

int QueueFront(const struct Queue *queue)
{
    if(queue == NULL)
    {
        return -1;
    }

    return queue->v;
}

char QueueIsEmpty(const struct Queue *queue)
{
    if(queue == NULL)
    {
        return 1;
    }

    return 0;
}

void QueueFree(struct Queue **queue)
{
    while(!QueueIsEmpty(*queue))
    {
        QueuePop(queue);
    }
}

void GraphInit(struct List ***adj, int **indegree, int V)
{
    int i;

    (*adj) = (struct List **)malloc(sizeof(struct List **)*V);
    (*indegree) = (int *)malloc(sizeof(int *)*V);

    for(i=0; i<V; i++)
    {
        (*adj)[i] = NULL;
        (*indegree)[i] = 0;
    }
}

void GraphFree(struct List ***adj, int **indegree, int n)
{
    int i;

    for(i=0; i<n; i++)
    {
        ListFree((*adj)+i);
    }

    free(*adj);
    free(*indegree);

    *adj = NULL;
    *indegree = NULL;
}

void GraphAddEdge(struct List **adj, int *indegree, int v, int w)
{
    ListPush(adj+v, w);
    ++indegree[w];
}

char GraphTopoLogicSort(struct List **adj, int *indegree, int V, struct Queue **q, struct Queue **r)
{
    struct List **u = NULL;
    struct List *p = NULL;
    int i;

    /*将所有入度为零的顶点入队*/
    for(i=0; i<V; i++)
    {
        if(indegree[i] == 0)
        {
            QueuePush(q, i);
        }
    }

    /*记录当前已经输出的顶点数*/
    int count = 0;

    while(!QueueIsEmpty(*q))
    {
        int v = QueueFront(*q);

        QueuePop(q);
        QueuePush(r, v);

        ++count;

        if(v == -1)
        {
            break;
        }

        u = adj + v;
        p = *u;

        i = 0;

        /*将所有v指向的顶点的入度减1*/
        while(p != NULL)
        {
            if(!(--indegree[p->w]))
            {
                /*若度为0则入栈*/

                QueuePush(q, p->w);
                        }

            i++;

            p = p->next;
                }
        }

    if(count < V)
    {
        return 0;
    }

    return 1;
}

int main()
{
    struct List **adj = NULL;
    struct Queue *p = NULL;
    struct Queue *q = NULL;
    int *indegree = NULL;
    int n = -1;
    int m = -1;
    int a = -1;
    int b = -1;
    int c = 0;
    int i = 0;
    int u = -1;

    scanf("%d %d", &n, &m);

    if(m < 1 || n < 1)
    {
        return -1;
    }

    GraphInit(&adj, &indegree, n);

    for(i=0; i<m; i++)
    {
        a = -1;
        b = -1;

        scanf("%d %d", &a, &b);

        if(a < 1 || b < 1)
        {
            continue;
        }

        GraphAddEdge(adj, indegree, a-1, b-1);
    }

    c = GraphTopoLogicSort(adj, indegree, n, &p, &q);

    if(QueueIsEmpty(q) || c == 0)
    {
        printf("-1\n");
    }
    else
    {
        u = QueueFront(q) + 1;

        printf("%d", u);

        QueuePop(&q);

        while(!QueueIsEmpty(q))
        {
            u = QueueFront(q) + 1;

            printf(" %d", u);

            QueuePop(&q);
        }

        printf("\n");
    }

    GraphFree(&adj, &indegree, n);

    return 0;
}

2.编译源码

$ gcc -o test test.c -std=c89

3.运行及其结果

$ ./test
5 4
1 2
2 3
3 4
4 5
1 2 3 4 5