BFS_最短路径
2024-10-13 19:52:18
已知若干个城市的地图,求从一个城市到另一个城市的路径,要求路径中经过的城市最少。
#include<iostream>
#include<cstring>
using namespace std;
int ju[][]=
{{,,,,,,,,},
{,,,,,,,,},
{,,,,,,,,},
{,,,,,,,,},
{,,,,,,,,},
{,,,,,,,,},
{,,,,,,,,},
{,,,,,,,,},
{,,,,,,,,}};
int a[],b[],s[],head,tail;
void print(int d)
{
cout << char(a[d]+);
while(b[d]){
d=b[d];
cout << "--" << char(a[d]+);
}
cout << endl;
}
void bfs()
{
int i;
head=;tail=; //tail依次记录每个节点
a[]=;b[]=;s[]=; //a数组记录每个节点上城市,b数组记录上一个城市的节点,s记录走过的城市
do{
head++;
for(i=;i<=;i++){
if(ju[a[head]][i]== && s[i]==){
tail++;
a[tail]=i;
b[tail]=head;
s[i]=;
if(i==) {
print(tail);
return;
}
}
}
}while(head<tail);
}
int main()
{
memset(s,,sizeof(s));
bfs();
return ;
}
最新文章
- JDK安装,环境配置
- ipad横竖屏尺寸(转载)
- Android系统onKeyDown监控/拦截/监听/屏蔽返回键、菜单键和Home键
- (转) C++ static、const和static const 以及它们的初始化
- centos 安装http协议的git server
- 启语外语培训网SEO历程
- Oracle表空间、段、区和块
- 【转】MAC使用adb工具
- VB6.0连接MySQL数据库
- python混账的编码问题解决之道
- httpappplication 和 httpmodule 的理解(转载,写的很好)
- QPixmap 在非QtCreator环境下无法显示jpg图片
- Java Networking: UDP DatagramSocket (翻译)
- PHP中使用Elasticsearch
- 【CSS】元素样式
- jqgrid 使用自带的行编辑
- [BZOJ1135][POI2009]Lyz[霍尔定理+线段树]
- PLSQL Developer windows 64位连接数据库的问题
- 软工1816 &#183; Beta冲刺(2/7)
- flex版本问题总结