《c语言实现的图的深度搜索与广度搜索程序》由会员分享，可在线阅读，更多相关《c语言实现的图的深度搜索与广度搜索程序（10页珍藏版）》请在金锄头文库上搜索。
1、C C 语言实现的图的深度搜索与广度搜索程序语言实现的图的深度搜索与广度搜索程序/*上机试验 5-图的建立和遍历1）建立【无向】 【非连通】图的邻接表存储结构，要求顶点个数不少于 15 个。2）用 DFS 及 BFS 对此邻接表进行遍历，打印出两种遍历的顶点访问顺序。3）给定图中任意两个顶点 v1 和 v2 及整数 k，判断是否存在从 v1到 v2 的路径长度为 k 的简单路径，若有打印出路径上的顶点序列（要求路径上不含回路） 。进一步：找出从 v1 到 v2 的所有路径长度为 k 的【简单】路径。 （简单路径是指：顶点序列中不含【重现】的顶点的路径。 ）*/#include#include
2、#include#define PointNum 15using namespace std;struct Vint vertex;int distance;int sign;struct V* next;VertexPointNum+1;int PPointNum; int union_find(int x) / 并查集 while(Px!=x)x=Px;return x;void DFS(int vertex_);void BFS(int vertex_);int DFS(int V1, int V2, int V3, int kn);int lujingPointNum+1,lujing
3、_I;int main() int times,vertexNumbers,edgeNumbers,i,j,V1,V2,Distance,n=1,v1,v2,kn;struct V *p,*q,*temp;printf(“请输入您所要进行的测试次数:“);scanf(“%d“, while(times-)printf(“n 第%d 组数据输入.n“,n+);printf(“请输入顶点数:“);scanf(“%d“, /要保证vertexNumbers next;/出来的时候 q 指向 VertexV1邻接表的结尾-NULL,temp = (struct V *)malloc(sizeof(Ve
4、rtex0);p-next = temp; temp-next = NULL;/接上temptemp-vertex = V2; temp-distance = Distance;temp-sign = 0; /给 temp 赋值p = q = VertexV2.next;while( q != NULL )p = q;q = q-next;temp = (struct V *)malloc(sizeof(Vertex0);/temp 的问题？p-next = temp; temp-next = NULL;/接上temptemp-vertex = V1;temp-distance = Dista
5、nce;temp-sign = 0; /给 temp 赋值for(i = 0 ; i vertex.sign = 0)printf(“%d-“,p-vertex);/输出访问节点Vertexp-vertex.sign = 1;/代表已经访问过了/othersp-vertex = -1;/代表这一个可以继续进行BFSelse othersp-vertex = p-vertex;/记录已有的点p = p-next;/主要while(p != NULL);p = while( p-next != NULL )/有些没有连接要考虑!p = p-next;if(othersp-vertex = -1)B
6、FS(p-vertex);void DFS(int vertex_)struct V *q = Vertexvertex_.next;/开始的：p = q = Vertexi.next;Vertexvertex_.sign = 1;/代表已经访问过了 printf(“%d-“,vertex_);/dofor(;q != NULL q = q-next);/判断节点是否已经访问过了/原来是 q-next != NULL/很大的错误:Vertexq-vertex.sign = 1 不能用:q.sign = 1(*if(q = NULL )return;/(q-next = NULL /从 q-ve
7、rtex 继续深搜索 *q-sign 居然没有赋初值! /很大的错误:Vertexq-vertex.sign = 1 不能用:q-sign = 1(*while( q != NULL );/有些没有连接要考虑!int DFS(int V1, int V2, int V3, int kn)struct V *q = VertexV1.next;/开始的int sum,i;VertexV1.sign = 1;/代表已经访问过了 lujinglujing_I + = V1;/printf(“%d-“,V1);/if(V1 = V2)for(sum=0,i=0; i = 1 )/从第二个点开始for(
8、q = q != NULL; q = q-next)if( q-vertex = lujingi)sum += q-distance;if(kn=sum)printf(“%d 到%d 距离为%d 的路径为：“,V3,kn,sum);for(i=0; i “,lujingi);printf(“%dn“,sum);/return sum;dofor(;q != NULL q = q-next);/判断节点是否已经访问过了/原来是 q-next != NULL/很大的错误:Vertexq-vertex.sign = 1 不能用:q.sign = 1(*if(q = NULL )return -1;/
9、(q-next = NULL /从 q-vertex 继续深搜索 *q-sign 居然没有赋初值! /很大的错误:Vertexq-vertex.sign = 1 不能用:q-sign = 1(*Vertexq-vertex.sign = 0;lujing_I - ;q = q-next;while( q != NULL );/有些没有连接要考虑!return 0;/*输入：10440 1 340 2 551 3 552 3 340 3 89550 1 10 3 10 4 11 2 11 3 17100 1 120 4 341 2 431 5 5432 3 542 4 542 5 543 6 6
10、44 5 645 6 65415160 1 11 2 11 10 12 3 13 4 14 5 15 6 16 7 16 14 17 8 18 9 19 10 110 11 111 12 112 13 113 14 1555 4 120 1 120 2 32 3 0 434 0 43输出：DFS 遍历的顶点访问顺序 :0 - 1 - 2 - 3 - 4 -DFS 遍历的顶点访问顺序 :1 - 0 - 3 - 4 - 2 -DFS 遍历的顶点访问顺序 :2 - 1 - 0 - 3 - 4 -DFS 遍历的顶点访问顺序 :3 - 0 - 1 - 2 - 4 -DFS 遍历的顶点访问顺序 :4 -
11、0 - 1 - 2 - 3 -BFS 遍历的顶点访问顺序 :0 - 1 - 3 - 4 - 2 -BFS 遍历的顶点访问顺序 :1 - 0 - 2 - 3 - 4 -BFS 遍历的顶点访问顺序 :2 - 1 - 0 - 3 - 4 -BFS 遍历的顶点访问顺序 :3 - 0 - 1 - 4 - 2 -BFS 遍历的顶点访问顺序 :4 - 0 - 1 - 3 - 2 -DFS 遍历的顶点访问顺序 :0 - 1 - 2 - 3 - 6 - 5 - 4 -DFS 遍历的顶点访问顺序 :1 - 0 - 4 - 2 - 3 - 6 - 5 -DFS 遍历的顶点访问顺序 :2 - 1 - 0 - 4 -
12、5 - 6 - 3 -DFS 遍历的顶点访问顺序 :3 - 2 - 1 - 0 - 4 - 5 - 6 -DFS 遍历的顶点访问顺序 :4 - 0 - 1 - 2 - 3 - 6 - 5 -DFS 遍历的顶点访问顺序 :5 - 1 - 0 - 4 - 2 - 3 - 6 -DFS 遍历的顶点访问顺序 :6 - 3 - 2 - 1 - 0 - 4 - 5 -BFS 遍历的顶点访问顺序 :0 - 1 - 4 - 2 - 5 - 3 - 6 -BFS 遍历的顶点访问顺序 :1 - 0 - 2 - 5 - 4 - 3 - 6 -BFS 遍历的顶点访问顺序 :2 - 1 - 3 - 4 - 5 - 0 - 6 -BFS 遍历的顶点访问顺序 :3 - 2 - 6 - 1 - 4 - 5 - 0 -BFS 遍历的顶点访问顺序 :4 - 0 - 2 - 5 - 1 - 3 - 6 -BFS 遍历的顶点访问顺序 :5 - 1 - 2 - 4 - 6 - 0 - 3 -BFS 遍历的顶点访问顺序 :6 - 3 - 5 - 2 - 1 - 4 - 0 -第 3 组数据输入.请输入顶点数:*/
