Рубрики
Без рубрики

Графики в Java: Поиск по глубине (DFS)

Автор оригинала: Olivera Popović.

Вступление

Графики-это удобный способ хранения определенных типов данных. Концепция была перенесена из математики и приспособлена для нужд информатики.

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

  • Графики на Java
    • Представление графиков в коде
    • Поиск по глубине (DFS)
    • Поиск по ширине (BFS)
    • Алгоритм Дейкстры

Поиск по глубине

Поиск по глубине (DFS) выполняет поиск как можно дальше вдоль ветви, а затем возвращается к поиску как можно дальше в следующей ветви. Это означает, что на следующем графике он начинается с первого соседа и продолжается вниз по линии, насколько это возможно:

Как только он достигает последнего узла в этой ветви (1), он возвращается к первому узлу, где он столкнулся с возможностью изменить курс (5), и посещает всю эту ветвь, которая в нашем случае является узлом (2).

Затем он снова возвращается к узлу (5), и поскольку он уже посетил узлы (1) и (2), он возвращается к (3) и перенаправляется в следующую ветвь (8).

Реализация

Поскольку мы знаем, как представлять графики в коде с помощью списков смежности и матриц, давайте составим график и пройдемся по нему с помощью DFS. Графики, с которыми мы будем работать, достаточно просты, поэтому не имеет значения, какую реализацию мы выберем.

Хотя для реальных проектов в большинстве случаев списки смежности будут лучшим выбором, поэтому мы представим график в виде списка смежности.

Мы хотим посетить все наши узлы один раз, как показано на анимации выше, они становятся красными после посещения, поэтому мы их больше не посещаем. Чтобы сделать это в коде, мы введем флаг посещено :

public class Node {
    int n;
    String name;
    boolean visited; // New attribute

    Node(int n, String name) {
        this.n = n;
        this.name = name;
        visited = false;
    }

    // Two new methods we'll need in our traversal algorithms
    void visit() {
        visited = true;
    }

    void unvisit() {
        visited = false;
    }
}

Теперь давайте определим График :

public class Graph {

    // Each node maps to a list of all his neighbors
    private HashMap> adjacencyMap;
    private boolean directed;

    public Graph(boolean directed) {
        this.directed = directed;
        adjacencyMap = new HashMap<>();
    }

    // ...
}

Теперь давайте добавим метод added() . Мы будем использовать два метода: вспомогательный метод и фактический метод.

В вспомогательном методе мы также проверим наличие возможных повторяющихся ребер. Прежде чем добавлять границу между A и B , мы сначала удалим ее и только затем добавим. Если ребро уже существовало, это не позволяет нам добавить дубликат ребра. Если там еще не было ребра, то у нас все еще есть только одно ребро между двумя узлами.

Если ребро не существовало, удаление несуществующего ребра приведет к исключению NullPointerException поэтому мы вводим временную копию списка:

public void addEdgeHelper(Node a, Node b) {
    LinkedList tmp = adjacencyMap.get(a);

    if (tmp != null) {
        tmp.remove(b);
    }
    else tmp = new LinkedList<>();
    tmp.add(b);
    adjacencyMap.put(a, tmp);
}

public void addEdge(Node source, Node destination) {

    // We make sure that every used node shows up in our .keySet()
    if (!adjacencyMap.keySet().contains(source))
        adjacencyMap.put(source, null);

    if (!adjacencyMap.keySet().contains(destination))
        adjacencyMap.put(destination, null);

    addEdgeHelper(source, destination);

    // If a graph is undirected, we want to add an edge from destination to source as well
    if (!directed) {
        addEdgeHelper(destination, source);
    }
}

Наконец, у нас будут края печати() , есть края() и посещенные узлы сброса() вспомогательные методы, которые довольно просты:

public void printEdges() {
    for (Node node : adjacencyMap.keySet()) {
        System.out.print("The " + node.name + " has an edge towards: ");
        for (Node neighbor : adjacencyMap.get(node)) {
            System.out.print(neighbor.name + " ");
        }
        System.out.println();
    }
}

public boolean hasEdge(Node source, Node destination) {
    return adjacencyMap.containsKey(source) && adjacencyMap.get(source).contains(destination);
}

public void resetNodesVisited(){
    for(Node node : adjacencyMap.keySet()){
        node.unvisit();
    }
}

Мы также добавим метод первого поиска по глубине(узел узла) в наш График класс, который выполняет следующее:

  • Если узел.посетил , просто верните
  • Если он еще не был посещен, выполните следующие действия:
    • Найдите первого незваного соседа новый узел из узла и вызовите первый поиск по глубине(новый узел)
    • Повторите процесс для всех незваных соседей

Давайте проиллюстрируем это примером:

Node A is connected with node D
Node B is connected with nodes D, C
Node C is connected with nodes A, B
Node D is connected with nodes B
  1. Все узлы в начале не посещены ( узел.посещен )
  2. Вызовите .первый поиск по глубине() с произвольным узлом в качестве начального узла, скажем первый поиск по глубине(B)
  3. отметьте B как посещенный
  4. Есть ли у Б какие-нибудь незваные соседи? Да -> первым не посещенным узлом является D, поэтому вызовите первый поиск по глубине(D)
  5. марк Дас посетил
  6. Есть ли у Д. какие-нибудь незваные соседи? Нет -> (B уже был посещен) возврат
  7. Есть ли у Б какие-нибудь незваные соседи? Да -> первым не посещенным узлом является C, поэтому вызовите первый поиск по глубине(C)
  8. отметьте C как посещенный
  9. Есть ли у С какие-нибудь незваные соседи? Да -> первым не посещенным узлом является A, поэтому вызовите первый поиск по глубине(A) 1. отметьте A как посещенный 2. Есть ли у A незваные соседи? Нет. -> возврат
  10. Есть ли у С какие-нибудь незваные соседи? Нет -> возврат
  11. Есть ли у Б какие-нибудь незваные соседи? Нет -> возврат

Вызов DFS на нашем графике дал бы нам обход B,D,C,A (порядок посещения). Когда алгоритм написан таким образом, его легко перевести в код:

Git Essentials

Ознакомьтесь с этим практическим руководством по изучению Git, содержащим лучшие практики и принятые в отрасли стандарты. Прекратите гуглить команды Git и на самом деле изучите это!

public void depthFirstSearch(Node node) {
    node.visit();
    System.out.print(node.name + " ");

    LinkedList allNeighbors = adjacencyMap.get(node);
    if (allNeighbors == null)
        return;

    for (Node neighbor : allNeighbors) {
        if (!neighbor.isVisited())
            depthFirstSearch(neighbor);
    }
}

Опять же, вот как это выглядит при переводе в анимацию:

DFS иногда называют “агрессивным” обходом графа, потому что он проходит как можно дальше через одну “ветвь”. Как мы можем видеть на приведенном выше gif, когда DFS сталкивается с узлом 25, он заставляет 25 – 12 – 6 – 4 ветвь, пока она не сможет идти дальше. Только после этого алгоритм возвращается, чтобы проверить наличие других незваных соседей предыдущих узлов, начиная с тех, которые были посещены совсем недавно.

Примечание: У нас может быть несвязанный график. Несвязанный граф-это граф, у которого нет пути между любыми двумя узлами.

В этом примере будут посещены узлы 0, 1 и 2, и выходные данные будут показывать эти узлы и полностью игнорировать узлы 3 и 4.

Аналогичная вещь произошла бы , если бы мы вызвали Первый поиск по глубине(4) , только на этот раз 4 и 3 были бы посещены, а 0, 1 и 2-нет. Решение этой проблемы состоит в том, чтобы продолжать вызывать DFS до тех пор, пока есть какие-либо не посещенные узлы.

Это можно сделать несколькими способами, но мы можем внести еще одну небольшую модификацию в наш класс Graph , чтобы решить эту проблему. Мы добавим новый Первый измененный поиск по глубине(узел узла) метод:

public void depthFirstSearchModified(Node node) {
    depthFirstSearch(node);

    for (Node n : adjacencyMap.keySet()) {
        if (!n.isVisited()) {
            depthFirstSearch(n);
        }
    }
}

public void depthFirstSearch(Node node) {
    node.visit();
    System.out.print(node.name + " ");

    LinkedList allNeighbors = adjacencyMap.get(node);
        if (allNeighbors == null)
            return;

    for (Node neighbor : allNeighbors) {
        if (!neighbor.isVisited())
            depthFirstSearch(neighbor);
    }
}

public class GraphShow {
    public static void main(String[] args) {

        Graph graph = new Graph(false);
        Node a = new Node(0, "0");
        Node b = new Node(1, "1");
        Node c = new Node(2, "2");
        Node d = new Node(3, "3");
        Node e = new Node(4, "4");


        graph.addEdge(a,b);
        graph.addEdge(a,c);
        graph.addEdge(c,b);
        graph.addEdge(e,d);

        System.out.println("If we were to use our previous DFS method, we would get an incomplete traversal");
        graph.depthFirstSearch(b);
        graph.resetNodesVisited(); // All nodes are marked as visited because of
                                   // the previous DFS algorithm so we need to
                                   // mark them all as not visited

        System.out.println();
        System.out.println("Using the modified method visits all nodes of the graph, even if it's unconnected");
        graph.depthFirstSearchModified(b);
    }
}

Что дает нам результат:

If we were to use our previous DFS method, we would get an incomplete traversal
1 0 2
Using the modified method visits all nodes of the graph, even if it's unconnected
1 0 2 4 3

Давайте запустим наш алгоритм еще на одном примере:

public class GraphShow {
    public static void main(String[] args) {

        Graph graph = new Graph(true);
        Node zero = new Node(0, "0");
        Node one = new Node(1, "1");
        Node two = new Node(2, "2");
        Node three = new Node(3, "3");
        Node four = new Node(4, "4");
        Node five = new Node(5, "5");
        Node six = new Node(6, "6");
        Node seven = new Node(7, "7");
        Node eight = new Node(8, "8");

        graph.addEdge(one,zero);
        graph.addEdge(three,one);
        graph.addEdge(two,seven);
        graph.addEdge(two,four);
        graph.addEdge(five,two);
        graph.addEdge(five,zero);
        graph.addEdge(six,five);
        graph.addEdge(six,three);
        graph.addEdge(six,eight);
        graph.addEdge(seven,five);
        graph.addEdge(seven,six);
        graph.addEdge(seven,eight);

        graph.depthFirstSearch(seven);
    }
}

Это дает нам результат:

7 5 2 4 0 6 3 1 8

Заказ Соседей

Еще одна “забавная” вещь, которую мы, возможно, захотим добавить, – это некоторый порядок, в котором соседи перечислены для каждого узла. Мы можем достичь этого, используя структуру данных кучи ( Очередь приоритетов в Java) вместо Связанного списка для соседей и реализуя метод compareTo() в нашем Узле классе, чтобы Java знала, как сортировать наши объекты:

public class Node implements Comparable {

    // Same code as before...

    public int compareTo(Node node) {
        return this.n - node.n;
    }
}

class Graph {
    // Replace all occurrences of LinkedList with PriorityQueue
}

public class GraphShow {
    public static void main(String[] args) {

        GraphAdjacencyList graph = new GraphAdjacencyList(true);
        Node a = new Node(0, "0");
        Node b = new Node(1, "1");
        Node c = new Node(2, "2");
        Node d = new Node(3, "3");
        Node e = new Node(4, "4");

        graph.addEdge(a,e);
        graph.addEdge(a,d);
        graph.addEdge(a,b);
        graph.addEdge(a,c);

        System.out.println("When using a PriorityQueue, it doesn't matter in which order we add neighbors, they will always be sorted");
        graph.printEdges();
        System.out.println();

        graph.depthFirstSearchModified(a);
        graph.resetNodesVisited();
    }
}

When using a PriorityQueue, it doesn't matter in which order we add neighbors, they will always be sorted
The 0 has an edge towards: 1 2 3 4

0 1 2 3 4

Если бы мы не использовали Приоритетную очередь , вывод DFS был бы 0,4,3,1,2 .

Вывод

Графики-это удобный способ хранения определенных типов данных. Концепция была перенесена из математики и приспособлена для нужд информатики.

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

Поиск по глубине (DFS)-один из немногих алгоритмов обхода графов, который выполняет поиск как можно дальше по ветви, а затем возвращается к поиску как можно дальше в следующей ветви.

Читайте ещё по теме: