The Q&A from job interviews: algorithms in Java, part 2

This is the second part of a brief overview of algorithms. Here's a link to the first article. Earlier we looked at various algorithms for sorting arrays as well as the so-called greedy algorithm.Today we will talk about graphs and the algorithms associated with them. A graph is one of the most flexible and versatile structures in programming. The graph G is usually defined by a pair of sets, i.e. G = (V, R), where:

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

Undirected connecting lines are called edges:Directed lines are called arcs:Typically, a graph is represented by a diagram in which some of the vertices are connected by edges (arcs). Graphs whose edges indicate a direction of traversal are called directed graphs. If a graph is connected by edges that do not indicate the direction of traversal, then we say it is an undirected graph. This means that movement is possible in both directions: both from vertex A to vertex B, and from vertex B to vertex 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, then the graph is said to be disconnected:Weights can also be assigned to the edges (arcs). The weights are numbers that represent, for example, the physical distance between two vertices (or the relative travel time between two vertices). These graphs are called weighted graphs:

3. Pathfinding algorithms (depth-first, breadth-first)

One of the basic operations performed with graphs is determining all the vertices reachable from a given vertex. Imagine that you are trying to determine how you can ride a bus from one city to another, including possible transfers. Some cities can be reached directly, while some can only be reached by passing through other cities. There are many other situations where you may need to find all the vertices you can reach from a given vertex. There are two main ways to traverse graphs: depth-first and breadth-first. We'll explore both of these. Both methods traverse all connected vertices. To further explore depth-first and breadth-first algorithms, we'll use the following graph:

Depth-first search

This is one of the most common graph traversal methods. The depth-first strategy is to go as deep as possible in a graph. Then after reaching a dead end, we return to the closest vertex that has previously unvisited adjacent vertices. This algorithm stores information on the stack about where to return when a dead-end is reached. Rules for depth-first search:

1. Visit a previously unvisited adjacent vertex, mark it as visited, and push it onto the stack.
2. Move to this vertex.
3. Repeat step 1.
4. If step 1 is impossible, return to the previous vertex and try to perform step 1. If that is not possible, then return to the vertex before that one, and so on, until we find a vertex from which we can continue the traversal.
5. Continue until all the vertices are on the stack.

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

public class Graph {
  private final int MAX_VERTS = 10;
  private Vertex vertexArray[]; // Array of vertices
  private int adjMat[][]; // Adjacency matrix
  private int nVerts; // Current number of vertices
  private Stack stack;

  public Graph() { // Initialize internal fields
     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() { // Depth-first search
     vertexArray[0].setVisited(true); // Take the first vertex
     displayVertex(0);
     stack.push(0);

     while (!stack.empty()) {
        int v = getAdjUnvisitedVertex(stack.peek()); // Return the index of the adjacent vertex: if any, 1; if not, -1
        if (v == -1) { // If there is no unvisited adjacent vertex
           stack.pop(); // The element is removed from the stack
        }
        else {
           vertexArray[v].setVisited(true);
           displayVertex(v);
           stack.push(v); // The element goes on top of the stack
        }
     }

     for (int j = 0; j < nVerts; j++) {  // Reset the flags
        vertexArray[j].visited = false;
     }

  }

  private int getAdjUnvisitedVertex(int v) {
     for (int j = 0; j < nVerts; j++) {
        if (adjMat[v][j] == 1 && vertexArray[j].visited == false) {
           return j; // Returns the first vertex found
        }
     }
     return -1;
  }
}

A vertex looks like this:

public class Vertex {
  private char label;  // for example, 'A'
  public boolean visited;

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

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

  public boolean isVisited() {
     return this.visited;
  }

  public void setVisited(final boolean visited) {
     this.visited = visited;
  }
}

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 are using a loop within a loop, the time complexity will be O(N²).

Breadth-first search

Like depth-first search, this algorithm is one of the simplest and most basic graph traversal methods. The gist is that we have some current vertex. We put all of its unvisited adjacent vertices into a queue and select the next element (which is the vertex stored at the head of the queue), which becomes the current vertex… Breaking this algorithm into stages, we can identify the following steps:

1. Visit the next previously unvisited vertex adjacent to the current vertex, mark it as visited in advance, and add it to the queue.
2. If step #1 cannot be performed, then remove the vertex from the queue and make it the current vertex.
3. If steps #1 and #2 cannot be performed, then we are done traversing — every vertex has been traversed (if we have a connected graph).

The graph class here is almost identical to the one we used for the depth-first search algorithm, except for the search method itself and the fact that a queue replaces the internal stack:

public class Graph {
  private final int MAX_VERTS = 10;
  private Vertex vertexList[]; // Array of vertices
  private int adjMat[][]; // Adjacency matrix
  private int nVerts; // Current number of vertices
  private Queue 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++) {  // Fill the adjacency matrix with zeros
           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() { // Depth-first search
     vertexList[0].setVisited(true);
     displayVertex(0);
     queue.add(0);
     int v2;

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

        while((v2 = getAdjUnvisitedVertex(v))!=-1) {// The loop runs until every adjacent vertex is found and added to the queue
           vertexList[v2].visited = true;
           displayVertex(v2);
           queue.add(v2);
        }
     }

     for (int j = 0; j < nVerts; j++) {  // Reset the flags
        vertexList[j].visited = false;
     }

  }

  private int getAdjUnvisitedVertex(int v) {
     for (int j = 0; j < nVerts; j++) {
        if (adjMat[v][j] == 1 && vertexList[j].visited == false) {
           return j; // Returns the first vertext found
        }
     }
     return -1;
  }
}

The Vertex class is identical to the one we used with 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 the time complexity of the above algorithm is O(N²).

4. Dijkstra's algorithm

As mentioned earlier, graphs can be directed or undirected. And you will recall that they can also be weighted. Weighted, directed graphs model relationships often found in real life: for example, a map of cities where cities are vertices, and the edges between them are roads with one-way traffic, flowing in the direction of the directed edge. Let's say you're a freight company and you need to find the shortest route between two distant cities. How would you do it? Finding the shortest path between two vertices is one of the most common problems solved using weighted graphs. To solve this problem, we use Dijkstra's algorithm. Once you run it you'll know the shortest paths from a given initial vertex to every other one. What are the steps of this algorithm? I will try to answer this question. Steps of Dijkstra's algorithm:

• Step 1: Find the adjacent node that has the lowest cost to navigate to (lowest edge weight). You're standing at the very beginning and thinking about where to go: to node A or node B. What is the cost of moving to each of these nodes?
• Step 2: calculate the distance to travel to all of node В's neighbors that have not yet been visited by the algorithm when traversing the edge from В. If the new distance is less than the old one, then the path through edge B becomes the new shortest path for this vertex.
• Step 3: mark vertex B as visited.
• Step 4: Go to step 1.

We'll repeat these steps in a loop until all the vertices have been visited. Let's consider the following weighted directed graph:Using the above algorithm, we'll determine the shortest path from A to G:

1. There are three possible paths for vertex A: to B with weight 3, to С with weight 5, and to D with weight 7. According to the first step of the algorithm, we select the node with the lowest cost (edge weight). In this case, B.

2. Since B's only unvisited neighbor is vertex Е, we check what the path would be if we passed through this vertex. 3(AB) + 6(BE) = 9.

   Thus, we record that the current shortest path from A to E is 9.

3. Since our work with vertex B is complete, we proceed to selecting the next vertex whose edge has the minimum weight.

   From vertices A and B, the possibilities are vertices D (7), C (5), or E (6).

   The edge to С has the smallest weight, so we go to this vertex.

4. Next, as before, we find the shortest path to neighboring vertices when passing through C:

   • AD = 5 (AC) + 3 (CD) = 8, but since the previous shortest path (AC = 7) is less than this one through С, we keep the shortest path (AC = 7) unchanged.

   • CE = 5(AC) + 4(CE) = 9. This new shortest path is equal to the previous one, so we also leave it unchanged.

5. From the nearest accessible vertices (E and D), select the vertex with the smallest edge weight, i.e. D (3).

6. We find the shortest path to its neighbor F.

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

7. From the nearest accessible vertices (E and F), select the vertex with the smallest edge weight, i.e. F (3).

8. Find the shortest path to its neighbor G.

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

   So, we've found a path from A to G.

   But to make sure it is the shortest, we must also perform our steps on vertex E.

9. Because vertex G has no neighboring vertices pointed to by directed edges, we have only vertex E left, so we choose it.

10. Find the shortest path to 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 the steps on the algorithm on this vertex. That means that the work of the algorithm is complete.

As I said earlier, in addition to finding the shortest path for AG, we also obtained the shortest paths from vertex A to every other vertex (AB, AC, AD, AE, AF). Well, now it's time to take a look at how this can be done in Java. Let's start with 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 virtually identical to the vertex class used for breadth-first search. To display the shortest paths, we need a new class that will contain the data we need:

public class Path { // A class that contains the distance and the previous and traversed vertices
   private int distance; // Current distance from the starting vertex
   private List parentVertices; // Current parent vertex

   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 getParentVertices() {
       return parentVertices;
   }

   public void setParentVertices(List parentVertices) {
       this.parentVertices = parentVertices;
   }
}

In this class, we can see the total distance of the path and the vertices that will be traversed when passing along the shortest path. And now let's look at the class where we actually traverse the shortest path through the graph. So here we have the Graph class:

public class Graph {
   private final int MAX_VERTS = 10;// Maximum number of vertices
   private final int INFINITY = 100000000; // This number represents infinity
   private Vertex vertexList[]; // List of vertices
   private int relationMatrix[][]; // Matrix of edges between vertices
   private int numberOfVertices; // Current number of vertices
   private int numberOfVerticesInTree; // Number of visited vertices in the tree
   private List shortestPaths; // List of shortest paths
   private int currentVertex; // Current vertex
   private int startToCurrent; // Distance to currentVertex

   public Graph() {
       vertexList = new Vertex[MAX_VERTS]; // Adjacency matrix
       relationMatrix = new int[MAX_VERTS][MAX_VERTS];
       numberOfVertices = 0;
       numberOfVerticesInTree = 0;
       for (int i = 0; i < MAX_VERTS; i++) { // Fill the adjacency matrix
           for (int k = 0; k < MAX_VERTS; k++) { // with "infinity"
               relationMatrix[i][k] = INFINITY; // Assign default values
               shortestPaths = new ArrayList<>(); // Assign an empty list
           }
       }
   }

   public void addVertex(char lab) {// Assign new vertices
       vertexList[numberOfVertices++] = new Vertex(lab);
   }

   public void addEdge(int start, int end, int weight) {
       relationMatrix[start][end] = weight; // Set weighted edges between vertices
   }

   public void path() { // Choose the shortest path
       // Set the initial vertex data
       int startTree = 0; // Start from vertex 0
       vertexList[startTree].setInTree(true); // Include the first element in the tree
       numberOfVerticesInTree = 1;

       // Fill out the shortest paths for vertices adjacent to the initial vertex
       for (int i = 0; i < numberOfVertices; i++) {
           int tempDist = relationMatrix[startTree][i];
           Path path = new Path(tempDist);
           path.getParentVertices().add(0);// The starting vertex will always be a parent vertex
           shortestPaths.add(path);
       }
       // Until every vertex is in the tree
       while (numberOfVerticesInTree < numberOfVertices) { // Do this until the number of of vertices in the tree equals the total number of vertices
           int indexMin = getMin();// Get the index of the of the vertex with the smallest distance from the vertices not yet in the tree
           int minDist = shortestPaths.get(indexMin).getDistance(); // Minimum distance to the vertices not yet in the tree

           if (minDist == INFINITY) {
               System.out.println("The graph has an unreachable vertex");
               break; // If only unreachable vertices have not been visited, then we exit the loop
           } else {
               currentVertex = indexMin; // Set currentVert to the index of the current vertex
               startToCurrent = shortestPaths.get(indexMin).getDistance(); // Set the distance to the current vertex
           }

           vertexList[currentVertex].setInTree(true);  // Add the current vertex to the tree
           numberOfVerticesInTree++; // Increase the count of vertices in the tree
           updateShortestPaths(); // Update the list of shortest paths
       }

       displayPaths(); // Display the results on the console
   }

   public void clear() { // Clear the tree
       numberOfVerticesInTree = 0;
       for (int i = 0; i < numberOfVertices; i++) {
           vertexList[i].setInTree(false);
       }
   }

   private int getMin() {
       int minDist = INFINITY; // The distance of the initial shortest path is taken to be infinite
       int indexMin = 0;
       for (int i = 1; i < numberOfVertices; i++) { // For each vertex
           if (!vertexList[i].isInTree() && shortestPaths.get(i).getDistance() < minDist) { // If the vertex is not yet in the tree and the distance to the vertex is less than the current minimum
               minDist = shortestPaths.get(i).getDistance(); // then update the minimum
               indexMin = i; // Update the index of the vertex with the minimum distance
           }
       }
       return indexMin; // Returns the index of the vertex with the smallest distance among those not yet in the tree
   }

   private void updateShortestPaths() {
       int vertexIndex = 1; // The initial vertex is skipped
       while (vertexIndex < numberOfVertices) { // Run over the columns

           if (vertexList[vertexIndex].isInTree()) { // If the column vertex is already in the tree, then we skip it
               vertexIndex++;
               continue;
           }
           // Calculate the distance for one element sPath
           // Get the edge from currentVert to column
           int currentToFringe = relationMatrix[currentVertex][vertexIndex];
           // Add up all the distances
           int startToFringe = startToCurrent + currentToFringe;
           // Determine the distance to the current vertexIndex
           int shortPathDistance = shortestPaths.get(vertexIndex).getDistance();

           // Compare the distance through currentVertex with the current distance in the vertex with index vertexIndex
           if (startToFringe < shortPathDistance) { // If it is smaller, then the vertex at vertexIndex is assigned the new shortest path
               List newParents = new ArrayList<>(shortestPaths.get(currentVertex).getParentVertices()); // Create a copy of the list of vertices of vertex currentVert's parents
               newParents.add(currentVertex); // And add currentVertex to it as the previous vertex
               shortestPaths.get(vertexIndex).setParentVertices(newParents); // Save the new path
               shortestPaths.get(vertexIndex).setDistance(startToFringe); // Save the new distance
           }
           vertexIndex++;
       }
   }

   private void displayPaths() { // A method for displaying the shortest paths on the screen
       for (int i = 0; i < numberOfVertices; 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 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() + ")");
           }
       }
   }
}

So that's all the magic =) 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("The following nodes form the shortest paths from node A:");
       graph.path();
       graph.clear();
   }
}

And the console output is this: The time complexity of this algorithm is none other than O(N²), since we have nested loops. That's all I've got today. Thanks for your attention!