이 기사의 예에서는 Java가 최단 경로를 계산하기 위해 BFS(Breadth-First Traversal)를 구현하는 방법을 설명합니다. 참고할 수 있도록 모든 사람과 공유하세요. 구체적인 분석은 다음과 같습니다.
우리는 문자열을 사용하여 학교의 교실, 광장, 화장실, 매점, 남문 및 북문 위치를 시뮬레이션하기 위해 그래프의 정점을 표현한 다음 두 지점 사이의 최단 경로를 계산합니다.
아래와 같이:
예를 들어 North Gate에서 Canteen으로 이동하려는 경우 프로그램의 출력은 다음과 같아야 합니다.
BFS: [북문]에서 [식당]까지:북문SquareCanteen
먼저 알고리즘 인터페이스 알고리즘을 정의합니다.
public interface Algorithm { /** * 알고리즘 실행*/ void Perform(Graph g, String sourceVertex) /** * 경로 가져오기*/ Map<String, String> getPath();}그런 다음 그래프를 정의합니다.
/** * (무방향) graph*/public class Graph { // 그래프의 시작점 private String firstVertax; // 인접 목록 private Map<String, List<String>> adj = new HashMap<>() / / 순회 알고리즘 private Algorithm 알고리즘; public Graph(Algorithm 알고리즘) { this.algorithm = 알고리즘 } /** * 알고리즘 실행*/ public void done() { 알고리듬.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 = 알고리듬.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에 대한 순회 알고리즘을 선택합니다.
공개 그래프(알고리즘 알고리즘) { this.algorithm = 알고리즘 }무방향 그래프의 저장 구조는 인접 리스트(Adjacency List)이다. 여기서 맵의 키는 학교 위치(String)이고 값은 위치 리스트(List<String>)이다. 위치와 연결됩니다.
// 인접 목록 private Map<String, List<String>> adj = new HashMap<>();
그런 다음 알고리즘 인터페이스의 BFS 구현을 작성합니다.
/** * BFS 알고리즘을 캡슐화합니다*/public class BroadFristSearchAlgorithm Implements Algorithm { // 방문한 위치 저장 private List<String> VisitVertex; // 최단 경로 저장 private Map<String, String> path @Override public void done( Graph g, String sourceVertex) { if (null == VisitVertex) { VisitVertex = 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> 대기열 new LinkedList<>(); // 시작점을 표시합니다.Vertex.add(sourceVertex); // 시작점을 대기열에 넣습니다. while(false == queue.isEmpty()) { String ver = queue.poll(); List<String> toBeVisitedVertex = g.getAdj().get(ver) for (String v : toBeVisitedVertex) { if (false == VisitVertex.contains( v)) { VisitVertex.add(v); path.put(v, ver); } } }}그 중 path는 Map타입으로 값에서 키까지의 경로를 뜻합니다.
BFS 알고리즘 설명:
1. 출발지를 방문했다고 표시하고 대기열에 넣습니다.
2. 큐에서 꼭지점을 가져와서 꼭지점에 연결된 모든 꼭지점을 가져옵니다.
3. 이 정점을 탐색하고 먼저 정점을 방문했는지 여부를 결정하고 방문하지 않은 경우 해당 지점을 방문한 것으로 표시하고 현재 경로를 기록하고 현재 정점을 대기열에 넣습니다.
4. 대기열이 빌 때까지 2단계와 3단계를 반복합니다.
테스트 케이스:
String[] vertex = {"북문", "남문", "교실", "광장", "화장실", "식당"} Edge[] edge = { new Edge("북문", "교실" ), new Edge("북문", "광장"), new Edge("교실", "화장실"), new Edge("광장", "화장실"), new Edge("광장", "식당"), new Edge("화장실", "남문"), new Edge("화장실", "남문"), };@Test public void testBFS() { Graph g = new Graph(new BroadFristSearchAlgorithm( )); addVertex(g); g.done(); Stack<String> result = g.findPathTo("Canteen"); System.out.println("BFS: [북문]에서 [식당]까지:"); while (!result.isEmpty()) { System.out.println(result.pop());이 글이 모든 사람의 Java 프로그래밍에 도움이 되기를 바랍니다.