c语⾔实现图的⼴度和深度搜索,C语⾔实现的图的深度搜索与
⼴度搜索程序
/*
上机试验5-图的建⽴和遍历
1)建⽴【⽆向】【⾮连通】图的邻接表存储结构，要求顶点个数不少于15个。
2)⽤DFS及BFS对此邻接表进⾏遍历，打印出两种遍历的顶点访问顺序。
3)给定图中任意两个顶点v1和v2及整数k，判断是否存在从v1到v2的路径长度为k的简单路径，若有打印出路径上的顶点序列(要求路径上不含回路)。
进⼀步：出从v1到v2的所有路径长度为k的【简单】路径。(简单路径是指：顶点序列中不含【重现】的顶点的路径。)
*/
#include
#include
#include
#define PointNum 15
using namespace std;
struct V{
int vertex;
int distance;
int sign;
struct V* next;
}Vertex[PointNum+1];
int P[PointNum];
int union_find(int x) // 并查集
{
while(P[x]!=x)x=P[x];
return x;
}
void DFS(int vertex_);
void BFS(int vertex_);
int DFS(int V1,  int V2, int V3, int kn);
int lujing[PointNum+1],lujing_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); //要保证vertexNumbers <= PointNum
for( i = 0 ; i < vertexNumbers ; i ++ )
{
Vertex[i].vertex = i;//
Vertex[i].distance = 0;
Vertex[i].sign = 0;
Vertex[i].next = NULL;
}
printf("请输⼊边数:");
scanf("%d",&edgeNumbers); //要保证vertexNumbers <= PointNum
for( i = 0 ; i < edgeNumbers ; i ++ )
{
printf("请输⼊数据:");
scanf("%d%d%d",&V1,&V2,&Distance);
p = &Vertex[V1];q = Vertex[V1].next;
while( q != NULL ){
p = q;
q = q->next;
}//出来的时候q指向Vertex[V1]邻接表的结尾-NULL,
temp = (struct V *)malloc(sizeof(Vertex[0]));
p->next = temp;  temp->next = NULL;//接上temp
temp->vertex = V2; temp->distance = Distance;temp->sign = 0;  //给temp赋值p = &Vertex[V2];q = Vertex[V2].next;
while( q != NULL ){
p = q;
q = q->next;
}
temp = (struct V *)malloc(sizeof(Vertex[0]));///temp的问题
p->next = temp;  temp->next = NULL;//接上temp
temp->vertex = V1;temp->distance = Distance;temp->sign = 0;  //给temp赋值}
for(i = 0 ; i < vertexNumbers ; i ++ )
{
printf("\nDFS遍历的顶点访问顺序 :");
DFS(i);
for(int j = 0 ; j < vertexNumbers ; j ++ )
{
Vertex[j].sign = 0;
}
}
printf("\n");
for(i = 0 ; i < vertexNumbers ; i ++ )
{
for(int j = 0 ; j < vertexNumbers ; j ++ )
{
Vertex[j].sign = 0;
}
printf("\nBFS遍历的顶点访问顺序 :");
BFS(i);
}
for(j = 0 ; j < vertexNumbers ; j ++ )
{
Vertex[j].sign = 0;
}
printf("输⼊v1、v2及整数kn :\n");
scanf("%d%d%d",&v1,&v2,&kn);
for(j = 0 ; j < vertexNumbers ; j ++ )
{
Vertex[j].sign = 0;
}
lujing_I = 0;
DFS(v1,v2,v1,kn);
}
return 0;
}
void BFS(int vertex_)
{
struct V *p = &Vertex[vertex_];
int others[PointNum];
do{
if(Vertex[p->vertex].sign == 0){
printf("%d->",p->vertex);//输出访问节点
Vertex[p->vertex].sign = 1;//代表已经访问过了//
others[p->vertex] = -1;//代表这⼀个可以继续进⾏BFS
}
else others[p->vertex] = p->vertex;//记录已有的点
p = p->next;//主要
}while(p != NULL);
p = &Vertex[vertex_];
while( p->next != NULL )//有些没有连接要考虑~~
{
p = p->next;
if(others[p->vertex] == -1)BFS(p->vertex);
}
}
void DFS(int vertex_)
{
struct V *q = Vertex[vertex_].next;//开始的：p = &Vertex[i];q = Vertex[i].next;
Vertex[vertex_].sign = 1;//代表已经访问过了
printf("%d->",vertex_);//
do{
for(;q != NULL && Vertex[q->vertex].sign == 1;q = q->next);//判断节点是否已经访问过了//原来是q->next != NULL//很⼤的错误:::::::::::::::Vertex[q->vertex].sign == 1不能⽤:::q.sign == 1(********************
if(q == NULL )return;//(q->next == NULL && vertex_Sum == vertexNumbers)
else DFS(q->vertex);//从q->vertex继续深搜索 *********************q->sign居然没有赋初值 //很⼤的错误:::::::::::::::Vertex[q-
>vertex].sign == 1不能⽤:::q->sign == 1(**************
}while( q != NULL );//有些没有连接要考虑~~
}
int DFS(int V1,  int V2, int V3, int kn)
{
struct V *q = Vertex[V1].next;//开始的
int sum,i;
Vertex[V1].sign = 1;//代表已经访问过了c语言搜题软件推荐
lujing[lujing_I ++ ] = V1;//printf("%d->",V1);//
if(V1 == V2)
{
for(sum=0,i=0; i < lujing_I; i++)
{
if(i >= 1 )//从第⼆个点开始
{
for(q = &Vertex[lujing[i-1]]; q != NULL; q = q->next)
{
if( q->vertex == lujing[i])sum += q->distance;
}
}
}
if(kn==sum)
{
printf("%d到%d距离为%d的路径为：",V3,kn,sum);
for(i=0; i < lujing_I; i++)
{
printf("%d->",lujing[i]);
}
printf("%d\n",sum);
}
//return sum;
}
do{
for(;q != NULL && Vertex[q->vertex].sign == 1;q = q->next);//判断节点是否已经访问过了//原来是q->next != NULL//很⼤的错误:::::::::::::::Vertex[q->vertex].sign == 1不能⽤:::q.sign == 1(********************

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。