Untitled
unknown
java
3 years ago
5.6 kB
6
Indexable
import java.util.Scanner; import java.util.ArrayList; import java.util.List; import java.util.*; public class Main { public static void main(String[] args) { System.out.println("Введите вершине в формате \"PARENT CHILD\". Для завершения ввода \"exit\""); Scanner scanner = new Scanner(System.in); Graph graph = new Graph(); String line = scanner.nextLine(); while (!line.equals("exit")){ String[] nodes = line.toUpperCase().split("\\s"); graph.addPath(nodes[0], nodes[1]); line = scanner.nextLine(); } System.out.println("Введите начальную вершину и вершину для поиска"); String start = scanner.nextLine(); String end = scanner.nextLine(); System.out.println("BFS"); graph.BFS(start, end); System.out.println("\nDFS"); graph.DFS(start, end); System.out.println("\nDFS REC"); graph.DFSRecursion(start, end); } } class Node { private Node parent; private final String name; private final List<Node> children; public Node(String name){ this.name = name; children = new ArrayList<>(); } public void addChildren(Node node){ children.add(node); } public String getName() { return name; } public List<Node> getChildren() { return children; } public Node getParent() { return parent; } public void setParent(Node parent) { this.parent = parent; } } class Graph { List<Node> nodeList; public Graph() { this.nodeList = new ArrayList<>(); } public void addPath(String parentName, String childName){ Node parent = createNode(parentName); Node child = createNode(childName); parent.addChildren(child); child.setParent(parent); } private Node createNode(String name){ for(Node node : nodeList){ if(node.getName().equals(name)){ return node; } } Node newNode = new Node(name); nodeList.add(newNode); return newNode; } public void DFS(String startNode, String endNode){ Node start = getNode(startNode); Node end = getNode(endNode); showShortPath(start, end); ArrayDeque<Node> queue = new ArrayDeque<>(); List<Node> path = new ArrayList<>(); queue.addFirst(start); while (!queue.isEmpty()){ Node node = queue.pollFirst(); path.add(node); if(node.getName().equalsIgnoreCase(end.getName())){ showPath(path); return; } Node[] reverse = node.getChildren().toArray(new Node[0]); for(int i = reverse.length - 1; i >= 0; --i){ queue.addFirst(reverse[i]); } } } public void DFSRecursion(String startNode, String endNode){ Node start = getNode(startNode); Node end = getNode(endNode); showShortPath(start, end); List<Node> path = new ArrayList<>(); DFSRecursion(start, end, path); } private void DFSRecursion(Node current, Node end, List<Node> path){ path.add(current); if(current.getName().equalsIgnoreCase(end.getName())){ showPath(path); return; } for(Node node : current.getChildren()){ DFSRecursion(node, end, path); } } private void showShortPath(Node start, Node end){ Node current = end; int i = 0; System.out.print("Кратчайший путь: "); while (current != null && !current.getName().equalsIgnoreCase(start.getName())){ if(i != 0){ System.out.print("->"); } System.out.print(current.getName()); current = current.getParent(); i++; } if(current != null && current.getName().equalsIgnoreCase(start.getName())){ System.out.print("->" + current.getName()); } System.out.println(" "); } private void showPath(List<Node> nodes){ System.out.print("Весь путь: "); int index = 0; for(Node node : nodes){ if(index != 0){ System.out.print(" -> "); } System.out.print(node.getName()); index++; } System.out.println(" "); } public void BFS(String startNode, String endNode){ Node start = getNode(startNode); Node end = getNode(endNode); ArrayDeque<Node> queue = new ArrayDeque<>(); List<Node> path = new ArrayList<>(); showShortPath(start, end); queue.add(start); while (!queue.isEmpty()){ Node node = queue.pop(); path.add(node); if(node.getName().equalsIgnoreCase(end.getName())){ showPath(path); return; } queue.addAll(node.getChildren()); } } private Node getNode(String name){ for(Node node : nodeList){ if(node.getName().equals(name)){ return node; } } throw new RuntimeException("Такой ноды нет"); } }
Editor is loading...