,图的遍历及最小生成树实验报告.doc

实验三最小生成树问题班级:计科 1101 班学号: 0909101605 姓名:杜茂鹏 2013 年5 月 23 日一、实验目的掌握图的存储表示和以及图的最小生成树算法。二、实验内容 ,并且读入图的内容。 。 。 。三、实验要求 ; ; 。四、概要设计、首先采用图的邻接矩阵存储结构,然后从终端输入图的顶点名称、弧以及弧的权值建立邻接矩阵,并将图存储在文件 中。然后利用已经建好的图,分别对其进行深度、广度优先遍历,一次输出遍历的顶点最后建立此图的最小生成树,并将对应的边及权值写入文件 graph_prim .txt 中。六、详细设计实验内容(原理、操作步骤、程序代码) #include<> #include<> #include<> #define INFINITY INT_MAX //最大值#define MAX_VERTEX_NUM 20 //最大顶点个数 int visited[MAX_VERTEX_NUM]; typedef struct ell{ int adj; int *info; //该弧相关信息的指针}ell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedef struct close { char adjvex; int lowcost; }closedge[MAX_VERTEX_NUM]; typedef struct{ char vexs[MAX_VERTEX_NUM]; //顶点向量 AdjMatrix arcs; //邻接矩阵 int vexnum,um; //图的当前顶点数和弧数 closedge cld; }MGraph; typedef struct QNode { char data; struct QNode *next; }QNode,*QueuePtr; typedef struct { QueuePtr front1; QueuePtr rear; }LinkQueue; void (*VisitFunc)(MGraph G,int v); void DFSTraverse(MGraph G,void (* Visit)(MGraph G,int v)); void DFS(MGraph G,int v); void InitQueue(LinkQueue &Q) { ==(QueuePtr)malloc(sizeof(QNode)); if(!) exit(0); ->next=NULL; } void EnQueue(LinkQueue &Q,char e) { QueuePtr p=(QueuePtr)malloc(sizeof(QNode)); if(!p) exit(0); p->data=e; p->next=NULL; ->next=p; =p; } char DeQueue(LinkQu