| 网站首页 | 技术文章 | 下载频道 | 博客 | 编程论坛 |
 
| 技术教程首页 | 开发语言 | WEB开发 | .NET技术 | 数据库 | 操作系统 | 网页制作 |
 
 
您现在的位置: 编程中国 >> 技术教程 >> 开发语言 >> 数据结构 >> 正文
  ►  无向图转换&遍历&MST
无向图转换&遍历&MST
作者:haroldi    阅读人次:……    文章来源:本站原创    发布时间:2007/6/12    网友评论()条
 

原帖地址:http://bbs.bccn.net/thread-129767-1-1.html

请不吝赐教,多多指点...多谢了!
//"有向图"参见http://bbs.bccn.net/thread-130955-1-1.html
#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] 下一页

 

 
文章录入:静夜思    责任编辑:静夜思 
  • 上一篇文章:

  • 下一篇文章:

  •  
    相关文章
    没有相关文章
    原创地带
    24小时热门帖子