What they ask at an interview: review of algorithms, part 2

This article is a continuation of my short review on algorithms. Here is the link to the first part . Previously, we looked at various array sorting algorithms and the so-called greedy algorithm . Today we will talk about graphs and algorithms related to them. A graph is one of the most flexible and universal structures in programming. A graph G is usually specified using a pair of sets G = (V, R) , where:

• V - set of vertices;
• R is the set of lines connecting pairs of vertices.

Common connecting lines are called edges : Lines with arrows - arcs : Typically, a graph is represented using a diagram in which some vertices are connected by edges (arcs). Graphs connected to each other by arcs directly indicating the direction are called directed . If the graphs are connected by edges, that is, without indicating the direction of possible movement, they become undirected . This means that movement along them is possible in both directions: both from vertex A to B, and from B to A. A connected graph is a graph in which at least one path leads from each vertex to any other vertex (as in the example above ). If this is not the case, the graph becomes disconnected : Also, edges (arcs) can be assigned weights - numbers representing the physical distance between two vertices (or the relative time of transition between two vertices). Such graphs are called weighted :

3. Path search algorithms (depth, width)

One of the basic operations that is performed on graphs is to determine all the vertices that are reachable from a given vertex. Imagine that you are trying to determine how to get from one city to another with possible transfers. Some cities can be reached directly, while others require a detour through other cities. There are many other situations in which it may be necessary to find all the vertices to which a path can be found from a given vertex. So, there are two main ways to traverse graphs: depth-first traversal and breadth-first traversal , which we will consider. Both methods will ensure iterates over all connected vertices. For further consideration of depth-first and breadth-first algorithms , take the following graph:

Depth First Traversal

This is one of the most common graph traversal methods. This depth -first search strategy consists of going “deep” into the graph as far as possible, and upon reaching a dead end, returning to the nearest vertex that has adjacent vertices that have not been visited before. This algorithm stores information on the stack about where to return when a deadlock is reached. Rules for depth first traversal:

1. Visit an adjacent, previously unvisited vertex, mark it and put it on the stack.
2. Go to this peak.
3. Repeat step 1.
4. If it is impossible to complete step 1, return to the previous vertex and try to repeat rule 1. If this is impossible, return to the vertex before it, and so on, until we find a vertex from which we can continue the traversal.
5. Continue until all vertices are on the stack.

Let's take a look at what the code for this algorithm might look like in Java:

public class Graph {
  private final int MAX_VERTS = 10;
  private Vertex vertexArray[]; //массив вершин
  private int adjMat[][]; // матрица смежности
  private int nVerts; // текущее количество вершин
  private Stack<integer> stack;

  public Graph() { // инициализация внутрених полей
     vertexArray = new Vertex[MAX_VERTS];
     adjMat = new int[MAX_VERTS][MAX_VERTS];
     nVerts = 0;
     for (int j = 0; j < MAX_VERTS; j++) {
        for (int k = 0; k < MAX_VERTS; k++) {
           adjMat[j][k] = 0;
        }
     }
     stack = new Stack<>();
  }

  public void addVertex(char lab) {
     vertexArray[nVerts++] = new Vertex(lab);
  }

  public void addEdge(int start, int end) {
     adjMat[start][end] = 1;
     adjMat[end][start] = 1;
  }

  public void displayVertex(int v) {
     System.out.println(vertexArray[v].getLabel());
  }

  public void dfs() { // обход в глубину
     vertexArray[0].setWasVisited(true); // берётся первая вершина
     displayVertex(0);
     stack.push(0);

     while (!stack.empty()) {
        int v = getAdjUnvisitedVertex(stack.peek()); // вынуть индекс смежной веришины, еckи есть 1, нету -1
        if (v == -1) { // если непройденных смежных вершин нету
           stack.pop(); // элемент извлекается из стека
        }
        else {
           vertexArray[v].setWasVisited(true);
           displayVertex(v);
           stack.push(v); // элемент попадает на вершину стека
        }
     }

     for (int j = 0; j < nVerts; j++) {  // сброс флагов
        vertexArray[j].wasVisited = false;
     }

  }

  private int getAdjUnvisitedVertex(int v) {
     for (int j = 0; j < nVerts; j++) {
        if (adjMat[v][j] == 1 && vertexArray[j].wasVisited == false) {
           return j; //возвращает первую найденную вершину
        }
     }
     return -1;
  }
}
</integer>

The top looks like:

public class Vertex {
  private char label;  // метка А например
  public boolean wasVisited;

  public Vertex(final char label) {
     this.label = label;
     wasVisited = false;
  }

  public char getLabel() {
     return this.label;
  }

  public boolean isWasVisited() {
     return this.wasVisited;
  }

  public void setWasVisited(final boolean wasVisited) {
     this.wasVisited = wasVisited;
  }
}

Let's run this algorithm with specific vertices and see if it works correctly:

public class Solution {
  public static void main(String[] args) {
     Graph graph = new Graph();
     graph.addVertex('A'); //0
     graph.addVertex('B'); //1
     graph.addVertex('C'); //2
     graph.addVertex('D'); //3
     graph.addVertex('E'); //4
     graph.addVertex('F'); //5
     graph.addVertex('G'); //6

     graph.addEdge(0,1);
     graph.addEdge(0,2);
     graph.addEdge(0,3);
     graph.addEdge(1,4);
     graph.addEdge(3,5);
     graph.addEdge(5,6);

     System.out.println("Visits: ");
     graph.dfs();
  }
}

Console output: Since we have an adjacency matrix and in the walk method we use a loop nested within a loop, the time complexity will be O(N²) .

Walk in width

This algorithm, like depth-first traversal, is one of the simplest and most basic methods for traversing a graph. Its essence is that we have a certain current vertex, from which we put all adjacent, untraversed vertices into a queue and select the next element (which is stored first in the queue) to make it current... If we break this algorithm into stages, we can highlight the following rules:

1. Visit the next, previously unvisited vertex adjacent to the current vertex, mark it in advance and add it to the queue.
2. If rule #1 cannot be fulfilled, remove the vertex from the queue and make it the current vertex.
3. If rules #1 and #2 are impossible, the traversal is completed and all vertices have been traversed (if our graph is connected).

The graph class is almost identical to the similar class from the depth-first search algorithm, except for the method that processes the algorithm and replaces the internal stack with a queue:

public class Graph {
  private final int MAX_VERTS = 10;
  private Vertex vertexList[]; //массив вершин
  private int adjMat[][]; // матрица смежности
  private int nVerts; // текущее количество вершин
  private Queue<integer> queue;

  public Graph() {
     vertexList = new Vertex[MAX_VERTS];
     adjMat = new int[MAX_VERTS][MAX_VERTS];
     nVerts = 0;
     for (int j = 0; j < MAX_VERTS; j++) {
        for (int k = 0; k < MAX_VERTS; k++) {  // заполнение матрицы смежности нулями
           adjMat[j][k] = 0;
        }
     }
     queue = new PriorityQueue<>();
  }

  public void addVertex(char lab) {
     vertexList[nVerts++] = new Vertex(lab);
  }

  public void addEdge(int start, int end) {
     adjMat[start][end] = 1;
     adjMat[end][start] = 1;
  }

  public void displayVertex(int v) {
     System.out.println(vertexList[v].getLabel());
  }

  public void bfc() { // обход в глубину
     vertexList[0].setWasVisited(true);
     displayVertex(0);
     queue.add(0);
     int v2;

     while (!queue.isEmpty()) {
        int v = queue.remove();

        while((v2 = getAdjUnvisitedVertex(v))!=-1) {// цикл будет работать, пока все смежные вершины не будут найденны, и не будут добавлены в очередь
           vertexList[v2].wasVisited =true;
           displayVertex(v2);
           queue.add(v2);
        }
     }

     for (int j = 0; j < nVerts; j++) {  // сброс флагов
        vertexList[j].wasVisited = false;
     }

  }

  private int getAdjUnvisitedVertex(int v) {
     for (int j = 0; j < nVerts; j++) {
        if (adjMat[v][j] == 1 && vertexList[j].wasVisited == false) {
           return j; //возвращает первую найденную вершину
        }
     }
     return -1;
  }
}
</integer>

The Vertex class is identical to the class from the depth-first search algorithm . Let's put this algorithm into action:

public class Solution {
  public static void main(String[] args) {
     Graph graph = new Graph();
     graph.addVertex('A'); //0
     graph.addVertex('B'); //1
     graph.addVertex('C'); //2
     graph.addVertex('D'); //3
     graph.addVertex('E'); //4
     graph.addVertex('F'); //5
     graph.addVertex('G'); //6

     graph.addEdge(0,1);
     graph.addEdge(0,2);
     graph.addEdge(0,3);
     graph.addEdge(1,4);
     graph.addEdge(3,5);
     graph.addEdge(5,6);

     System.out.println("Visits: ");
     graph.bfc();
  }
}

Console output: Again: we have an adjacency matrix and use a loop nested within a loop, so O(N²) is the time complexity of the above algorithm.

4. Dijkstra's algorithm

As mentioned earlier, graphs can be directed or undirected . And as you remember, they can still be weighted . Weighted, directed graphs are often found in real life: for example, a map of cities, where the cities are vertices, the paths between them are roads, roads can have one-way traffic - the direction of the graph. Let's say you are engaged in cargo transportation and you need to create the shortest route between two distant cities. How will you do this? One of the most common problems involving weighted graphs is the problem of choosing the shortest path between two vertices. To solve this problem we use Dijkstra's algorithm . I would like to immediately note that by executing Dijkstra’s algorithm we will find out the shortest paths to all vertices from a given initial one. What stages does this algorithm have? I'll try to answer this question. Stages of Dijkstra's algorithm:

• Stage 1 : search for the node, the transition to which will be the least cost. You are standing at the very beginning and wondering where to go: to node A or to node B. How long will it take to get to each of these nodes?
• Stage 2 : calculating how much time it takes to get to all neighbors of B that have not yet been affected by the algorithm when moving along an edge from B. If this new time turns out to be less than the old one, the path through edge B will become the new shortest path for this vertex.
• Stage 3 : mark vertex B as passed.
• Step 4 : Go to Step 1.

We will repeat the cycle of these stages until all the peaks have been passed. Let's consider the following weighted directed graph: So, using the above algorithm, we will determine the shortest path from A to G:

1. For vertex A there are three possible paths: to B with a weight of 3, to C with a weight of 5 and to D with a weight of 7. According to the first point of the algorithm, we select the node with the lowest transition cost - that is, to B.
2. Since the only untraversed neighboring vertex for B is vertex E , we check what the path will be when passing through this vertex. 3( AB ) + 6( BE ) = 9.

   Thus, we note that the current shortest path to AE = 9.

3. Since our work with vertex B is already completed, we move on to selecting the next vertex with the minimum weight of the edge before it.

   From vertices A and B these can be vertices D (7), C (5), E (6).

   C has the smallest edge weight , so we move on to this vertex.

4. Next, as before, we find out the shortest path to neighboring vertices when passing through C:
   • AD = 5( AC ) + 3( CD ) = 8, but since the previous shortest path AC = 7, that is, less than this one through C , we leave the shortest path AD = 7 unchanged.
   • CE = 5( AC ) + 4( CE ) = 9, this new shortest path is equal to the previous one so we leave it unchanged too.
5. From the nearest available vertices, E and D , we select the vertex with the smallest edge weight, that is, D (3).
6. We find out the shortest path to its neighbor - F.

   AF = 7( AD ) + 3( DF ) = 10

7. From the nearest available vertices E and F , we select the vertex with the least weight of the edge to it, that is, F (3).
8. We find out the shortest path to its neighbor - G.

   AG = 7( AD ) + 3( DF ) + 4( FG ) = 14

   Actually, here we have found the path from A to G.

   But to make sure that it is the shortest, we must run our steps for vertex E as well .

9. Since vertex G does not have neighboring vertices to which a directed path would lead, we only have vertex E left : we select it.
10. We find out the shortest path to the neighbor - G.

    AG = 3( AB ) + 6( BE ) + 6( EG ) = 15, this path is longer than the previous shortest AG(14), so we leave this path unchanged.

    Since there are no vertices leading from G , it makes no sense to run stages for a given vertex. Therefore, the work of the algorithm can be considered complete.

As I said earlier, in addition to finding the shortest path for AG , we got the shortest paths to all vertices from vertex A (AB, AC, AD, AE, AF) . Well, it's time to look at how this can be implemented in Java. First, let's look at the vertex class:

public class Vertex {
   private char label;
   private boolean isInTree;

   public Vertex(char label) {
       this.label = label;
       this.isInTree = false;
   }

   public char getLabel() {
       return label;
   }

   public void setLabel(char label) {
       this.label = label;
   }

   public boolean isInTree() {
       return isInTree;
   }

   public void setInTree(boolean inTree) {
       isInTree = inTree;
   }
}

The vertex class is actually identical to the vertex class from depth-first and breadth-first search. To display shortest paths, we need a new class that will contain the data we need:

public class Path { // an object данного класса содержащий расстояние и предыдущие и пройденные вершины
   private int distance; // текущая дистанция от начальной вершины
   private List<integer> parentVertices; // текущий родитель вершины

   public Path(int distance) {
       this.distance = distance;
       this.parentVertices = new ArrayList<>();
   }

   public int getDistance() {
       return distance;
   }

   public void setDistance(int distance) {
       this.distance = distance;
   }

   public List<integer> getParentVertices() {
       return parentVertices;
   }

   public void setParentVertices(List<integer> parentVertices) {
       this.parentVertices = parentVertices;
   }
}
</integer></integer></integer>

In this class we can see the total distance of the path and the vertices that will be covered when passing along the shortest path. And now I would like to consider the class in which, in fact, the shortest traversal of the graph occurs. So, the graph class:

public class Graph {
   private final int MAX_VERTS = 10;// максимальное количество вершин
   private final int INFINITY = 100000000; // это число у нас будет служить в качестве "бесконечности"
   private Vertex vertexList[]; // список вершин
   private int relationMatrix[][]; // матрица связей вершин
   private int countOfVertices; // текущее количество вершин
   private int countOfVertexInTree; // количество рассмотренных вершин в дереве
   private List<path> shortestPaths; // список данных кратчайших путей
   private int currentVertex; // текущая вершина
   private int startToCurrent; //расстояние до currentVertex

   public Graph() {
       vertexList = new Vertex[MAX_VERTS]; // матрица смежности
       relationMatrix = new int[MAX_VERTS][MAX_VERTS];
       countOfVertices = 0;
       countOfVertexInTree = 0;
       for (int i = 0; i < MAX_VERTS; i++) {// матрица смежности заполняется
           for (int k = 0; k < MAX_VERTS; k++) { // бесконечными расстояниями
               relationMatrix[i][k] = INFINITY; // задания значений по умолчанию
               shortestPaths = new ArrayList<>();// задается пустым
           }
       }
   }

   public void addVertex(char lab) {// задание новых вершин
       vertexList[countOfVertices++] = new Vertex(lab);
   }

   public void addEdge(int start, int end, int weight) {
       relationMatrix[start][end] = weight; // задание ребер между вершинами, с весом между ними
   }

   public void path() { // выбор кратчайшего пути
       //  задание данных для стартовой вершины
       int startTree = 0; // стартуем с вершины 0
       vertexList[startTree].setInTree(true); // включение в состав дерева первого element
       countOfVertexInTree = 1;

       // заполнение коротких путей для вершин смежных с стартовой
       for (int i = 0; i < countOfVertices; i++) {
           int tempDist = relationMatrix[startTree][i];
           Path path = new Path(tempDist);
           path.getParentVertices().add(0);// первым родительским элементом, будет всегда стартовая вершина
           shortestPaths.add(path);
       }
       // пока все вершины не окажутся в дереве
       while (countOfVertexInTree < countOfVertices) { // выполняем, пока количество вершин в дереве не сравняется с общим количеством вершин
           int indexMin = getMin();//получаем индекс вершины с наименшей дистанцией, из вершин еще не входящих в дерево
           int minDist = shortestPaths.get(indexMin).getDistance();// минимальная дистанция вершины, из тек которые ещё не в дереве

           if (minDist == INFINITY) {
               System.out.println("В графе пристувствуют недостижимые вершины");
               break;// в случае если остались непройденными только недостижимые вершины, мы выходим из цикла
           } else {
               currentVertex = indexMin; // переводим указатель currentVert к текущей вершине
               startToCurrent = shortestPaths.get(indexMin).getDistance();// задаем дистанцию к текущей вершине
           }

           vertexList[currentVertex].setInTree(true);  //включение текущей вершины в дерево
           countOfVertexInTree++; // увеличиваем счетчик вершин в дереве
           updateShortestPaths(); // обновление списка кратчайших путей
       }

       displayPaths(); // выводим в консоль результаты
   }

   public void clean() { // очиска дерева
       countOfVertexInTree = 0;
       for (int i = 0; i < countOfVertices; i++) {
           vertexList[i].setInTree(false);
       }
   }

   private int getMin() {
       int minDist = INFINITY; // за точку старта взята "бесконечная" длина
       int indexMin = 0;
       for (int i = 1; i < countOfVertices; i++) {// для каждой вершины
           if (!vertexList[i].isInTree() && shortestPaths.get(i).getDistance() < minDist) { // если вершина ещё не ве дереве и её растояние меньше старого минимума
               minDist = shortestPaths.get(i).getDistance(); // задаётся новый минимум
               indexMin = i; // обновление индекса вершины содержащую минимаьную дистанцию
           }
       }
       return indexMin; //возвращает индекс вершины с наименшей дистанцией, из вершин еще не входящих в дерево
   }

   private void updateShortestPaths() {
       int vertexIndex = 1; // стартовая вершина пропускается
       while (vertexIndex < countOfVertices) { // перебор столбцов

           if (vertexList[vertexIndex].isInTree()) { // если вершина column уже включена в дерево, она пропускается
               vertexIndex++;
               continue;
           }
           // вычисление расстояния для одного element sPath
           // получение ребра от currentVert к column
           int currentToFringe = relationMatrix[currentVertex][vertexIndex];
           // суммирование всех расстояний
           int startToFringe = startToCurrent + currentToFringe;
           // определение расстояния текущего element vertexIndex
           int shortPathDistance = shortestPaths.get(vertexIndex).getDistance();

           // сравнение расстояния через currentVertex с текущим расстоянием в вершине с индексом vertexIndex
           if (startToFringe < shortPathDistance) {// если меньше, то у вершины под индексом vertexIndex будет задан новый кратчайший путь
               List<integer> newParents = new ArrayList<>(shortestPaths.get(currentVertex).getParentVertices());//создаём копию списка родителей вершины currentVert
               newParents.add(currentVertex);// задаём в него и currentVertex How предыдущий
               shortestPaths.get(vertexIndex).setParentVertices(newParents); // соохраняем новый маршут
               shortestPaths.get(vertexIndex).setDistance(startToFringe); // соохраняем новую дистанцию
           }
           vertexIndex++;
       }
   }

   private void displayPaths() { // метод для вывода кратчайших путей на экран
       for (int i = 0; i < countOfVertices; i++) {
           System.out.print(vertexList[i].getLabel() + " = ");
           if (shortestPaths.get(i).getDistance() == INFINITY) {
               System.out.println("0");
           } else {
               String result = shortestPaths.get(i).getDistance() + " (";
               List<integer> parents = shortestPaths.get(i).getParentVertices();
               for (int j = 0; j < parents.size(); j++) {
                   result += vertexList[parents.get(j)].getLabel() + " -> ";
               }
               System.out.println(result + vertexList[i].getLabel() + ")");
           }
       }
   }
}
</integer></integer></path>

Actually, that’s all the magic =) Well, now, let’s take a look at this algorithm in action:

public class Solution {

   public static void main(String[] args) {
       Graph graph = new Graph();
       graph.addVertex('A');
       graph.addVertex('B');
       graph.addVertex('C');
       graph.addVertex('D');
       graph.addVertex('E');
       graph.addVertex('F');
       graph.addVertex('G');

       graph.addEdge(0, 1, 3);
       graph.addEdge(0, 2, 5);
       graph.addEdge(0, 3, 7);
       graph.addEdge(1, 4, 6);
       graph.addEdge(2, 4, 4);
       graph.addEdge(2, 3, 3);
       graph.addEdge(3, 5, 3);
       graph.addEdge(4, 6, 6);
       graph.addEdge(5, 6, 4);

       System.out.println("Элементы имеют кратчайшие пути из точки A: ");
       graph.path();
       graph.clean();
   }
}

And the output in the console: The time complexity of this algorithm is nothing more than O(N²) since we have loops nested within a loop. Well, that's all for me today, thanks for your attention!