本文实例讲述了java实现利用广度优先遍历(bfs)计算最短路径的方法。分享给大家供大家参考。具体分析如下：
我们用字符串代表图的顶点(vertax)，来模拟学校中classroom, square, toilet, canteen, south gate, north gate几个地点，然后计算任意两点之间的最短路径。
如下图所示：
如，我想从north gate去canteen, 程序的输出结果应为：
bfs: from [north gate] to [canteen]: north gate square canteen
首先定义一个算法接口algorithm:
我要评论
public interface algorithm {
/**
* 执行算法
*/
void perform(graph g, string sourcevertex);
/**
* 得到路径
*/
map<string, string> getpath();
}
然后，定义图:
/**
* (无向)图
*/
public class graph {
// 图的起点
private string firstvertax;
// 邻接表
private map<string, list<string>> adj = new hashmap<>();
// 遍历算法
private algorithm algorithm;
public graph(algorithm algorithm) {
this.algorithm = algorithm;
}
/**
* 执行算法
*/
public void done() {
algorithm.perform(this, firstvertax);
}
/**
* 得到从起点到{@code vertex}点的最短路径
* @param vertex
* @return
*/
public stack<string> findpathto(string vertex) {
stack<string> stack = new stack<>();
stack.add(vertex);
map<string, string> path = algorithm.getpath();
for (string location = path.get(vertex) ; false == location.equals(firstvertax) ; location = path.get(location)) {
stack.push(location);
}
stack.push(firstvertax);
return stack;
}
/**
* 添加一条边
*/
public void addedge(string fromvertex, string tovertex) {
if (firstvertax == null) {
firstvertax = fromvertex;
}
adj.get(fromvertex).add(tovertex);
adj.get(tovertex).add(fromvertex);
}
/**
* 添加一个顶点
*/
public void addvertex(string vertex) {
adj.put(vertex, new arraylist<>());
}
public map<string, list<string>> getadj() {
return adj;
}
}
这里我们使用策略设计模式，将算法与graph类分离，通过在构造graph对象时传入一个algorithm接口的实现来为graph选择遍历算法。
public graph(algorithm algorithm) {
this.algorithm = algorithm;
}
无向图的存储结构为邻接表，这里用一个map表示邻接表，map的key是学校地点(string)，value是一个与该地点相连通的地点表(list<string>)。
// 邻接表 private map<string, list<string>> adj = new hashmap<>();
然后，编写algorithm接口的bfs实现：
/**
* 封装bfs算法
*/
public class broadfristsearchalgorithm implements algorithm {
// 保存已经访问过的地点
private list<string> visitedvertex;
// 保存最短路径
private map<string, string> path;
@override
public void perform(graph g, string sourcevertex) {
if (null == visitedvertex) {
visitedvertex = new arraylist<>();
}
if (null == path) {
path = new hashmap<>();
}
bfs(g, sourcevertex);
}
@override
public map<string, string> getpath() {
return path;
}
private void bfs(graph g, string sourcevertex) {
queue<string> queue = new linkedlist<>();
// 标记起点
visitedvertex.add(sourcevertex);
// 起点入列
queue.add(sourcevertex);
while (false == queue.isempty()) {
string ver = queue.poll();
list<string> tobevisitedvertex = g.getadj().get(ver);
for (string v : tobevisitedvertex) {
if (false == visitedvertex.contains(v)) {
visitedvertex.add(v);
path.put(v, ver);
queue.add(v);
}
}
}
}
}
其中，path是map类型，意为从 value 到 key 的一条路径。
bfs算法描述：
1. 将起点标记为已访问并放入队列。
2. 从队列中取出一个顶点，得到与该顶点相通的所有顶点。
3. 遍历这些顶点，先判断顶点是否已被访问过，如果否，标记该点为已访问，记录当前路径，并将当前顶点入列。
4. 重复2、3，直到队列为空。
测试用例：
string[] vertex = {"north gate", "south gate", "classroom", "square", "toilet", "canteen"};
edge[] edges = {
new edge("north gate", "classroom"),
new edge("north gate", "square"),
new edge("classroom", "toilet"),
new edge("square", "toilet"),
new edge("square", "canteen"),
new edge("toilet", "south gate"),
new edge("toilet", "south gate"),
};
@test
public void testbfs() {
graph g = new graph(new broadfristsearchalgorithm());
addvertex(g);
addedge(g);
g.done();
stack<string> result = g.findpathto("canteen");
system.out.println("bfs: from [north gate] to [canteen]:");
while (!result.isempty()) {
system.out.println(result.pop());
}
}
希望本文所述对大家的java程序设计有所帮助。
如对本文有疑问， 点击进行留言回复！！
sap cloud platform destination的配置
springcloud中feign调用处理mybatis-plus Ipage反序列化问题。
Flume 史上最全面的大数据学习第十篇（一） 别再说不知道flume是什么了
网友评论