原帖地址：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("第二行： 1616\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]下一页