*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.

## 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:- Visit a previously unvisited adjacent vertex, mark it as visited, and push it onto the stack.
- Move to this vertex.
- Repeat step 1.
- 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.
- Continue until all the vertices are on the stack.

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

```
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:
## 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.

- 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.
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.

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.

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.

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

We find the shortest path to its neighbor F.

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

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

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.

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

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.

```
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:
GO TO FULL VERSION