实验三 图的存储结构及各种运算的实现.docx

实验三 图的存储结构及各种运算的实现（必做） 计算机与信息技术学院14级3班黄雨梅201421012808计算机科学与技术 实验目的： 1、 掌握图的逻辑结构及其常用的存储表示方法，建立图的邻接表与邻接矩阵。2、 熟练掌握图的深度与广度优先搜索算法的基本思想，并能在不同存储结构上实现算法。3、 深入理解最小生成树的定义，掌握Prim算法和Kruskar算法构造最小生成树的基本思想，并实现Prim算法。4、 掌握用DIJKSTTRA算法求解单源最短路径的基本过程和算法。实验学时:8实验内容：1、建立图的邻接表与邻接矩阵，并在不同存储结构上实现深度与广度优先搜索算法。 2、用Prim算法构造带权网络的最小生成树。 3、用DIJKSTTRA算法求解单源最短路径。 选做部分4、求拓朴序列和关键路径。 第一题： 建立图的邻接表与邻接矩阵，并在不同存储结构上实现深度与广度优先搜索算法 #include #include #define INFINITY 32767 #define MAX_VEX 20 #define QUEUE_SIZE (MAX_VEX+1) bool *visited; typedef struct char *vexs; /顶点向量 int arcsMAX_VEXMAX_VEX; /邻接矩阵 int vexnum,arcnum; /图的当前顶点数和弧数 Graph; /队列类 class Queue public: void InitQueue() base=(int *)malloc(QUEUE_SIZE*sizeof(int); front=rear=0; void EnQueue(int e) baserear=e; rear=(rear+1)%QUEUE_SIZE; void DeQueue(int &e) e=basefront; front=(front+1)%QUEUE_SIZE; public: int *base; int front; int rear; ; /图G中查找元素c的位置 int Locate(Graph G,char c) for(int i=0;iG.vexnum;i+) if(G.vexsi=c) return i; return -1; /创建无向网 void CreateUDN(Graph &G) int i,j,w,s1,s2; char a,b,temp; printf(输入顶点数和弧数: ); scanf(%d%d,&G.vexnum,&G.arcnum); temp=getchar(); /接收回车 G.vexs=(char *)malloc(G.vexnum*sizeof(char); /分配顶点数目 printf(输入%d个顶点.n,G.vexnum); for(i=0;iG.vexnum;i+) /初始化顶点 printf(输入顶点%d: ,i); scanf(%c,&G.vexsi); temp=getchar(); /接收回车 for(i=0;iG.vexnum;i+) /初始化邻接矩阵 for(j=0;jG.vexnum;j+) G.arcsij=INFINITY; printf(输入%d条弧.n,G.arcnum); for(i=0;i=0 & kG.vexnum) /k合理 for(int i=0;i=0 & i=0 & jG.vexnum) /i,j合理 for(int k=j+1;kG.vexnum;k+) if(G.arcsik!=INFINITY) return k; return -1; /深度优先遍历 void DFS(Graph G,int k) int i; if(k=-1) /第一次执行DFS时,k为-1 for(i=0;i=0;i=NextVex(G,k,i) if(!visitedi) /对k的尚未访问的邻接顶点i递归调用DFS DFS(G,i); /广度优先遍历 void BFS(Graph G) int k; Queue Q; /辅助队列Q Q.InitQueue(); for(int i=0;i=0;w=NextVex(G,k,w) if(!visitedw) /w为k的尚未访问的邻接顶点 visitedw=true; printf(%c ,G.vexsw); Q.EnQueue(w); /主函数 void main() int i; Graph G; CreateUDN(G); visited=(bool *)malloc(G.vexnum*sizeof(bool); printf(n深度优先遍历: ); for(i=0;iG.vexnum;i+) visitedi=false; DFS(G,-1); /* NODE: DFS */ printf(n广度优先遍历: ); for(i=0;iG.vexnum;i+) visitedi=false; BFS(G); /* NODE: BFS */ printf(n程序结束.n); 结果拷屏：第二题：用Prim算法构造带权网络的最小生成树。#include#include#define FALSE 0#define TRUE 1#define max 10typedef char vextype;typedef int adjtype;typedef struct vextype vexsmax;adjtype arcsmaxmax;graph;typedef structint fromvex,endvex;int length;edge;edge Tmax-1;graph g;int n,e;int visitedmax;/建立无向图的邻接矩阵;void creategraph(graph *ga) int i,j,k,w; printf(请输入顶点数和边数:); scanf(%d%d,&n,&e); printf(请输入顶点信息:); getchar(); for(i=0;ivexsi=getchar(); getchar(); for(i=0;in;i+) for(j=0;jarcsij=100; printf(请输入边和权值，用空格间隔，每组输完用回车:n); for(k=0;karcsij=ga-arcsji=w; /最小生成树prim算法;prim()int j,k,m,v,min,nmax=1000;int d;edge e;for(j=1;jn;j+)Tj-1.fromvex=1;Tj-1.endvex=j+1;Tj-1.length=g.arcs0j;for(k=0;kn-1;k+)min=nmax;for(j=k;jn-1;j+)if(Tj.lengthmin)min=Tj.length;m=j;e=Tm;Tm=Tk;Tk=e;v=Tk.endvex;for(j=k+1;jn-1;j+)d=g.arcsv-1Tj.endvex-1;if(dTj.length) Tj.length=d;Tj.fromvex=v; void main() int i,j; creategraph(&g); printf(顶点信息: ); for(i=0;in;i+) printf(%c,g.vexsi); printf(n); printf(图的邻接矩阵是:n); for(i=0;in;i+) for(j=0;jn;j+) printf( %d,g.arcsij); printf(n); printf(最小生成树是:n);prim();for(i=0;i%d:%dn,Ti.fromvex,Ti.endvex,Ti.length);printf(n);拷屏：第三题：用DIJKSTTRA算法求解单源最短路径#include #include #define true 1#define false 0#define nmax 10#define MAX 1000typedef char vextype;typedef int adjtype;typedef struct vextype vexsnmax; adjtype arcsnmaxnmax; graph;typedef struct int fromvex,endvex; int length; edge;graph g;int n,e;int visitednmax;void creategraph(graph *ga) int i,j,k,w; printf(请输入顶点数和边数:); scanf(%d%d,&n,&e); printf(请输入顶点信息:); getchar(); for(i=0;ivexsi=getchar(); getchar(); for(i=0;in;i+) for(j=0;jarcsij=MAX; printf(请输入顶点对序号和权值:); for(k=0;karcsij=w; void dijkstra(int Cnmax,int v) int Dnmax; int Pnmax,Snmax; int i,j,k,v1,pre; int min; v1=v-1; for(i=0;in;i+) Di=Cv1i; if(Di!=MAX) Pi=v; else Pi=0; for(i=0;in;i+) Si=0; Sv1=1; Dv1=0; for(i=0;in;i+) min=MAX+1; for(j=0;jn;j+) if(!Sj) & (Djmin) min=Dj; k=j; Sk=1; for(j=0;jDk+Ckj) Dj=Dk+Ckj; Pj=k+1; for(i=0;in;i+) printf(%dt%d,Di,i+1); pre=Pi; while(pre!=0) printf(-%d,pre); pre=Ppre-1; printf(n); void main() int i,j; creategraph(&g); print