实验六：图的遍历与最小生成树

1、实验六 图的邻接矩阵存储和最小生成树一、实验目的1掌握图的邻接矩阵存储结构（或邻接表）2掌握图的深度优先遍历和广度优先遍历算法2掌握图的最小生成树算法（Prim算法）二、实验内容按下图所示无向带权图，实现以下各项功能。图1 无向带权图1用图的邻接矩阵（或者邻接表）的方式存储图1的无向带权图。2输出该无向带权图的顶点序列以及权值集合（采用邻接矩阵存储）。3分别采用深度优先和广度优先算法遍历该无向图4采用Prim算法求该无向带权图的最小生成树。 要求：实验后用专用实验纸书写报告。报告中要说明实验题目，内容；分析实验过程，总结实验结果。三、设计指导1）创建一个头文件seqlist.h用来保存顺序表相

2、关函数。#define MaxSize 100typedef char DataType;typedef structDataType listMaxSize;int size;SeqList;/初始化ListInitiate(L)void ListInit(SeqList *L) L-size = 0;/*定义初始数据元素个数*/ /求当前数据元素个数ListLength(L)int ListLength(SeqList L) return L.size; /插入数据元素ListInsert(L, i, x)int ListInsert(SeqList *L, int i, DataType

3、 x) int j;for(j = L-size; j i; j-) L-listj = L-listj-1; /*依次后移*/L-listi = x; /*插入x*/L-size +; /*元素个数加1*/return 1;/删除数据元素ListDelete(L, i, x)int ListDelete(SeqList *L, int i, DataType *x) int j; *x = L-listi;/*保存删除的元素到x中*/for(j = i +1; j size-1; j+) L-listj-1 = L-listj;/*依次前移*/ L-size-;/*数据元素个数减1*/ re

4、turn 1;/取数据元素ListGet(L, i, x)int ListGet(SeqList L, int i, DataType *x) if(i L.size-1) printf(参数i不合法! n); return 0;else*x = L.listi; return 1;2）创建一个头文件seqcqueue.h用来保存循环队列相关函数。#include#define MaxQueueSize 20typedef struct DataType queueMaxQueueSize; int rear; int front; int count; SeqCQueue; /初始化Queu

5、eInit(Q)void QueueInit(SeqCQueue *Q) Q-rear = 0; Q-front = 0; Q-count = 0;/非空否QueueNotEmpty(Q)int QueueNotEmpty(SeqCQueue Q) if(Q.count != 0)return 1; else return 0;/入队列QueueAppend(Q, x)int QueueAppend(SeqCQueue *Q, DataType x) if(Q-count 0 & Q-rear = Q-front) printf(队列已满无法插入! n); return 0; else Q-q

6、ueueQ-rear = x; Q-rear = (Q-rear + 1) % MaxQueueSize; Q-count+; return 1; /出队列QueueDelete(Q, d)int QueueDelete(SeqCQueue *Q, DataType *d) if(Q-count = 0) printf(队列已空无数据元素出队列! n); return 0; else *d = Q-queueQ-front; Q-front = (Q-front + 1) % MaxQueueSize; Q-count-; return 1; /取队头数据元素QueueGet(Q, d)int

7、 QueueGet(SeqCQueue Q, DataType *d) if(Q.count = 0) printf(队列已空无数据元素可取! n); return 0; else *d = Q.queueQ.front; return 1; 3）主函数中包含的部分函数#include#include#include SeqList.h#includeSeqCQueue.h#define MaxWeight 10000#define MaxVertices 10typedef char VerT;/图的结构体定义typedef structSeqList Vertices;int edgeMa

8、xVerticesMaxVertices;int numOfEdges;AdjMGraph;/边信息结构体定义typedef structint row;int col;int weight;RowColWeight;/最小生成树结构体typedef struct VerT vertex; int weight;MinSpanTree;int visited110=0;int visited210=0;/图的初始化void GraphInit(AdjMGraph *G,int n)/请大家自己完成！/插入顶点void InsertVertex(AdjMGraph *G,DataType ver

9、tex)/请大家自己完成！/插入一条边void InsertEdge(AdjMGraph *G,int v1,int v2,int weight)/请大家自己完成！/删除一条边void DeleteEdge(AdjMGraph *G,int v1,int v2)/请大家自己完成！/取第一个邻接顶点int GetFirstVex(AdjMGraph G,int v)/请大家自己完成！/取下一个邻接顶点int GetNextVex(AdjMGraph G,int v1,int v2)/请大家自己完成！/创建图函数void CreateGraph(AdjMGraph *G,DataType V,in

10、t n,RowColWeight E,int e)int i,k;GraphInit(G,n);for(i=0;in;i+)InsertVertex(G,Vi);for(k=0;ke;k+)InsertEdge(G,Ek.row,Ek.col,Ek.weight);void Visit(DataType item)printf(%c ,item);/图的深度优先遍历算法void DepthFSearch(AdjMGraph G,int v)/请大家自己完成！/图的广度优先遍历算法void BroadFSearch(AdjMGraph G,int v)/请大家自己完成！/Prim算法建立带权图的

11、最小生成树void Prim(AdjMGraph G, MinSpanTree closeVertex) /请大家自己完成！void main()AdjMGraph g1;DataType a=A,B,C,D,E,F,G;RowColWeight rcw=0,1,50,1,0,50,0,2,60,2,0,60,1,3,65,3,1,65,1,4,40,4,1,40,2,3,52,3,2,52,2,6,45,6,2,45,3,4,50,4,3,50,3,5,30,5,3,30,3,6,42,6,3,42,4,5,70,5,4,70;int n=7,e=20;int i,j;MinSpanTree

12、 closeVertex7; CreateGraph(&g1,a,n,rcw,e);/DeleteEdge(&g1,0,4);printf(顶点集合为：n);for(i=0;ig1.Vertices.size;i+)printf(%c ,g1.Vertices.listi);printf(n);printf(权值集合为：n);for(i=0;ig1.Vertices.size;i+)for(j=0;jg1.Vertices.size;j+)printf(%5d ,g1.edgeij);printf(n);printf(深度优先遍历序列为：n);DepthFSearch(g1,0);printf(n广度优先遍历序列为：n);BroadFSearch(g1,0);