Вступление

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

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

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

Поиск в ширину

Поиск в ширину (BFS) посещает "слой за слоем". Это означает, что в Graph, как показано ниже, он сначала посещает всех дочерних элементов начального узла. Эти дочерние элементы рассматриваются как «второй слой».

В отличие от поиска в глубину (DFS), BFS не проходит агрессивно через одну ветвь до тех пор, пока не достигнет конца, скорее, когда мы начинаем поиск с узла, он посещает всех непосещенных соседей этого узла, прежде чем перейти ко всем непосещенным соседям. другого узла:

{.ezlazyload}

Выполнение

Мы будем использовать графы, реализованные через список смежности, как мы использовали для DFS. Кроме того, нам нужно добавить visited вместе с visit() и univisit() в наш класс Node

 public class Node { 
 int n; 
 String name; 
 boolean visited; 
 
 Node(int n, String name) { 
 this.n = n; 
 this.name = name; 
 visited = false; 
 } 
 
 void visit() { 
 visited = true; 
 } 
 
 void unvisit() { 
 visited = false; 
 } 
 } 

Теперь давайте определим Graph :

 public class Graph { 
 
 // Each node maps to a list of all his neighbors 
 private HashMap<Node, LinkedList<Node>> adjacencyMap; 
 private boolean directed; 
 
 public Graph(boolean directed) { 
 this.directed = directed; 
 adjacencyMap = new HashMap<>(); 
 } 
 
 // ... 
 } 

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

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

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

 public void addEdgeHelper(Node a, Node b) { 
 LinkedList<Node> 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); 
 } 
 } 

Наконец, у нас будут довольно простые вспомогательные методы printEdges() , hasEdge() и resetNodesVisited()

 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(); 
 } 
 } 

Давайте рассмотрим алгоритм BFS на следующем неориентированном графе:

 Node 0 has neighbors: 1, 3, 2 
 Node 1 has neighbors: 0 
 Node 2 has neighbors: 3, 0 
 Node 3 has neighbors: 2, 0 

Мы можем выбрать любой узел для начала, поэтому давайте начнем с 1. Мы повторяем процесс добавления и удаления узлов из очереди, пока очередь не станет пустой.

Очередь - это структура данных FIFO (first-in-first-out). Он работает так же, как реальная очередь, поэтому записи обрабатываются (удаляются из очереди) одна за другой в том порядке, в котором они были добавлены.

Это очень удобная структура данных для BFS, так как мы хотим обрабатывать узлы в том порядке, в котором мы их посещаем, чтобы сначала обработать узлы «ближе» к начальному узлу.

Поскольку они добавляются в очередь до того, как любые узлы, находящиеся «дальше» от начального, будут добавлены в очередь, мы знаем, что в первую очередь будут обработаны более близкие узлы.

1. Мы начинаем с очереди, содержащей только узел 1

{.ezlazyload}

2. Удалите первый элемент из очереди, в данном случае 1, отметьте его как посещенный
3. Добавить всех непосещенных соседей 1 в очередь (только 0)

{.ezlazyload}

4. Удалите первый элемент из очереди, в данном случае 0, отметьте его как посещенный
5. Добавить всех непосещенных соседей 0 в очередь (узлы 3 и 2 , 1 уже отмечены как посещенные)

{.ezlazyload}

6. Удалите первый элемент из очереди, в данном случае 3, отметьте его как посещенный
7. Добавить всех трех непосещенных соседей в очередь (их нет)

{.ezlazyload}

8. Удалите первый элемент из очереди, в данном случае 2, отметьте его как посещенный
9. Добавить всех двух непосещенных соседей в очередь (опять же, их нет)
10. Очередь пуста, BFS закончил

Наши узлы посещаются в порядке 1-0-3-2 Должно быть очевидно, что набор шагов 2-3, 4-5, 6-7 и 8-9 одинаков и что шаг 10 является условием завершения цикла. При таком взгляде должно быть легко написать код для нашего breadthFirstSearch(Node node) .

В Java есть несколько типов реализаций Queue , но вместо этого мы будем использовать LinkedList , поскольку он предоставляет все необходимые методы.

Мы добавляем следующий метод в наш класс Graph

 void breadthFirstSearch(Node node) { 
 
 // Just so we handle receiving an uninitialized Node, otherwise an 
 // exception will be thrown when we try to add it to queue 
 if (node == null) 
 return; 
 
 // Creating the queue, and adding the first node (step 1) 
 LinkedList<Node> queue = new LinkedList<>(); 
 queue.add(node); 
 
 while (!queue.isEmpty()) { 
 Node currentFirst = queue.removeFirst(); 
 
 // In some cases we might have added a particular node more than once before 
 // actually visiting that node, so we make sure to check and skip that node if we have 
 // encountered it before 
 if (currentFirst.isVisited()) 
 continue; 
 
 // Mark the node as visited 
 currentFirst.visit(); 
 System.out.print(currentFirst.name + " "); 
 
 LinkedList<Node> allNeighbors = adjacencyMap.get(currentFirst); 
 
 // We have to check whether the list of neighbors is null before proceeding, otherwise 
 // the for-each loop will throw an exception 
 if (allNeighbors == null) 
 continue; 
 
 for (Node neighbor : allNeighbors) { 
 // We only add unvisited neighbors 
 if (!neighbor.isVisited()) { 
 queue.add(neighbor); 
 } 
 } 
 } 
 System.out.println(); 
 } 

Теперь мы создаем наш пример графа в коде и проверяем, работает ли наш метод должным образом:

 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,d); 
 graph.addEdge(a,b); 
 graph.addEdge(a,c); 
 graph.addEdge(c,d); 
 
 graph.breadthFirstSearch(b); 
 } 
 } 

Выход:

 1 0 3 2 

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

То же самое происходит с BFS, и это также может происходить, когда графы ориентированы, иногда мы не можем достичь всех узлов. Иногда это именно то поведение, которое мы ищем, но иногда мы хотим, чтобы были посещены все узлы.

Мы сделаем то же самое, что и в DFS, то есть будем продолжать вызывать BFS, пока есть какие-либо непосещенные узлы. Мы breadthFirstSearchModified(Node node) который сделает это за нас:

 void breadthFirstSearchModified(Node node) { 
 breadthFirstSearch(node); 
 
 for (Node n : adjacencyMap.keySet()) { 
 if (!n.isVisited()) { 
 breadthFirstSearch(n); 
 } 
 } 
 } 

 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,d); 
 graph.addEdge(a,b); 
 graph.addEdge(c,e); 
 
 System.out.println("Using the unmodified version of BFS we get:"); 
 graph.breadthFirstSearch(a); 
 
 graph.resetNodesVisited(); 
 System.out.println("Using the modified version of BFS we get:"); 
 graph.breadthFirstSearchModified(a); 
 } 
 } 

Выход:

 Using the unmodified version of BFS we get: 
 0 3 1 
 Using the modified version of BFS we get: 
 0 3 1 
 4 2 

Также существует так называемый «двунаправленный» поиск BFS. Это полезно, когда мы хотим найти кратчайший путь между двумя вершинами (узлами).

Это достигается одновременным (в разных потоках) запуском BFS от начального узла и узла назначения. Теоретически это позволяет найти кратчайший путь между двумя узлами в два раза быстрее, чем запуск BFS только с начального узла.

Примечание. Как и в случае с DFS, если мы хотим пройти через соседей в определенном порядке (вместо порядка, в котором были добавлены ребра), мы можем использовать PriorityQueue вместо LinkedList для списка соседей.

Код тот же , нам просто нужно реализовать Comparable и добавить compareTo() в наш класс Node

Заключение

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

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

Поиск в ширину - один из немногих алгоритмов обхода графа и посещения узлов «послойно». В отличие от поиска в глубину, BFS не проходит агрессивно через одну ветвь, пока не достигнет конца, скорее, когда мы начинаем поиск с узла, он посещает всех непосещенных соседей этого узла, прежде чем перейти ко всем непосещенным соседям другого узла .