Вступление

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

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

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

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

Представление графиков в коде

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

Основными двумя подходами к этой проблеме являются матрицы смежности и списки смежности .

Матрица смежности

Начнем с предположения, что у нас есть n узлов, и они имеют удобное название 0,1,...n-1 и что они содержат то же значение, имя которого они имеют. Конечно, это случается редко, но это упрощает объяснение матрицы смежности.

Ситуация, когда наши узлы / вершины являются объектами (как они, скорее всего, будут), очень сложна и требует множества методов обслуживания, которые делают матрицы смежности больше проблем, чем они стоят большую часть времени, поэтому мы предоставим только реализация «простого» корпуса.

Допустим, у нас есть следующий график:

{.ezlazyload}

В этом графе 5 узлов - (0,1,2,3,4) с ребрами {1,2}, {1,3}, {2,4}, {3,0}. По определению, когда мы смотрим на невзвешенный неориентированный граф

• позиция (i,j) в нашей матрице смежности равна 1, если ребро существует между узлами i и j , в противном случае - 0. В случае неориентированного графа матрица смежности равна симметричный.

Матрица смежности из предыдущего примера будет выглядеть так:

{.ezlazyload}

Мы могли бы также обратить процесс вспять, нарисовав график из заданной матрицы смежности.

Мы приведем пример обратного процесса, но с матрицей смежности взвешенного графа. В этом случае позиция (i,j) в нашей матрице равна весу ребра между узлами i и j если он существует, в противном случае он равен бесконечности.

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

Построим взвешенный граф из следующей матрицы смежности:

{.ezlazyload}

{.ezlazyload}

В последнем примере мы покажем, как ориентированный взвешенный граф представлен матрицей смежности:

{.ezlazyload}

{.ezlazyload}

Обратите внимание, что в ориентированных графах матрица смежности не является симметричной, например, у нас есть значение в (0,3), но не в (3,0). Также нет причин, по которым узел не может быть начальным и конечным узлами ребра, и у нас могут быть полностью несвязанные узлы.

Реализация матриц смежности

Теперь, когда мы увидели, как матрицы смежности работают на бумаге, нам нужно рассмотреть их реализацию. Если бы наши «узлы» действительно были просто целыми числами 0,1,...n-1 , реализация была бы довольно простой.

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

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

Мы также предоставим выбор между ориентированным и неориентированным графом, а также взвешенным / невзвешенным.

 public class Graph { 
 
 private int numOfNodes; 
 private boolean directed; 
 private boolean weighted; 
 private float[][] matrix; 
 
 /* 
 This will allow us to safely add weighted graphs in our class since 
 we will be able to check whether an edge exists without relying 
 on specific special values (like 0) 
 */ 
 private boolean[][] isSetMatrix; 
 
 // ... 
 } 

Тогда у нас будет простой конструктор:

 public Graph(int numOfNodes, boolean directed, boolean weighted) { 
 
 this.directed = directed; 
 this.weighted = weighted; 
 this.numOfNodes = numOfNodes; 
 
 // Simply initializes our adjacency matrix to the appropriate size 
 matrix = new float[numOfNodes][numOfNodes]; 
 isSetMatrix = new boolean[numOfNodes][numOfNodes]; 
 } 

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

 /* 
 Since matrices for directed graphs are symmetrical, we have to add 
 [destination][source] at the same time as [source][destination] 
 */ 
 public void addEdge(int source, int destination) { 
 
 int valueToAdd = 1; 
 
 if (weighted) { 
 valueToAdd = 0; 
 } 
 
 matrix[source][destination] = valueToAdd; 
 isSetMatrix[source][destination] = true; 
 
 if (!directed) { 
 matrix[destination][source] = valueToAdd; 
 isSetMatrix[destination][source] = true; 
 } 
 } 

В случае, если график не взвешен и вес предоставлен, мы просто игнорируем это и устанавливаем значение [source,destination] равным 1, указывая на то, что ребро действительно существует:

 public void addEdge(int source, int destination, float weight) { 
 
 float valueToAdd = weight; 
 
 if (!weighted) { 
 valueToAdd = 1; 
 } 
 
 matrix[source][destination] = valueToAdd; 
 isSetMatrix[source][destination] = true; 
 
 if (!directed) { 
 matrix[destination][source] = valueToAdd; 
 isSetMatrix[destination][source] = true; 
 } 
 } 

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

 public void printMatrix() { 
 for (int i = 0; i < numOfNodes; i++) { 
 for (int j = 0; j < numOfNodes; j++) { 
 // We only want to print the values of those positions that have been marked as set 
 if (isSetMatrix[i][j]) 
 System.out.format("%8s", String.valueOf(matrix[i][j])); 
 else System.out.format("%8s", "/ "); 
 } 
 System.out.println(); 
 } 
 } 

И после этого удобный метод, который распечатывает края более понятным способом:

 /* 
 We look at each row, one by one. 
 When we're at row i, every column j that has a set value represents that an edge exists from 
 i to j, so we print it 
 */ 
 public void printEdges() { 
 for (int i = 0; i < numOfNodes; i++) { 
 System.out.print("Node " + i + " is connected to: "); 
 for (int j = 0; j < numOfNodes; j++) { 
 if (isSetMatrix[i][j]) { 
 System.out.print(j + " "); 
 } 
 } 
 System.out.println(); 
 } 
 } 

Наконец, давайте напишем два вспомогательных метода, которые мы будем использовать позже:

 public boolean hasEdge(int source, int destination) { 
 return isSetMatrix[source][destination]; 
 } 
 
 public Float getEdgeValue(int source, int destination) { 
 if (!weighted || !isSetMatrix[source][destination]) 
 return null; 
 return matrix[source][destination]; 
 } 

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

 public class GraphShow { 
 public static void main(String[] args) { 
 
 // Graph(numOfNodes, directed, weighted) 
 Graph graph = new Graph(5, false, true); 
 
 graph.addEdge(0, 2, 19); 
 graph.addEdge(0, 3, -2); 
 graph.addEdge(1, 2, 3); 
 graph.addEdge(1, 3); // The default weight is 0 if weighted == true 
 graph.addEdge(1, 4); 
 graph.addEdge(2, 3); 
 graph.addEdge(3, 4); 
 
 graph.printMatrix(); 
 
 System.out.println(); 
 System.out.println(); 
 
 graph.printEdges(); 
 
 System.out.println(); 
 System.out.println("Does an edge from 1 to 0 exist?"); 
 if (graph.hasEdge(0,1)) { 
 System.out.println("Yes"); 
 } 
 else System.out.println("No"); 
 } 
 } 

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

 / / 19.0 -2.0 / 
 / / 3.0 0.0 0.0 
 19.0 3.0 / 0.0 / 
 -2.0 0.0 0.0 / 0.0 
 / 0.0 / 0.0 / 
 
 
 Node 0 is connected to: 2 3 
 Node 1 is connected to: 2 3 4 
 Node 2 is connected to: 0 1 3 
 Node 3 is connected to: 0 1 2 4 
 Node 4 is connected to: 1 3 
 
 Does an edge from 1 to 0 exist? 
 No 
 null 

Если бы мы построили граф на основе этой матрицы, он бы выглядел так:

{.ezlazyload}

Списки смежности

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

Как следует из названия, мы используем списки для представления всех узлов, к которым у нашего узла есть граница. Чаще всего это реализуется с помощью HashMap s и LinkedList s.

{.ezlazyload}

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

В этом примере мы видим, что:

 Node 0 is connected with node 3 
 Node 1 is connected with nodes 3, 2 
 Node 2 is connected with nodes 1, 4 
 Node 3 is connected with nodes 1, 0 
 Node 4 is connected with node 2 

Очевидно, что для узла 0 мы создадим LinkedList , содержащий узел 3. Для узла 1 мы создадим LinkedList содержащий узлы 3 и 2, и так далее.

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

{.ezlazyload}

 0: [1,-50] -> [3,3] 
 1: [0,-50] 
 2: [3, 10] 
 3: [0,3] -> [2,10] -> 4,7 
 4: [3,7] 

{.ezlazyload}

 0: [2,10] 
 1: null 
 2: [2,5] -> [3,5] -> [4,3] 
 3: [0,-2] 
 4: [3,5] 

В списках смежности замечательно то, что работать с объектами намного проще, чем с матрицей смежности.

Мы будем реализовывать списки смежности с объектами в качестве узлов, а не с индексами. Это и рекомендуется при объяснении списков смежности, и более полезно знать, поскольку вы, вероятно, будете работать с объектами в проекте.

Реализация списков смежности

Код может показаться сложным на первый взгляд, но при внимательном рассмотрении он довольно прост. Во-первых, давайте начнем с простого класса Node

 public class Node { 
 int n; 
 String name; 
 
 Node(int n, String name){ 
 this.n = n; 
 this.name = name; 
 } 
 } 

Теперь давайте определим 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() , которые довольно просты:

 public void printEdges() { 
 for (Node node : adjacencyMap.keySet()) { 
 System.out.print("The " + node.name + " has an edge towards: "); 
 if (adjacencyMap.get(node) != null) { 
 for (Node neighbor : adjacencyMap.get(node)) { 
 System.out.print(neighbor.name + " "); 
 } 
 System.out.println(); 
 } 
 else { 
 System.out.println("none"); 
 } 
 } 
 } 
 
 public boolean hasEdge(Node source, Node destination) { 
 return adjacencyMap.containsKey(source) && adjacencyMap.get(source) != null && adjacencyMap.get(source).contains(destination); 
 } 

Чтобы продемонстрировать, как работают списки смежности, давайте создадим несколько узлов и заполним ими граф:

 public class GraphShow { 
 public static void main(String[] args) { 
 
 Graph graph = new Graph(true); 
 Node a = new Node(0, "A"); 
 Node b = new Node(1, "B"); 
 Node c = new Node(2, "C"); 
 Node d = new Node(3, "D"); 
 Node e = new Node(4, "E"); 
 
 graph.addEdge(a,b); 
 graph.addEdge(b,c); 
 graph.addEdge(b,d); 
 graph.addEdge(c,e); 
 graph.addEdge(b,a); 
 
 graph.printEdges(); 
 
 System.out.println(graph.hasEdge(a,b)); 
 System.out.println(graph.hasEdge(d,a)); 
 } 
 } 

Получаем на выходе:

 The A has an edge towards: B 
 The B has an edge towards: CDA 
 The C has an edge towards: E 
 true 
 false 

Примечание. Это, конечно, сильно зависит от того, как Java обрабатывает объекты в памяти. Мы должны убедиться , что дальнейшие изменения в нашем a узел в main , после того как мы добавили его в наш граф, отразятся на нашем графике! Иногда это то, к чему мы стремимся, но иногда это не так. В любом случае, мы должны знать, что в этом случае a в нашем графе совпадает a узлом main .

Конечно, мы могли бы реализовать это по-другому. Другой популярный подход - добавить список исходящих ребер к Node и соответствующим образом изменить класс Graph

 public class Node { 
 int n; 
 String name; 
 LinkedList<Node> adjacentNodes; 
 
 Node(int n, String name) { 
 this.n = n; 
 this.name = name; 
 adjacentNodes = new LinkedList<>(); 
 } 
 
 public void addEdge(Node node) { 
 if (!adjacentNodes.contains(node)) 
 adjacentNodes.add(node); 
 } 
 } 

Оба подхода по-своему соответствуют духу концепции объектно-ориентированной инкапсуляции, так что любой из них подходит.

Матрицы смежности и списки смежности

Матрицы смежности имеют гораздо более быстрое время поиска, чем списки смежности. Например, если мы хотим проверить, 0 ребро, ведущее к узлу 4 мы могли бы просто проверить матрицу по индексам [0,4] что дает нам постоянное время выполнения.

С другой стороны, мы потенциально должны были бы проверить весь список 0 соседей «s в списке смежности , чтобы найти , есть ли край ведущий к узлу 4 , что дает нам линейное (O (N)) просмотровое время.

Добавление ребер также намного быстрее в матрицах смежности - просто измените значение в позиции [i,j] чтобы добавить ребро от узла i к узлу j , в то время как со списками (если у нас нет доступа к указателю на последний элемент ) также может занять время O (n) , особенно если нам нужно проверить, существует ли это ребро уже в списке или нет.

Что касается места - списки смежности намного эффективнее по очень простой причине. Большинство реальных графов - это то, что мы называем разреженными , что означает, что количество ребер намного меньше, чем максимально возможное количество ребер.

Почему это важно? Что ж, в матрице смежности у нас всегда есть матрица размером n x n (где n - количество узлов), независимо от того, есть ли у нас только несколько ребер или почти максимальное количество (где каждый узел соединен друг с другом).

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

Говоря более конкретно, если бы у нас был граф с N узлами и E ребрами, пространственная сложность этих двух подходов была бы:

{.ezlazyload}

Что мне выбрать для реализации?

Краткий ответ - списки смежности. Они более прямолинейны при работе с объектами, и большую часть времени нас не волнует немного лучшее время поиска, которое обеспечивают матрицы смежности по сравнению с обслуживанием и удобочитаемостью кода.

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

Так, например, если вы, скорее всего, собираетесь использовать следующую операцию:

• Проверка того, является ли ребро частью графа: матрица смежности , поскольку проверка того, является ли ребро частью графа, занимает время O (1) , а в списках смежности - время O (lengthOfList)
• Добавление или удаление ребер из графа: матрица смежности , такая же разница, как и в предыдущем случае
• Обход графа: список смежности занимает время O (N + E) вместо O (N ^ 2)

Заключение

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

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

Основными двумя подходами к представлению графов в коде являются матрицы смежности и списки смежности .