package com.example.chantest;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Stack;
public class FindPath {
public interface Algorithm {
//执行算法
void perform(Graph g, String sourceVertex);
//得到路径
Map<String,String> getPath();
}
public static class Graph {
// 图的起点
private String firstVertax;
// 邻接表
private Map<String, List<String>> adj = new HashMap<>();
// 遍历算法
//private Algorithm algorithm;
private BroadFristSearchAlgorithm algorithm;
public Graph(BroadFristSearchAlgorithm bb) {
algorithm = bb;
}
/**
* 执行算法
*/
public void done() {
algorithm.perform(this, firstVertax);
}
/**
* 得到从起点到{@code vertex}点的最短路径
* @param vertex
* @return
*/
public Stack<String> findPathTo(String vertex) {
Stack<String> stack = new Stack<>();//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;
}
}
/**
* 封装BFS算法
*/
public static 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<String, String>();
}
BFS(g, sourceVertex);
System.out.println("\n"+"........");
visitedVertex.clear();//清空集合中被标记的节点
//DFS(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);
//打印当前节点
System.out.print(v+" ");
path.put(v, ver);
queue.add(v);
}
}
}
}
private void DFS(Graph g,String firstVertex){
if(visitedVertex.contains(firstVertex)){
return;
}
visitedVertex.add(firstVertex);
//打印当前节点
System.out.print(firstVertex+" ");
for(int i=0;i<g.getAdj().get(firstVertex).size();i++){
DFS(g,g.getAdj().get(firstVertex).get(i));
}
}
}
public static void main(String[] args){
final String[] str={"NorthGate","ClassRoom","lalala","Square","Toilet","Canteen","South Gate"};
//final String[] str = new String[16];
Graph g = new Graph(new BroadFristSearchAlgorithm());
for(int i=0;i<7;i++){
//str[i]=String.valueOf(i);
g.addVertex(str[i]);
}
g.addEdge(str[0], str[1]);
g.addEdge(str[0], str[2]);
g.addEdge(str[0], str[3]);
g.addEdge(str[1], str[4]);
g.addEdge(str[2], str[4]);
//g.addEdge(str[2], str[5]);
g.addEdge(str[3], str[5]);
g.addEdge(str[4], str[6]);
g.addEdge(str[5], str[6]);
/*
g.addEdge(str[0], str[1]);
g.addEdge(str[0], str[4]);
g.addEdge(str[1], str[2]);
g.addEdge(str[1], str[5]);
g.addEdge(str[2], str[3]);
g.addEdge(str[2], str[6]);
//g.addEdge(str[3], str[7]);
g.addEdge(str[4], str[5]);
g.addEdge(str[4], str[8]);
//g.addEdge(str[5], str[6]);
g.addEdge(str[5], str[9]);
g.addEdge(str[6], str[7]);
g.addEdge(str[6], str[10]);
//g.addEdge(str[7], str[11]);
g.addEdge(str[8], str[9]);
g.addEdge(str[8], str[12]);
g.addEdge(str[9], str[10]);
g.addEdge(str[9], str[13]);
g.addEdge(str[10], str[11]);
g.addEdge(str[10], str[14]);
//g.addEdge(str[11], str[15]);
g.addEdge(str[12], str[13]);
g.addEdge(str[13], str[14]);
g.addEdge(str[14], str[15]);
*/
g.done();
Stack<String> result = g.findPathTo(str[5]);
System.out.println("BFS: From [North Gate] to [Canteen]:");
while (!result.isEmpty()) {
System.out.println(result.pop());
}
}
}
