Блог

Я написал этот статический метод на Python для выполнения поиска в ширину. Однако я в основном использую Java, и я хочу получить представление о том, как структуры данных преобразуются в Java, учитывая обобщения и т.д. Мой код:

 def bfs(graph, start_vertex, target_value):
  path = [start_vertex] #a list that contains start_vertex
  vertex_and_path = [start_vertex, path] #a list that contains start_vertex and path
  bfs_queue = [vertex_and_path]
  visited = set() #visited defined as an empty set

  while bfs_queue: #while the queue is not empty
    current_vertex, path = bfs_queue.pop(0) #removes element from queue and sets both equal to that first element
    visited.add(current_vertex) #adds current vertex to visited list

    for neighbor in graph[current_vertex]: #looks at all neighboring vertices
      if neighbor not in visited: #if neighbor is not in visited list
        if neighbor is target_value: #if it's the target value
          return path   [neighbor] #returns path with neighbor appended
        else:
          bfs_queue.append([neighbor, path   [neighbor]]) #recursive call with path that has neighbor appended
  

график, на котором я бы использовал это, был бы:

 myGraph = { //I'm not sure how to structure this in Java
    'lava': set(['sharks', 'piranhas']),
    'sharks': set(['lava', 'bees', 'lasers']),
    'piranhas': set(['lava', 'crocodiles']),
    'bees': set(['sharks']),
    'lasers': set(['sharks', 'crocodiles']),
    'crocodiles': set(['piranhas', 'lasers'])
  }
  

и я бы назвал это как

 public static void main(String[] args){
    System.out.println(bfs(myGraph, "crocodiles", "bees"));
}
  

Пока что вот Java, которую я имею:

     public class BreadthFirstSearch{

    ///NOT DONE YET
    public static ArrayList<String> BFS(Map<String, String[]> graph, String start, String target) {
            List<String> path = new ArrayList<>();
            path.add(start);
            List<String> vertexAndPath = new ArrayList<>();
            vertexAndPath.add(start);
            vertexAndPath.add(path.get(0));
            ArrayList<String> queue = new ArrayList<>();
            queue.add(vertexAndPath.get(0));
            queue.add(vertexAndPath.get(1));
            Set<String> visited = new HashSet<String>();
            while(!queue.isEmpty()) {
                String currentVertex = queue.remove(0);
                String curVerValue = currentVertex;
                path.add(currentVertex);
                .
                .
                .
            }
        }
}
  

Хорошая работа над переводом. Позвольте мне предложить свой код, а затем объяснение:

 import java.util.*;

class BreadthFirstSearch {
    public static ArrayList<String> BFS(
        Map<String, String[]> graph, String start, String target
    ) {
        Map<String, String> visited = new HashMap<>();
        visited.put(start, null);
        ArrayDeque<String> deque = new ArrayDeque<>();
        deque.offer(start);

        while (!deque.isEmpty()) {
            String curr = deque.poll();

            if (curr.equals(target)) {
                ArrayList<String> path = new ArrayList<>();
                path.add(curr);

                while (visited.get(curr) != null) {
                    curr = visited.get(curr);
                    path.add(curr);
                }

                Collections.reverse(path);
                return path;
            }

            for (String neighbor : graph.get(curr)) {
                if (!visited.containsKey(neighbor)) {
                    visited.put(neighbor, curr);
                    deque.offer(neighbor);
                }
            }
        }

        return null;
    }

    public static void main(String[] args) {
        Map<String, String[]> myGraph = new HashMap<>();
        myGraph.put(
            "lava", new String[] {"sharks", "piranhas"}
        );
        myGraph.put(
            "sharks", new String[] {"lava", "bees", "lasers"}
        );
        myGraph.put(
            "piranhas", new String[] {"lava", "crocodiles"}
        );
        myGraph.put(
            "bees", new String[] {"sharks"}
        );
        myGraph.put(
            "lasers", new String[] {"sharks", "crocodiles"}
        );
        myGraph.put(
            "crocodiles", new String[] {"piranhas", "lasers"}
        );
        System.out.println(BFS(myGraph, "crocodiles", "bees"));
        System.out.println(BFS(myGraph, "crocodiles", "crocodiles"));
        System.out.println(BFS(myGraph, "crocodiles", "zebras"));
    }
}
  

Вывод

 [crocodiles, lasers, sharks, bees]
[crocodiles]
null
  

Объяснение

Я принял проектное решение избегать копирования path ArrayList на каждом узле графика в пользу visited хэша, который хранит узлы в childNode => parentNode парах. Таким образом, как только я найду конечный узел, я повторяю свои шаги, чтобы создать путь за один выстрел, вместо того, чтобы строить путь для каждого узла, большинство из которых в конечном итоге никуда не ведут. Это более эффективно в пространстве и времени; Python позволяет слишком легко испортить вашу временную сложность с помощью [] [] оператора объединения списков O (n).

Использование child => parent visited HashMap также проще для программирования на Java, которая не имеет легкого веса Pair / Tuple / struct , который может удобно хранить различные типы в качестве узлов в очереди. Чтобы делать то, что вы делаете в Python, передавая список из 2 элементов в очередь, вам пришлось бы либо написать свой собственный Pair класс, использовать два ArrayDeques, либо избегать обобщений и использовать приведение, все из которых уродливы (особенно последнее, которое также небезопасно).

Еще одна проблема, которую я заметил в вашем коде, — это использование ArrayList в качестве очереди. Вставка и удаление в начале списка — это операция O (n), поскольку все элементы в списке должны быть сдвинуты вперед или назад в базовом массиве для поддержания последовательности. Оптимальной структурой очереди в Java является ArrayDeque, который предлагает добавление и удаление O (1) на обоих концах и не является потокобезопасным, в отличие от коллекции Queue.

Аналогично, в Python вы обнаружите, что производительность лучше всего достигается при использовании коллекции deque, которая предлагает быструю popleft работу для всех ваших нужд в очередях. Кроме того, в вашей реализации Python каждый ключ в вашем хэше указывает на set , что нормально, но кажется ненужной структурой, когда подойдет список (вы переключились на примитивный массив в Java). Если вы не манипулируете графиком, а только перебираете соседей, это кажется идеальным.

Обратите внимание, что этот код также предполагает, что у каждого узла есть ключ в хэше, который представляет график, как это делает ваш ввод. Если вы планируете вводить графики, где узлы могут не иметь ключей в хэше, вы захотите убедиться, что это graph.get(curr) обернуто containsKey проверкой, чтобы избежать сбоев.

Еще одно предположение, о котором стоит упомянуть: убедитесь, что ваш график не содержит null s, поскольку visited хэш полагается на null , чтобы указать, что у дочернего элемента нет родителя и является началом поиска.

Вам нужно было бы создать отдельный класс для хранения узлов графика. Эти узлы не могли быть статическими, поскольку все они имеют уникальные вершины. Оттуда все остальное очень похоже.

 public class Node {
    public String name;
    public ArrayList<Node> vertices;
    public void addEdge(Node node) {
        edges.add(node);
    }
}