Visually Explained Algorithms The edge list is another way to represent adjacent vertices. Why would you want to create an edge list? Again, to save time. The edge list is much more efficient when trying to figure out the adjacent nodes in a graph. Let’s look at an example of how someone would create an edge list from a directed graph. The edge list contains a list of edges in alphanumerical order. We start by filling in all the outbound edges from vertex 1. Vertex 1 has one outbound edge to vertex 6, so that edge is stored. Moving through
Articles
Visually Explained Algorithms The Depth First Search algorithm traverses the graph and explores each adjacent node before backtracking and moving to the next node. It utilizes the stack data structure. Remember, the stack uses the last-in-first-out (LIFO) approach. We push items onto the stack and pop items from the top of the stack. We’ll keep track of the stack and we’ll show the vertices in the order of which they were discovered. We’ll begin our traversal at vertex A. Vertex A has been discovered, so it’s added to the discovery list. Vertex A is also pushed onto the stack and
Visually Explained Algorithms Topological sorting is the result you get when you sort the tree in order of decreasing finishing times. What this means is that you run the Depth First Search algorithm and once it’s complete, you’ll have two sets of values: discovery times and finishing times. Finishing times sorted in reverse will generate the topologically sorted list. DFS starts traversing the tree at vertex A. Since it has been discovered, we’ll mark it with the number 1. Number 1 is used to indicate that it has been discovered first. The algorithm checks all the unvisited nodes from vertex
Algorithms Visually Explained The Breadth First Search algorithm is like the Depth First Search algorithm with the exception that it uses a queue rather than a stack. BFS is technically the opposite of DFS since the BFS algorithm explores the deepest nodes first before backtracking to explore the shallower nodes. An element can be enqueued or dequeued. The queue works on a first-in-first-out principle (FIFO), which means that the element that was enqueued first will be dequeued first. BFS works like this: Select the first node Explore all unvisited nodes and enqueue them Once all unvisited, adjacent nodes have been
Visually Explained Algorithms The Greedy Method is an approach for solving certain types of optimization problems. The greedy algorithm chooses the optimum result at each stage. While this works the majority of the times, there are numerous examples where the greedy approach is not the correct approach. For example, let’s say that you’re taking the greedy algorithm approach to earning money at a certain point in your life. You graduate high school and have two options: Get a job that only requires a high school diploma Go to college and then get a job after you graduate from college The
Algorithms Visually Explained The Minimum Spanning Tree connects all vertices utilizing the minimum path. This is just a quick intro since we will cover MSTs in detail in a couple of later articles, but we’ll show a quick example of what an MST looks like. We’re not going to take any algorithmic approach, but instead use intuition in this example. We can see that there are two negative edges in this graph, so most likely they’ll be part of the minimum spanning tree. We’ll start by adding those edges. From there, we can add edges from vertices D, E, and
Visually Explained Algorithms Kruskal’s algorithm generates a minimum spanning tree. The way it works is that it keeps selecting the least costly edge until a minimum spanning tree is created. The only constraint is that a cycle doesn’t appear once the least costly edge is selected. Let’s look at an example. There are 10 vertices and each vertex has at least one edge connecting to it. We’ll look through the edges until we find the least costly edge. We can quickly see that edge F-I has the least costly edge, so we’ll include it first. Next, there are two edges
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
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