Как этот поиск в ширину будет преобразован в статический метод в Java? - PullRequest
Новая
       29

Как этот поиск в ширину будет преобразован в статический метод в Java?

1 голос
/ 29 марта 2019

Я написал этот статический метод на 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);
                .
                .
                .
            }
        }
}

Ответы [ 2 ]

2 голосов
/ 29 марта 2019

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

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 с, поскольку хеш visited использует null, чтобы указать, что у ребенка нет родителя и он является началом поиска.

0 голосов
/ 29 марта 2019

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

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