图的操作算法

计算机学院（软件学院）实验报告学生姓名学号实验成绩专业19计科班级2班实验日期2020年11月10日课程名称数据结构与算法任课教师实验名称图的操作算法实验序号实验地点S510实验台号指导教师一、实验目的及要求1.熟悉各种图的存储结构。2．掌握图的各种搜索路径的遍历方法。二、实验内容（或实验原理、实验拓扑）1.任选一种存储结构（邻接表为主），完成图的DFS（深度优先遍历）和BFS（广度优先遍历）的操作（实验题8.1和实验题8.2）2．练习如何构造最小生成树（实验题8.5和实验题8.6）。3.练习如何寻找并求得关键路径并调试出例8.15的拓扑排序。三、实验设备与环境WindowsDEV-C++四、实验设计方案（包括实验步骤、设计思想、算法描述或开发流程等）8.1设计思路CreateMat(&g):创建图，由相关数据构造一个图gDispMat(g):输出图，显示图g的顶点和边信息。DestroyGraph(&g):销毁图，释放图g占用的内存空间。（1）创建图的邻接矩阵voidCreateMat(MatGraph&g,intA[MAXV][MAXV],intn,inte)//创建图的邻接矩阵{inti,j;g.n=n;g.e=e;for(i=0;ig.n;i++)for(j=0;jg.n;j++)g.edges[i][j]=A[i][j];}（2）输出邻接矩阵voidDispMat(MatGraphg){inti,j;for(i=0;ig.n;i++){for(j=0;jg.n;j++){if(g.edges[i][j]!=INF)printf(%4d,g.edges[i][j]);elseprintf(%4s,∞);}printf(\n);}}邻接表创建图的邻接表voidCreateAdj(AdjGraph*&G,intA[MAXV][MAXV],intn,inte)//创建图的邻接表{inti,j;ArcNode*p;G=(AdjGraph*)malloc(sizeof(AdjGraph));for(i=0;in;i++)//给邻接表中所有头结点的指针域置初值NULL{G-adjlist[i].firstarc=NULL;}for(i=0;in;i++)//检查邻接矩阵中的每个元素{for(j=n-1;j=0;j--){if(A[i][j]!=0&&A[i][j]!=INF)//存在一条边{p=(ArcNode*)malloc(sizeof(ArcNode));//创建一个结点pp-adjvex=j;//邻接点编号p-weight=A[i][j];//边的权重p-nextarc=G-adjlist[i].firstarc;//采用头插法插入结点pG-adjlist[i].firstarc=p;}}}G-n=n;G-e=e;}输出邻接表voidDispAdj(AdjGraph*G){ArcNode*p;for(inti=0;iG-n;i++){p=G-adjlist[i].firstarc;printf(顶点%d:,i);while(p!=NULL){printf(%3d[%d]-,p-adjvex,p-weight);//邻接点编号[权重]p=p-nextarc;}printf(∧\n);}}销毁图的邻接表voidDestroyAdj(AdjGraph*&G){ArcNode*pre,*p;for(inti=0;iG-n;i++){pre=G-adjlist[i].firstarc;//pre指向第i个单链表的首结点if(pre!=NULL){p=pre-nextarc;while(p!=NULL)//释放第i个单链表的所有边结点{free(pre);pre=p;p=p-nextarc;}free(pre);}}free(G);//释放头结点数组}8.2DFS(g,v):从顶点v出发深度优先遍历图g.BFS(g,v):从顶点v出发广度优先遍历图g.//递归深度优先遍历voidDFS(ALGraph*G,intv){ArcNode*p;visited[v]=1;printf(%3d,v);p=G-adjlist[v].firstarc;//指向v的第一个邻接点while(p)//查找v的所有临界点{if(visited[p-adjvex]==0)//若当前邻接点未被访问DFS(G,p-adjvex);//p=p-nextarc;//}}//非递归深度优先遍历voidDFS1(ALGraph*G,intv){ArcNode*p;ArcNode*St[MAXV];inttop=-1,i,w;for(i=0;iG-n;i++)visited[i]=0;//恢复环境，使该顶点可重复使用printf(%3d,v);visited[v]=1;top++;St[top]=G-adjlist[v].firstarc;while(top-1){p=St[top];top--;while(p){w=p-adjvex;if(visited[w]==0)//若w未被访问,则递归访问之{printf(%3d,w);visited[w]=1;top++;St[top]=G-adjlist[w].firstarc;break;}p=p-nextarc;//找u的下一个邻接点}}printf(\n);}//广度优先遍历voidBFS(ALGraph*G,intv){ArcNode*p;//定义指针intqueue[MAXV],front=0,rear=0;//定义顶点访问标记数组intw,i;for(i=0;iG-n;i++)//访问标记数组初始化visited[i]=0;printf(%3d,v);//输出被访问顶点编号visited[v]=1;//置已访问标记rear=(rear+1)%MAXV;queue[rear]=v;while(front!=rear){front=(front+1)%MAXV;w=queue[front];p=G-adjlist[w].firstarc;while(p){if(visited[p-adjvex]==0)//若当前邻接点未被访问{printf(%3d,p-adjvex);//访问该邻接点visited[p-adjvex]=1;//置已访问标记rear=(rear+1)%MAXV;queue[rear]=p-adjvex;//该顶点进栈}p=p-nextarc;//找下一个邻接点}}printf(\n);}8.5邻接矩阵的基本运算算法---------------------------*/创建图的邻接矩阵voidCreateMat(MatGraph&g,intA[MAXV][MAXV],intn,inte){inti,j;g.n=n;g.e=e;for(i=0;ig.n;i++)for(j=0;jg.n;j++)g.edges[i][j]=A[i][j];}邻接表的基本运算算法创建图的邻接表G-voidCreateAdj(AdjGraph*&G,intA[MAXV][MAXV],intn,inte){inti,j;ArcNode*p;G=(AdjGraph*)malloc(sizeof(AdjGraph));for(i=0;in;i++)//给邻接表中所有头结点的指针域置初值NULL{G-adjlist[i].firstarc=NULL;}for(i=0;in;i++)//检查邻接矩阵中的每个元素{for(j=n-1;j=0;j--){if(A[i][j]!=0&&A[i][j]!=INF)//存在一条边{p=(ArcNode*)malloc(sizeof(ArcNode));//创建一个结点pp-adjvex=j;//邻接点编号p-weight=A[i][j];//边的权重p-nextarc=G-adjlist[i].firstarc;//采用头插法插入结点pG-adjlist[i].firstarc=p;}}}G-n=n;G-e=e;}8.6邻接矩阵的基本运算算法创建图的邻接矩阵voidCreateMat(MatGraph&g,intA[MAXV][MAXV],intn,inte){inti,j;g.n=n;g.e=e;for(i=0;ig.n;i++)for(j=0;jg.n;j++)g.edges[i][j]=A[i][j];}/*------------输出邻接矩阵g--------------------*/voidDispMat(MatGraphg){inti,j;for(i=0;ig.n;i++){for(j=0;jg.n;j++){if(g.edges[i][j]!=INF)printf(%4d,g.edges[i][j]);elseprintf(%4s,∞);}printf(\n);}}邻接表的基本运算算法创建图的邻接表voidCreateAdj(AdjGraph*&G,intA[MAXV][MAXV],intn,inte){inti,j;ArcNode*p;G=(AdjGraph*)malloc(sizeof(AdjGraph));for(i=0;in;i++)//给邻接表中所有头结点的指针域置初值NULL{G-adjlist[i].firstarc=NULL;}for(i=0;in;i++)//检查邻接矩阵中的每个元素{for(j=n-1;j=0;j--){if(A[i][j]!=0&&A[i][j]!=INF)//存在一条边{p=(ArcNode*)malloc(sizeof(ArcNode));//创建一个结点pp-adjvex=j;//邻接点编号p-weight=A[i][j];//边的权重p-nextarc=G-adjlist[i].firstarc;//采用头插法插入结点pG-adjlist[i].firstarc=p;}}}G-n=n;G-e=e;}-输出邻接表GvoidDispAdj(AdjGraph*G){ArcNode*p;for(inti=0;iG-n;i++){p=G-adjlist[i].firstarc;printf(%d:,i);while(p!=NULL){printf(%3d[%d]-,p-adjvex,p-weight);//邻接点编号[权重]p=p-nextarc;}printf(∧\n);}}销毁图的邻接表voidDestroyAdj(AdjGraph*&G){ArcNode*pre,*p;for(inti=0;iG-n;i++){pre=G-adjlist[i].firstarc;//pre指向第i个单链表的首结点if(pre!=NULL){p=pre-nextarc;while(p!=NULL)//释放第i个单链表的所有边结点{free(pre);pre=p;p=p-nextarc;}free(pre);}}free(G);//释放头结点数组}功能:采用克鲁斯卡尔算法输出图g的一棵最小生成树(n个顶点，n-1条边)voidKruskal(MatGraphg){intu1,v1;intsn1,sn2;inti,j;intk;EdgeE[MAX_SIZE];//存放所有边intvset[MAXV];k=0;//E数组的下标从0开始计printf(图g边集合:\n);for(i=0;ig.n;i++)//由g产生的边集E{for(j=0;j=i;j++){if(g.edges[i][j]!=0&&g.edges[i][j]!=INF){E[k].u=i;E[k].v=j;E[k].w=g.edges[i][j];k++;printf(边(%d,%d)=%d\n,i,j,g.edges[i][j]);}}}insert_sort(E,g.e);//采用直接插入排序方法对E[