Visually Explained Algorithms Prim’s Algorithm is similar to Kruskal’s Algorithm. It’s a greedy algorithm that finds the MST (minimum spanning tree) for a weighted, undirected graph. Starting at an arbitrary ve rtex, the algorithm builds the MST one vertex at a time where each vertex takes the shortest path from the root node. Let’s move to our example. Although we can begin with any vertex, we’ll choose vertex A for this example. Vertex A has direct edges to B and I. The cost to vertex B is 7 and the cost to vertex I is 15. Since Prim’s algorithm is a greedy

# Category: Computer Science

Visually Explained Algorithms There are three types of depth first binary tree traversals: Pre-order: <root><left><right> In-order: <left><root><right> Post-order: <left><right><root> We will be focusing on the In-Order Binary Tree Traversal. We can see that starting from the root node, we’ll visit all the nodes in the left subtree, come back to the root node and then visit all the vertices in the right subtree. Next to each node, we’ll put a couple of reminders for ourselves: left subtree visit/print node right subtree We’ll begin with the root node. At this point, we can cross out the left subtree label and start

Expanding Branches When inserting a node, remember this rule: nodes will only be added as leaves in the tree. Let’s assume we have the following tree. If we look at this tree, you’ll notice that at each node, values in the left subtree are smaller than the value of the node, and values in the right subtree are larger than the node’s value. Let’s say we wanted to insert the value 35. Can you predict where it would be in the tree? Let’s walk through it and see where it ends up. We start by comparing 35 to the root

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

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