graph.c

二、问题描述 给出一张某公园的导游图

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

#define TRUE        1
#define FALSE       0
#define OK          1
#define ERROR       0
#define INFEASIBLE -1
#define OVERFLOW   -2
#define MAX_VERTEX_NUM 20
#define MAX_WEIGHT    30000

typedef struct ArcNode
{
    int adjvex;                     //
    struct ArcNode *nextarc;
    int weight;
}ArcNode;

typedef struct VNode
{
    char *data;
    ArcNode *firstarc;
}VNode;

typedef struct
{
    VNode vexlist[MAX_VERTEX_NUM];
    int vexnum, arcnum;
}ALGraph;



int init_graph(ALGraph *G)
{
    G->vexnum = 0;
    G->arcnum = 0;
}

int init_ArcNode(ArcNode **p)
{
    *p =(ArcNode *)malloc(sizeof(ArcNode));
    if(!*p)
    {  
        printf("内存申请失败!\n"); 
        system("PAUSE");
        exit(ERROR);
    }
}

int destroy_graph(ALGraph *G)
{
    int i;
    for(i = 0; i < G->vexnum; i++)
    {
        free((G->vexlist[i]).data);
        destroy_arc((G->vexlist[i]).firstarc);
    }
}

int destroy_arc(ArcNode *p)
{
    if(p)
    {
        if(p->nextarc)
            destroy_arc(p->nextarc);
        free(p);
    }
}

int find_shortest_way(ALGraph G)
{
    int i, j, k, x, y, flag, m, n;
    int minweight, minnumber;
    int visit[MAX_VERTEX_NUM] = {0};
    int path[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
    ArcNode *p;
    for(i = 0; i < MAX_VERTEX_NUM; i++)
    {
        path[i][0] = MAX_WEIGHT;
        for(j = 1; j < MAX_VERTEX_NUM; j++)
            path[i][j] = -1;
    }
    for(i = 0; i < G.vexnum; i++)
    {
        printf("%d.%s\n", i, G.vexlist[i].data);
    }
    printf("请输入你所处的景点的代号：");
    scanf("%d", &x);
    printf("请输入你想去的景点的代号：");
    scanf("%d", &y);
    if(x >= 0 && y >= 0 && x < G.vexnum && y < G.vexnum)
    {
        visit[x] = 1;
        path[x][0] = 0;
        for(i = 0; i < G.vexnum - 1 && visit[y] == 0; i++)
        {        
            for(j = 0; j < G.vexnum; j++)
            {
                if(visit[j] == 0)
                for(k = 0; k < G.vexnum; k++)
                {
                    if(visit[k] == 1)
                    {
                        flag = 0;
                        for(p = G.vexlist[k].firstarc; p != NULL; p = p->nextarc)
                        {
                            if(p->adjvex == j)
                            {
                                flag++;
                                break;
                            }
                        }
                        if(flag)
                        {
                            if(path[k][0] + p->weight < path[j][0])
                            {
                                path[j][0] = path[k][0] + p->weight;
                                for(m = 1; path[k][m] >= 0; m++)
                                {
                                   path[j][m] = path[k][m];
                                }
                                path[j][m] = j;
                                path[j][m + 1] = -1;
                            }
                        }
                    }
                }
            }
            minweight = MAX_WEIGHT;
            for(n = 0; n < G.vexnum; n++)
            {
                if(visit[n] == 0)
                {
                    if(path[n][0] < minweight)
                    {
                        minweight = path[n][0];
                        minnumber = n;
                    }
                }
            }
            visit[minnumber] = 1;
        }
        printf("最短路径：%s", G.vexlist[x].data);
        for(i = 1; path[y][i] >= 0; i++)
        {
            printf("=>%s", G.vexlist[path[y][i]].data);
        }
        printf("\n");
    }
    else
    {
        printf("输入数字超过范围!\n");
        return ERROR;
    }
}

int add_arc(ALGraph *G, int x, int y, int weight)
{
    int i;
    ArcNode *NewArc;
    if(G->vexnum < 2)
    {
        printf("结点数小于2,添加弧失败!\n");
        return ERROR;
    }
    else
    {
        if(x >= 0 && y >= 0 && x < G->vexnum && y < G->vexnum)
        {
            init_ArcNode(&NewArc);
            NewArc->adjvex = y;
            NewArc->nextarc = (G->vexlist[x]).firstarc;
            (G->vexlist[x]).firstarc = NewArc;
            NewArc->weight = weight;
            init_ArcNode(&NewArc);
            NewArc->adjvex = x;
            NewArc->nextarc = (G->vexlist[y]).firstarc;
            (G->vexlist[y]).firstarc = NewArc;
            NewArc->weight = weight;
            G->arcnum++;
        }
        else
        {
            printf("输入数字超过范围!\n");
            return ERROR;
        }
    }
}

int add_vex(ALGraph *G, char *name)
{

    (G->vexlist[G->vexnum]).data = (char *)malloc((strlen(name) + 1) * sizeof(char));
    if(!(G->vexlist[G->vexnum]).data)
    {  
        printf("内存申请失败!\n"); 
        system("PAUSE");
        exit(ERROR);
    }
    strcpy((G->vexlist[G->vexnum]).data, name);   
    (G->vexlist[G->vexnum]).firstarc = NULL;
    G->vexnum++;
}

int main()
{
    ALGraph G;
    ArcNode *p =NULL;
    int i;
    char *name[20] = {"出发地", "夫妻岩", "夫妻岩观景点", "秦桧跪灵", "朝天观",
                      "金鞭岩", "望朗峰", "双枫醉秋", "天书宝匣", "九重仙阁",
                      "劈山救母", "凤凰岩", "黑枞脑", "天桥遗墩", "龙宫舞女",
                      "五女拜师", "蜡烛峰", "飞鹰崖", NULL, NULL}; 
    init_graph(&G);
    for(i = 0; name[i] != NULL; i++)
    {
        add_vex(&G, name[i]);
    }
    add_arc(&G, 1, 0, 4);
    add_arc(&G, 2, 0, 5);
    add_arc(&G, 2, 1, 5);
    add_arc(&G, 3, 2, 2);
    add_arc(&G, 4, 3, 6);
    add_arc(&G, 5, 1, 6);
    add_arc(&G, 6, 2, 4);
    add_arc(&G, 7, 6, 3);
    add_arc(&G, 8, 7, 3);
    add_arc(&G, 9, 4, 16);
    add_arc(&G, 9, 6, 5);
    add_arc(&G, 9, 8, 3);
    add_arc(&G, 10, 5, 3);
    add_arc(&G, 10, 8, 5);
    add_arc(&G, 11, 8, 9);
    add_arc(&G, 11, 9, 5);
    add_arc(&G, 12, 10, 7);
    add_arc(&G, 13, 12, 2);
    add_arc(&G, 14, 11, 8);
    add_arc(&G, 14, 13, 4);
    add_arc(&G, 15, 12, 6);
    add_arc(&G, 15, 13, 3);
    add_arc(&G, 16, 13, 5);
    add_arc(&G, 16, 14, 5);
    add_arc(&G, 17, 15, 4);
    add_arc(&G, 17, 16, 8);
    find_shortest_way(G);
    /*for(i = 0; name[i] != NULL; i++)
    {
        printf("%s ",G.vexlist[i].data);
        for(p = G.vexlist[i].firstarc; p != NULL; p = p->nextarc)
        {
            printf("%d %d ", p->adjvex, p->weight);
        }
        printf("\n");
    }*/
    destroy_graph(&G);
    system("PAUSE");
}