《2022年数据结构试验图的建立与运算知识》由会员分享，可在线阅读，更多相关《2022年数据结构试验图的建立与运算知识（6页珍藏版）》请在金锄头文库上搜索。
1、实验报告实验名称：数据结构实验五实验内容： 图的建立与运算实验仪器：计算机学院：计算机学院班级： B 软件工程学号 ：XXXX 姓名：XXX 成绩：指导教师： XXX 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 6 页 - - - - - - - - - 实验五图的建立与运算问题描述建立无向非连通图的邻接表存储结构，要求顶点个数不少于15 个。用 DFS及 BFS对此邻接表进行遍历，打印出两种遍历的顶点访问顺序。给定图中任意两个顶点v1 和 v2 及整数 k，判断是否
2、存在从v1 到 v2 的路径长度为k 的简单路径，若有打印出路径上的顶点序列（要求路径上不含回路）。进一步：找出从v1 到v2 的所有路径长度为k 的简单路径。 （简单路径：顶点序列中不含重现的顶点的路径。）程序代码usingnamespace System; #includestdafx.h #includestdlib.h #includestdio.h #includeconio.h struct node int vertex; struct node *nextnode; ; typedefstruct node *graph; struct node head9; int visi
3、ted9; void creategraph(int node152,int num) graph newnode; graph ptr; int from; int to; int i; for ( i = 0; i vertex = to; newnode-nextnode = NULL; ptr = &(headfrom); while ( ptr-nextnode != NULL ) ptr = ptr-nextnode; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2
4、页，共 6 页 - - - - - - - - - ptr-nextnode = newnode; void dfs(int current) graph ptr; visitedcurrent = 1; printf(vertex%dn,current); ptr = headcurrent.nextnode; while ( ptr != NULL ) if ( visitedptr-vertex = 0 ) dfs(ptr-vertex); ptr = ptr-nextnode; #define MAXQUEUE 10 int queueMAXQUEUE; int front = -1;
5、 int rear = -1; int enqueue( int value) if ( rear = MAXQUEUE ) return -1; rear+; queuerear = value; int dequeue() if ( front = rear ) return -1; front+; return queuefront; void bfs(int current) graph ptr; enqueue(current); visitedcurrent = 1; printf( Vertex%dn,current); while ( front != rear ) curre
6、nt = dequeue(); ptr = headcurrent.nextnode; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 6 页 - - - - - - - - - while ( ptr != NULL ) if ( visitedptr-vertex = 0 ) enqueue(ptr-vertex); visitedptr-vertex = 1; printf( Vertex%dn,ptr-vertex); ptr = ptr-nextnode; vo
7、id main() graph ptr; int node152 = 1, 7, 7, 1, 5, 2, 2, 5, 6, 5, 5, 6, 1, 3, 3, 1, 4, 7, 7, 4, 3, 7, 7, 3, 5, 9, 9, 5, 5, 5; int i; for ( i = 1; i = 8; i+ ) headi.vertex = i; headi.nextnode = NULL; visitedi = 0; creategraph(node,15); printf( 深度优先遍历 :n ); for ( i = 1; i ,headi.vertex); ptr = headi.ne
8、xtnode; while ( ptr != NULL ) printf( %d ,ptr-vertex); ptr = ptr-nextnode; printf(n ); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 6 页 - - - - - - - - - printf(nThe end of the dfs are:n); dfs(1); printf(n ); puts(广度优先遍历 :n ); for ( i = 1; i = 8; i+ ) headi.v
9、ertex = i; headi.nextnode = NULL; visitedi = 0; creategraph(node,15); printf(The content of the graphs allist is:n); for ( i = 1; i ,headi.vertex); ptr = headi.nextnode; while ( ptr != NULL ) printf( %d ,ptr-vertex); ptr = ptr-nextnode; printf(n ); printf(The contents of BFS are:n); bfs(1); printf(n ); puts( Press any key to quit.); getch(); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 6 页 - - - - - - - - - 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 6 页 - - - - - - - - -
