文档介绍：数据结构教程上机实验报告实验七、图算法上机实现实验目的:了解熟知图的定义和图的基本术语,掌握图的几种存储结构。掌握邻接矩阵和邻接表定义及特点,并通过实例解析掌握邻接矩阵和邻接表的类型定义。掌握图的遍历的定义、复杂性分析及应用,并掌握图的遍历方法及其基本思想。实验内容:建立无向图的邻接矩阵图的深度优先搜索图的广度优先搜索三、实验步骤及结果:建立无向图的邻接矩阵:源代码:#include""#include""#defineMAXSIZE30typedefstruct{ charvertex[MAXSIZE];//顶点为字符型且顶点表的长度小于MAXSIZE intedges[MAXSIZE][MAXSIZE];//边为整形且edges为邻近矩阵}MGraph;//MGraph为采用邻近矩阵存储的图类型voidCreatMGraph(MGraph*g,inte,intn){//建立无向图的邻近矩阵g->egdes,n为顶点个数,e为边数 inti,j,k; printf("Inputdataofvertexs(0~n-1):\n"); for(i=0;i<n;i++) g->vertex[i]=i;//读入顶点信息 for(i=0;i<n;i++) for(j=0;j<n;j++) g->edges[i][j]=0;//初始化邻接矩阵 for(k=1;k<=e;k++)//输入e条边{ printf("Inputedgesof(i,j):"); scanf("%d,%d",&i,&j); g->edges[i][j]=1; g->edges[j][i]=1; }}voidmain(){ inti,j,n,e; MGraph*g;//建立指向采用邻接矩阵存储图类型指针 g=(MGraph*)malloc(sizeof(MGraph));//生成采用邻接举证存储图类型的存储空间 printf("InputsizeofMGraph:");//输入邻接矩阵的大小 scanf("%d",&n); printf("Inputnumberofedge:");//输入邻接矩阵的边数 scanf("%d",&e); CreatMGraph(g,e,n);//生成存储图的邻接矩阵 printf("OutputMGraph:\n");//输出存储图的邻接矩阵 for(i=0;i<n;i++) { for(j=0;j<n;j++) printf("%4d",g->edges[i][j]); printf("\n"); }}运行结果:图的深度优先搜索:源代码:#include""#include""#defineMAXSIZE30typedefstructnode//邻接表结点{ intadjvex;//邻接点域 structnode*next;//指向下一个邻接边结点的指针域}EdgeNode;//邻接表结点类型typedefstructvnode//顶点表结点{ intvertex;//顶点域 EdgeNode*firstedge;//指向邻接表第一个邻接边节点的指针域}VertexNode;//顶点表结点类型voidCreatAdjlist(VertexNodeg[],inte,intn){//建立无向图的邻接表,n为顶点数,e为边数,g[]存储n个顶点表结点 EdgeNode*p; inti,j,k; printf("Inputdataofvetex(0~n-1);\n"); for(i=0;i<n;i++)//建立有n个顶点的顶点表 { g[i].vertex=i;//读入顶点i信息 g[i].firstedge=NULL;//初始化指向顶点i的邻接表表头指针 } for(k=1;k<=e;k++)//输入e条边 { printf("Inputedgeof(i,j):"); scanf("%d,%d",&i,&j); p=(EdgeNode*)malloc(sizeof(EdgeNode)); p->adjvex=j;//在顶点vi的邻接表中添加邻接点为j的结点 p->next=g[i].firstedge;//插入是在邻接表表头进行的 g[i].firstedge=p; p=(EdgeNode*)malloc(sizeof(EdgeNode)); p->adjvex=i;//在顶点vj的邻接表中添加邻接点为i的结点 p->next=g[j].firstedge;//插入是在邻接表表头进行的 g[j].firstedge=p; }}intvisited[MAXSIZE];//MAXSIZE为大于或等于无向图顶点个数的常量voidDFS(VertexNodeg[],inti){ EdgeN