Visually Explained Algorithms The Selection Sort algorithm sorts an array by looking for the smallest item and moving it to the front of the list. That’s really all you have to know. Let’s jump into an example. Selection Sort starts by setting the first value as the minimum value. It then starts comparing it with each value in the array. If a lower value is found, the minimum value is updated, and the traversal continues until the end of the array is reached. During the first comparison, the value at index 1 is compared to the minimum value. Since the
Category: Education
Visually Explained Algorithms The adjacency matrix is a square matrix that’s used to represent a graph. The elements that are next to each other represent adjacent vertices. Why would you want to create an adjacency matrix? To save time. The adjacency matrix 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 adjacency matrix from a directed graph. Although the graph looks complicated, creating an adjacency matrix is a simple process. Since there are 6 vertices, the adjacency matrix will have 6 rows and
Visually Explained Algorithms The adjacency list is another way to represent adjacent vertices. Why would you want to create an adjacency list? Again, to save time. The adjacency list is much more efficient when trying to figure out the adjacent nodes in a graph. Adjacency list also takes up less space than the adjacency matrix. In the adjacency matrix, each node must contain a value, regardless of whether it contains an edge to another node or not. The adjacency list only contains nodes that are connected. Let’s look at an example of how someone would create an adjacency list from
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
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