What they ask in an interview: an overview of algorithms, part 2

This article is a continuation of my short review of algorithms. Here is a link to the first part . Previously, we considered 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 versatile structures in programming. A graph G is usually defined using a pair of sets G = (V, R) , where:

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

Ordinary connecting lines are called edges : Lines with arrows - arcs : As a rule, a graph is represented using a diagram in which some vertices are connected by edges (arcs). Graphs connected by arcs that directly indicate 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 movements along them are 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.: Edges (arcs) can also be assigned weights, numbers representing the physical distance between two vertices (or the relative transition time between two vertices). Such graphs are called weighted :

3. Algorithms for finding a path (depth, width)

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

Depth walk

This is one of the most common graph traversal methods. This depth -first search strategy is to go "deeper" in the graph as far as possible, and when reaching a dead end, return to the nearest vertex that has adjacent vertices that have not been visited before. This algorithm stores on the stack information about where to return when a dead end is reached. Depth traversal rules:

1. Visit an adjacent, previously unvisited vertex, mark it, and push it onto the stack.
2. Go to this peak.
3. Repeat step 1.
4. If the execution of step 1 is impossible, 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 bypassing.
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 look at the correctness of the work:

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 we use a nested loop in the pass method, the time complexity will be O(N²) .

Bypass in width

This algorithm, like depth-first traversal, is one of the simplest and most basic graph traversal methods. Its essence is that we have some current vertex, with which we enqueue all adjacent, not passed vertices, 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 select the following rules:

1. Visit the next, previously unvisited vertex adjacent to the current vertex, mark it in advance and put it in the queue.
2. If rule #1 fails, extract the vertex from the queue and make it the current vertex.
3. If rule #1 and #2 are impossible, the traversal is completed and all vertices are passed (if the 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 in the DFS 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 nested 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 cities are vertices, the paths between them are roads, roads can have one-way traffic - the direction of the graph. Let's say you're a trucking company and you need to find the shortest route between two distant cities. How will you do it? One of the most common problems associated with 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 are the steps in this algorithm? I will try to answer this question. Steps of Dijkstra's algorithm:

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

We will repeat the cycle of these stages until all the vertices 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 weight 3, to C with weight 5, and to D with weight 7. According to the first step of the algorithm, we select the node with the lowest transition cost - that is, to B .
2. Since the only non-traversed neighbor of B is 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 has already been completed, we proceed to the selection of the next vertex with the minimum weight of the edge to it.

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

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

4. Further, 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 old one, so we leave it unchanged too.
5. From the nearest available vertices, E and D , we select the vertex with the lowest edge weight, i.e. 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 smallest edge weight 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 it's the shortest, we have to run our steps for vertex E as well .

9. Since the vertex G has no neighboring vertices to which the directed path would lead, we have only the vertex E : 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 path AG(14), so we leave this path unchanged.

    Since there are no vertices leading from G , it makes no sense to run stages for this 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 take a 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 search and breadth-first search. To display the 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 passed 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 takes place. 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 less than O(N²) since we have loops nested within a loop. Well, that's all for today, thank you for your attention!