AutoCAD 3DMAX C语言 Pro/E UG JAVA编程 PHP编程 Maya动画 Matlab应用 Android
Photoshop Word Excel flash VB编程 VC编程 Coreldraw SolidWorks A Designer Unity3D
 首页 > 数据结构

无向图转换&遍历&MST

51自学网 2015-09-08 http://www.51zixue.net

原帖地址: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;
}

<

 

 

 
上一篇:Huffman编码生成程序  下一篇:链表基本操作的程序实现