Trimming Leaves Algorithmically When deleting a leaf in the tree, the structure of the tree does not change. If we examine the tree below, the outlined nodes can be deleted safely without changing the overall structure of the tree. The leaves circled in red can simply be removed without modifying the existing leaf structure. Nodes that pointed to the deleted leaf node will no longer point to that node. You thought this would be a tediously long explanation? Nope. Like I try to reiterate through my articles, simplicity is key. Don’t overthink it. Computer Science topics, especially Algorithms, can be
Author: Dino Cajic
Trimming the Branches Exactly what it sounds like. We’ll be deleting a node from a tree that has only one child. Let’s look at our tree and examine which nodes have one child. In our example, only node 33 has one child. All other nodes have two children. If we removed node 47 from the list, we would have two nodes that have 1 child each; node 40 would have one immediate child and node 33 would have one immediate child. However, let’s keep the example as is. It is important for the reader to have this visual in their
Visual Explanation of Deleting a Node with Two Children What would happen if we wanted to remove node 40 from the tree below? Since node 40 has two children, we can’t simply point to its child and hope it works. There’s an algorithmic approach to this problem too. The way we remove this node is by replacing it with the next largest value. How do we get the next largest value? By going into the right subtree, and then following the left subtree until we get to the leaf node. Let’s look at that more closely. We enter node 40’s right
Planar Graphs Demystified A planar graph is a graph that can be drawn on the plane with no intersecting arcs. The edges can intersect only at endpoints. Let’s look at a couple of planar graphs. Let’s also take a quick look at a graph that is not planar. This is the famous K5 graph. We’ll attempt to make it planar. After step 1, we can see that intersecting edges still exist. Let’s see what step 2 and 3 look like. We can see that in step 2, it still looks promising. There’s only one additional intersecting edge that must be
A Visual Guide to Longest Common Subsequence Another type of problem that arises in computer science is finding the longest common subsequence. If you have the following string, BEADCA and ABCDA, what is the longest common subsequence? You can probably quickly figure out that the longest common subsequence of these two strings is BDA. It is possible to have multiple subsequences that are of equal length that would work. Let’s see how we would find the longest common subsequence in this problem. We begin by constructing a matrix. One sequence goes on top of the matrix and the other goes
All-Pairs Shortest Path Matrix Multiplication You’re presented with a graph and your goal is to find all-pairs of shortest paths using dynamic programming. The first step is to create a matrix where the number of rows and columns equals the number of vertices and then to populate it with initial data. For each vertex that can be reached by one hop, you will populate it with the edge weight. If a vertex cannot be reached with one hop, you will populate it with infinity and if a vertex is trying to reach itself, you will populate it with zero. Let’s
A Visual Guide to Floyd-Warshall and Matrix Multiplication The goal of the Floyd-Warshall algorithm is to find the shortest paths in a tree using Dynamic Programming. Let’s get started with an example. The Floyd-Warshall algorithm starts by gathering the initial weights and placing them into a matrix. Since there are 4 vertices, the matrix will have 4 rows and 4 columns. Starting with vertex 1, the algorithm gathers the initial weights from 1 to the other 3 vertices. It will place a 0 for itself and infinity if there is no direct path. The edge weight from 1 to itself
Visualizing Dijkstra’s Single Source Shortest Path Dijkstra’s Algorithm can be applied to either a directed or an undirected graph to find the shortest path to each vertex from a single source. It can only be used with non-negative edge weights. A table is generated to track the distance from the source (S) vertex. The distance to each vertex is initialized to infinity except for the source itself. Another variable, π, is used to track the previous vertex from which the specified vertex was reached. Dijkstra’s algorithm starts with the source, S, and relaxes the edges that are connected directly to
Exploring Shortest Paths The Bellman-Ford algorithm finds the shortest path to each vertex in the directed graph from the source vertex. Unlike Dijkstra’s algorithm, Bellman-Ford can have negative edges. To begin, all the outbound edges are recorded in a table in alphabetical order. Like Dijkstra’s algorithm, a table recording the distance to each vertex and the predecessor of each vertex is created. The distances for each vertex, except the source vertex, is initialized to infinity. Distance is represented by the variable d and the predecessor is represented by the variable π. The Bellman-Ford algorithm will iterate through each of the edges.
Visual Explanation of Johnson’s Algorithm Johnson’s algorithm finds the shortest paths between all pairs of vertices in a directed graph. It converts negative edge weights into non-negative edge links. It does this by using the Bellman-Ford algorithm to remove all negative weights. It then allows Dijkstra’s algorithm to be used on the new graph. Let’s start with an example. Since this graph contains negative edges, Dijkstra’s algorithm cannot be applied to it yet. To begin, the edge links must be transformed to contain non-negative numbers. Johnson’s algorithm starts off by selecting a source vertex. The problem with choosing an existing