#include<stdio.h>
#include<stdlib.h>
typedef struct node
{
int adjvex;
struct node *next;
}EdgeNode;
typedef struct vnode
{
char c;
EdgeNode *firstedge;
}VertexNode;
VertexNode AdjList[10001];
int pre[10001]; //用于记录各节点的前驱
int d[10001]; //用于记录用原点到各节点的距离
void InPut(int n,int e) //节点及边的录入 以及建立邻接表
{
int i,j,s,d,find;
char ch1,ch2;
EdgeNode *p,*q;
printf("请输入一次输入所有字符节点 且第一个输入的点默认为源节点\n");
for(i=0;i<n;i++)
{
scanf("%c ",&AdjList[i].c);
AdjList[i].firstedge=NULL;
}
printf("请输入各条边\n");
for(i=1;i<=e;i++)//建立邻接表 由于是无向图则要申请两个节点p和q
{
find=0;
scanf("%c %c ",&ch1,&ch2);
for(j=0;find!=2&&j<n;j++)
if(ch1==AdjList[j].c)
{
s=j;
find++;
}
else if(ch2==AdjList[j].c)
{
d=j;
find++;
}
p=(EdgeNode*)malloc(sizeof(EdgeNode));//由于是无向图则要申请两个节点p和q
q=(EdgeNode*)malloc(sizeof(EdgeNode));
p->adjvex=d;
p->next=AdjList[s].firstedge;
AdjList[s].firstedge=p;
q->adjvex=s;
q->next=AdjList[d].firstedge;
AdjList[d].firstedge=q;
}
}
void BFS(int n)//广度搜索
{
int color[10001]; //1代表白色表示该点尚未发现 2代表灰色现已发现 3代表黑色表示与它邻接的边已发现
int i,u,v,max=100000000;
int queue[10001],head,tail;
EdgeNode *p;
for(i=0;i<n;i++)
{
d[i]=max;
color[i]=1;//1代表白色表示该点尚未发现
pre[i]=-1;
}
color[0]=2;//2代表灰色 原点 现已发现
d[0]=0;
pre[0]=-1;
head=0; tail=-1;//队列置空
queue[++tail]=0;//源点进队
while(head<=tail)
{
u=queue[head++];//出队
p=AdjList[u].firstedge;
while(p)//搜索所有以u的邻接边 即点v 并进队
{
v=p->adjvex;
if(color[v]==1)
{
color[v]=2;
d[v]=d[u]+1;
pre[v]=u;
queue[++tail]=v;
}
p=p->next;
}
color[u]=3;//所有以u的邻接边已发现 并把u点置为黑色表示完成
}
}
void printpath(int i,int n)//递归输出源点到各点的路径
{
if(pre[i]==-1)
{
printf("%c->",AdjList[i].c);
return ;
}
else
{
printpath(pre[i],n);
if(i==n)
printf("%c",AdjList[i].c);
else
printf("%c->",AdjList[i].c);
}
}
void print(int n)////输出源点到各点的长度及路径
{
int i;
for(i=1;i<n;i++)
{
printf("%d: ",d[i]);
printpath(i,i);//递归输出源点到各点的路径
printf("\n");
}
}
int main()
{ freopen("1.txt","r",stdin);
int n,e;
printf("请输入字符节点的个数N 和边的数目E:\n");
scanf("%d%d ",&n,&e);
InPut(n,e); //节点及边的录入 以及建立邻接表
BFS(n);//广度搜索
print(n);//输出源点到各点的长度及路径
return 0;
}
分享到:
相关推荐
TSP广度搜索算法C++ TSP广度搜索算法C++
利用队列实现图的广度搜索,层次结构清晰,代码质量高,能够加深对图的广度搜索认识
深度搜索和广度搜索 两种C版本的 需要的可以下载 希望对大家有所帮助
广度搜索是一项重要的软件设计技术,该例采用C编程实现了3个水杯倒水,采用广度搜索的实现算法
盲目搜索(广度搜索)解重排九宫问题,即把数码问题的盲目搜索求解!C++实现的。
可以用一种称为广度搜索的算法,将迷宫的入点(1,1)作为第一个出发点,向四周搜索可通行的位置,形成第一层新的出发点,然后对第一层中各个位置再分别向四周搜索可通行的位置,形成第二层新的出发点,如此进行下去...
人工智能实验: 实现结果:给定八数码的起始...最简单的方法是在上述深度搜索代码上进行改动,即可进行广度搜索。 深度是将集合中的元素从末尾取出,即和栈的特点相同,那么将先进后出变为先进先出,即将栈改成了队列。
迷宫深度搜索和广度搜索 是否可以走出迷宫和最短路径 1234567890
图(邻接矩阵,深度搜索,广度搜索,最小生成树,prime,kruskal,AOV,AOE,最短路径)代码和讲解,内容详细全面,通俗易懂,通过测试,代码可以直接使用,方便大家学习.
图 拓扑排序 深度搜索 广度搜索 最小生成树
NULL 博文链接:https://wwwjjq.iteye.com/blog/1606337
我知道这不值钱,但我穷的没点下载东西了。希望需要的兄弟赞助下。 c/c++用递归实现深度搜索和广度搜索解迷宫的源码。 广度搜索可找出迷宫的最优路径。
此文本中包括了图论中的经典的广度搜索算法,算法运算效率还可以。
边集数组的非递归深度搜索遍历和广度搜索遍
用C++写的 BFS (brand first search)广度优先搜索
使用广度搜索的方法实现八数码问题,代码GCC亲自测试无误,有备注,有题目说明
用C语言编写的深度、广度搜索代码,方便C语言初学者使用!
适合大学生,学生党学习c++的二叉树的广度搜索遍历的c++程序。
图(邻接表,深度搜索,广度搜索,最小生成树,prime,kruskal,AOV,AOE,最短路径)代码和讲解,内容详细全面,通俗易懂,通过测试,代码可以直接使用,方便大家学习.