天天看點

圖--拓撲排序--p153

圖--拓撲排序--p153

源程式:在vc++6.0中運作通過

//  c0,c1,c2,c3,c4四個結點,在程式中和0,1,2,3,4來表示

//  main.cpp

//  top_sort

//

//  Created by duanqibo on 2019/12/20.

//  Copyright © 2019年 duanqibo. All rights reserved.

//

#include <stdio.h>

#include <stdlib.h>

const int vnum=20;

typedef struct node    //定義棧結構

{

    int data;

    struct node *next;

}*LkStk,LkStack;

typedef struct arcnode

{

    int adjvex;

    struct arcnode *nextarc;

    //OtherInfo info;

}ArcNode;

typedef struct vexnode

{

    char data;

    struct arcnode *firstarc;

}VNode, AdjList[vnum];

typedef struct gp

{

    AdjList adjlist;    //vertices;

    int vexnum, arcnum;

}Graph;

//并聲明一個int 類型的indegree[]數組,初始化為0:

int indegree[vnum] = { 0 };

//用于記錄下标節點的入度。

//入棧函數:

LkStk Push(LkStk S, int e)

{

    LkStk p;

    p = (LkStk)malloc(sizeof(LkStack));

    p->data = e;

    p->next = S;

    S = p;

    return S;

}

//出棧操作

LkStk Pop(LkStk S, int *e)

{

    LkStk p;

    p = S;

    //if (!p)

    //    return NULL;

    *e = p->data;

    S = S->next;

    free(p);

    return S;

int LocateVex(Graph *G, char v)

{

    int i;

    for (i = 0; i < (G->vexnum); i++)

    {

        if (v == G->adjlist[i].data)

            return i;

    }

}

void CreateUDG(Graph *G)

{

    int i, j, k;

    char v1, v2;

    ArcNode *p1;

    printf("輸入總節點數和總邊數:");

    scanf("%d%d", &G->vexnum, &G->arcnum);

    fflush(stdin);

    printf("輸入各個節點的值:");

    for (i = 0; i < G->vexnum; i++)

    {

        scanf("%c", &G->adjlist[i].data);

        G->adjlist[i].firstarc = NULL;

    }

    for (k = 0; k < G->arcnum; k++)

    {

        fflush(stdin);

        printf("輸入一條邊的兩個節點:");

        scanf("%c %c", &v1, &v2);

        i = LocateVex(G, v1);

        j = LocateVex(G, v2);

        p1 = (arcnode *)malloc(sizeof(arcnode));

        p1->adjvex = j;

        p1->nextarc = G->adjlist[i].firstarc;

        G->adjlist[i].firstarc = p1;

        indegree[j]++;

    }

}

//注意在建立圖過程中記錄節點的入度。

//拓撲排序算法:

int TopologicalSort(Graph G, int *topo)

{

    int i, m, k;

    LkStk S;

    ArcNode *p;

    S = NULL;

    for (i = 0; i < G.vexnum; i++)

    {

        if (!indegree[i])

            S = Push(S, i);

    }

    m = 0;

    while(S)

    {

        S = Pop(S, &i);

        topo[m] = i;

        ++m;

        p = G.adjlist[i].firstarc;

        while (p != NULL)

        {

            k = p->adjvex;

            --indegree[k];

            if (indegree[k] == 0)

                S = Push(S, k);

            p = p->nextarc;

        }

    }

    topo[m] = -1;

    if (m < G.vexnum)

        return 0;

    else

        return 1;

}

//主函數

int main(void)

{

    Graph G;

    int i;

    int topo[99] = { 0 };

    CreateUDG(&G);

    if (TopologicalSort(G, topo))

    {

        for (i = 0; topo[i] != -1; i++)

        {

            printf("%c ", G.adjlist[topo[i]].data);

        }

    }

    else

        printf("錯誤");

    printf("\n");

    system("pause");

    return 1;

}