我想大部分读者都用Floyd或者Dijstra算法,甚至dfs算过最短路吧。
其实BFS也可以计算最短路。(补充:本文只针对无权图,有权图很难用BFS)
当我们用BFS找端对端最短路时,从出发点开始,第一次遍历到终点时过的那条路径就是最短的路径。(读者可以思考一下为什么!)
下面就用邻接表来实现一下BFS最短路,并把路径打出来。
#include<iostream>
#include<fstream>
#include<queue>
using namespace std;
const int MAX = 50;
struct link
{
int data;
link *next;
};
struct Node
{
int v; //顶点相关的信息
link *next;
};
struct Graph
{
Node node[MAX+1]; //所有的结点
int nodeCnt; //用来记录图中结点的数目,这里假设用的是连通图。假设不连通,稍微改一下本程序就行了,具体操作留给读者思考!
};
int visited[MAX+1]; //标志数组
int pa[MAX+1];
/* 读取文件中的数据,构造一个邻接表来表示图 */
Graph readGraph()
{
ifstream cin("c:\\graph.txt");
//表的初始化
Graph graph;
int i ;
for(i = 1; i < MAX; i ++)
{
graph.node[i].v = i;
graph.node[i].next = NULL;
}
int n1 = 0,n2 = 0;
link *s;
graph.nodeCnt = 1;//把结点数初始化为1
while(cin>>n1>>n2)
{
if(graph.nodeCnt < n1) graph.nodeCnt=n1;
if(graph.nodeCnt < n2) graph.nodeCnt=n2;
s = new link;
s->data = n2;
s->next=graph.node[n1].next;
graph.node[n1].next=s; //从尾部插入
//delete(s);
s=new link;
s->data = n1;
s->next=graph.node[n2].next;
graph.node[n2].next=s; //反过来也赋值,说明本程序测试的是无向图,如果是有向图的话读者应该知道怎么改了吧!
//delete(s);
}
return graph;
}
/* 打印邻接表 */
void printGraph(Graph graph)
{
link *p;
for(int i = 1; i <= graph.nodeCnt; i ++)
{
cout<<graph.node[i].v<<" -- ";
p=graph.node[i].next;
while(p!=NULL)
{
cout<<p->data;
p=p->next;
if(p != NULL)
cout<<",";
}
cout<<endl;
}
}
/* 用BFS求最短路径 */
void shortestPath(Graph graph, int s, int d)
{
cout<<"从"<<s<<"到"<<d<<"的bfs最短路求解过程如下:"<<endl;
queue<int> que ;
link * p = NULL;
//int cnt = 0;
int parents = s;
memset(visited,0,sizeof(visited));
memset(pa,0,sizeof(pa));
visited[s] = 1;
pa[s] = -1;
que.push(s);
while(!que.empty()){
p = graph.node[que.front()].next;
parents = que.front();
que.pop();
//cnt ++;
while(p != NULL)
{
if(!visited[p->data])
{
visited[p->data] = 1;
pa[p->data] = parents;
cout<<"访问:"<<p->data<<endl;
if(p->data == d) //找到了目标结点
{
//cout<<"在第"<<cnt<<"层找到目标结点!(出发点算第一层)"<<endl;
break;
}
que.push(p->data);
}
p = p->next;
}
}
cout<<"路径如下:"<<endl;
parents = d;
//cout<<parents<<" <- ";
while(pa[parents] != -1)
{
cout<<parents<<" <- ";
parents = pa[parents];
}
cout<<parents<<endl;
}
int main()
{
int s,d;
Graph graph = readGraph();
printGraph(graph);
while(true)
{
cout<<"请输入起点和终点:"<<endl;
cin>>s>>d;
shortestPath(graph, s , d);
}
return 0;
}
输入文件graph.txt里数据格式如下:
1 2
1 3
1 4
2 4
分享到:
相关推荐
题解:Bfs找最短路径(正解,绝对正确)这是c++中一道题的题解
人工智能大作业:c++代码bfs解决8数码问题
这是a BFS-based shortest path program。其中包含算法和程序源代码,完整的实验报告模板。
用BFS寻找剩余图的最大流值,再进行优化
能够提取最短路径 和最长路径 的 广度优先搜索 BFS (Breadth-first search)代码, 编写语言C++
1.随意设置起点位置 2.随意设置终点位置 3.随意设置障碍物 4.自动bfs寻路,地图上打印寻找的路径
比较DFS与BFS 简单的实现了,小地图范围的两种寻路算法原理的比较。 左键控制,可自动寻找路径,方便观察
估计很多初学者对这个问题一直不明白,为什么使用 BFS 进行广度搜索,一定可以搜索到最短路径。 讲真,在学校里学习 BFS 的时候,自己也没完全明白为什么。老师这么教,课本这么写,我就这么记。 其实回答这个问题很...
ZOJ 1055 Oh, Those Achin Feet.bfs求最短路径.
使用python 随机生成迷宫,带有...界面还有按钮,能够采用DFS和BFS算法来找到从起点到终点的路径,生成的迷宫没有一条路径能够到达起点和终点,会做提示。 界面采用PySimpleGUI实现,总共200多行代码,需要可以下载哈
【二维路径规划】基于Breadth First Search (BFS) 实现二维路径规划附matlab代码
数据结构实验,用C语言编写代码 1. 输入迷宫的相关信息 2. 用栈解决迷宫问题,找到一条通路,输出探索过程和探索路径 3. 找到一条最短路径,输出探索过程和探索路径 4. 如果找不到路径,则输出无路径
详细讲解了骑士的任务用队列方法解决的策略,层层深入
bfs标算,1表示不能走,0表示可以走,求最短路(边权相等)
代码 基于BFS广度优先搜索算法代码代码 基于BFS广度优先搜索算法代码代码 基于BFS广度优先搜索算法代码代码 基于BFS广度优先搜索算法代码代码 基于BFS广度优先搜索算法代码代码 基于BFS广度优先搜索算法代码代码 ...
This is a demo visualizing the execution of various path...不同算法的路径搜寻执行过程可视化程序。 包含5个算法 A* (曼哈顿距离) A* (欧式距离) A* (切比雪夫距离) Dijkstra Bi-Directional Breadth-First-Search
宽度优先搜索算法(又称广度优先搜索)是最简便的图的搜索算法之一,这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。其别名又叫BFS,属于...
在JS中使用递归除法生成迷宫并使用BFS解决它们。 迷宫和解决方案在HTML <canvas>上可视化。
BFS DFS 深度优先搜索 广度优先搜索 图 输出所有路径 输出最短路径 随便输出一条可能的路径