数据结构实验-图实验报告

数据构造实验报告目的要求１．掌握图的储存思想及其储存实现。２．掌握图的深度、广度优先遍历算法思想及其程序实现。３．掌握图的常有应用算法的思想及其程序实现。实验内容１．键盘输入数据，成立一个有向图的毗邻表。２．输出该毗邻表。．在有向图的毗邻表的基础上计算各极点的度，并输出。．以有向图的毗邻表为基础实现输出它的拓扑排序序列。．采纳毗邻表储存实现无向图的深度优先递归遍历。6．采纳毗邻表储存实现无向图的广度优先遍历。7．在主函数中设计一个简单的菜单，分别调试上述算法。源程序：主程序的头文件：行列#include<>#include<>#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineOVERFLOW-2typedefintQElemType;typedefstructQNode{

ata='A'+i;G->vertices[i].firstarc=NULL;}for(i=0;i<G->vexnum;){printf("请输入极点的数组坐标(若退出，请输入-1)：");scanf("%d",&i);if(i==-1)break;printf("请输入极点所指向下一个极点的数组坐标：");scanf("%d",&j);s=(ArcNode*)malloc(sizeof(ArcNode));s->adjvex=j;s->nextarc=G->vertices[i].firstarc;G->vertices[i].firstarc=s;}}5cata);for(p=[i].firstarc;p;p=p->nextarc)printf("%3d",p->adjvex);printf("\n");}}egree=0;G->vertices[i].indegree=0;}irstarc;p;p=p->nextarc){G->vertices[i].degree++;G->vertices[p->adjvex].degree++;G->vertices[p->adjvex].indegree++;}}voidprint_degree(ALGraphG){inti;printf("\nNomdatadegreeindegree\n");for(i=0;i<;i++)printf("\n%4d%5c%7d%8d",i,[i].data,[i].degree,[i].indegree);printf("\n");}ndegree)stack[top++]=i;count=0;while(top!=0){i=stack[--top];if(count==0)printf("%c",[i].data);elseprintf("-->%c",[i].data);count++;for(p=[i].firstarc;p;p=p->nextarc)if(![p->adjvex].indegree)stack[top++]=p->adjvex;}if(count<return(FALSE);elsereturn(TRUE);}irstarc)return0;elsereturn[v].firstarc->adjvex);}irstarc;while(p->adjvex!=u)p=p->nextarc;

出该有向图的度和入度

4.输出该有向图拓扑排序序列

\n");printf("5.

创立一个无向图的毗邻表

6.

深度优先递归遍历该无向图\n");printf("7.广度优先遍历该无向图0.printf("请输当选择：");scanf("%d",&select);switch(select){case1:printf("\n创立一个有向图的毗邻表：

\n");

退出

\n");creat_link(&G);break;case2:printf("\n输出该毗邻表：\n");visit(G);break;case3:printf("\n输出该有向图的度和入度：\n");cacu(&G);print_degree(G);break;case4:printf("\n输出该有向图拓扑排序序列：\n");if(!TopologiSort(G))printf("Toposortisnotsuccess!");break;case5:printf("\n创立一个无向图的毗邻表creat_link(&G);break;case6:printf("\n深度优先递归遍历该无向图DFSTraverse(G);break;

:\n");:\n");case7:printf("\n

广度优先遍历该无向图：

\n");BFSTraverse(G);break;case0:break;default:printf("

输当选项错误！从头输入！

\n");}}while(select);}运转结果截图：主菜单界面：创立一个有向图的领接表输出该毗邻表在有向图的毗邻表的基础上计算各极点的度，并输出。输出它的拓扑排序序列输出所建无向图的毗邻表深度优先递归遍历该无向图广度优先遍历该无向图说明：本实验用的有向图是课本182页图，无向图为课本168页图（a）实验总结此次的图的操作实验，与树的操作近似，但又比树复杂，包括更多的储存构造和遍历方法的操作，并且图的遍历需要沿着弧进行，以便输出弧上的信息。本实验中图的遍历采纳毗邻表的储存构造，在输入