原帖地址：http://bbs.bc-cn.net/dispbbs.asp?boardid=179&id=129767

请不吝赐教,多多指点...多谢了!
//"有向图"参见http://bbs.bc-cn.net/dispbbs.asp?boardid=179&id=130955&star=1#130955
//http://blog.bc-cn.net/user15/82588/index.shtml
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#define MaxSize 250
#define MaxLine 20
typedef int Status;
typedef int ElemType;
typedef struct{
    ElemType VNode;
    }VexType;
typedef struct Arcs{
    ElemType Adj;
    unsigned int Weight;
    struct Arcs *NextArc;
    }ArcType;
typedef struct{
    VexType Vex[MaxSize];
    ArcType *FirstArc[MaxSize];
    int VexNums;
    }ALGraph;    //定义图的无向邻接表;
typedef struct{
    VexType Vex[MaxSize];
    unsigned int Weight[MaxSize][MaxSize];
    int VexNums;
    }AMGraph;    //定义图的邻接矩阵;
typedef struct{
    ElemType head,tail;
    unsigned int Weight;
    }MST;        //最小生成树辅助结构;
//=================================================================================
Status CreateALGraph(ALGraph *ALG,FILE *fp);        //创立无向图的邻接表;
Status AL2AM(ALGraph ALG,AMGraph *AMG);            //转换为图的邻接矩阵;
Status ALG_Travers(ALGraph ALG);                //图的遍历;
Status ALG_DFS(ALGraph ALG,int v,int *Visited);            //深度遍历(递  归);
Status ALG_DFS_Uni(ALGraph ALG,int v,int *Visited);        //深度遍历(非递归);
Status ALG_BFS(ALGraph ALG,int v,int *Visited);            //广度遍历;
Status CreateMST(ALGraph ALG,AMGraph AMG);        //构造最小生成树;
Status AMG_Prim(AMGraph AMG,MST *MST_P);         //(邻接矩阵)Prim;
Status ALG_Prim(ALGraph ALG,MST *MST_P);         //(邻 接 表)Prim;
Status ALG_Kruskal(ALGraph ALG,MST *MST_K);        //(邻 接 表)Kruskal;
Status AMG_Kruskal(AMGraph AMG,MST *MST_K);        //(邻接矩阵)Kruskal;
Status FindVex(int *Vex,int v);    //(Kruskal)查找顶点所在树的根结点在数组Vex中的序号;
Status Prn_ALGraph(ALGraph ALG);            //输出邻接表;
Status Prn_AMGraph(AMGraph AMG);            //输出邻接矩阵;
Status PrintMST(MST *MT);                //输出最小生成树;
//=================================================================================
int main(void)
{
    ALGraph ALG;
    AMGraph AMG;
    FILE *fp;
    char FileName[MaxLine];
    printf("\t\t<<<<<<  无向图的应用演示  >>>>>>\n创立无向图：\n");
    printf("==============================================================\n");
    printf("  包含图信息的文本文件的格式为：\n第一行：  12\t<--- 顶点总数；\n");
    printf("第二行：   1  6  16\n");
    printf("\t   ↑ ↑ ↑\n");    
    printf("\t   │ │ └───  AB边的权值Weight；\n");
    printf("\t   │ └────   A边所依附的另一顶点B；\n");
    printf("\t   └──────  某顶点A。\n第m行 ：以后各行与第二行类似。\n");
    printf("==============================================================\n");
    printf("输入文本文件名(输入quit退出)。\n");
    do{
        printf("    输入文件名：");
        gets(FileName);
        if(!strcmp(FileName,"quit"))    exit (1);
    }while(FileName[0] == '\0' || !(fp = fopen(FileName,"r")));

    printf("\n\n 一、创立无向图的邻接表(Adjacency List)：\n");    
    CreateALGraph(&ALG,fp);
    fclose(fp);
    Prn_ALGraph(ALG);
    printf("\n\n 二、邻接表的图的遍历(Traversing graph)：\n");    
    ALG_Travers(ALG);
     printf("\n\n 三、图的邻接表转换为邻接矩阵(Adjacency Matrix)：\n");    
    AL2AM(ALG,&AMG);
    Prn_AMGraph(AMG);
     printf("\n\n 四、构建最小生成树MST(mininum cost spaning tree)：\n");    
    CreateMST(ALG,AMG);
    printf("\n");system("pause");
    return 0;
}

[1] [2] 下一页