Tag Archives: Mathematics

Computer Algorithms: Graph Best-First Search

algorithms, data structures, , , , , , , , , , , , , , , ,

Introduction

So far we know how to implement graph depth-first and breadth-first search. These two approaches are crucial in order to understand graph traversal algorithms. However they are just explaining how we can walk through in breadth or depth and sometimes this isn’t enough for an efficient solution of graph traversal.

In the examples so far we had an undirected, unweighted graph and we were using adjacency matrices to represent the graphs. By using adjacency matrices we store 1 in the A[i][j] if there’s an edge between vertex i and vertex j. Otherwise we put a 0. However the value of 1 gives us only the information that we have an edge between two vertices, which is not always enough when designing graphs.

Indeed graphs can be weighted. Sometimes the path between two vertices can have a value. Thinking of a road map we know that distances between cities are represented in miles or kilometers. Thus often representing a road map as a graph, we don’t put just 1 between city A and city B, to say that there is a path between them, but also we put some meaningful information – let’s say the distance in miles between A and B.

Note that this value can be the distance in miles, but it can be something else, like the time in hours we’ve to walk between those two cities. In general this value is a function of A and B. So if we keep the distance between A and B we can say this function is F(A, B) = X, or distance(A, B) = X miles.

Of course in this particular example F(A, B) = F(B, A), but this isn’t always true in practice. We can have a directed graph where F(A, B) != F(B, A).

Here I talk about distance between two cities and it is the edge that brings some additional information. However sometimes we have to store the value of the vertices. Let’s say I’m playing a game (like chess) and each move brings me some additional benefit. So each move (vertex) can be evaluated with some particular value. Thus sometimes we don’t have a function of and edge like F(A, B), but function of the vertices, like F(A) and F(B).

In breadth-first search and depth-first search we just pick up a vertex and we consecutively walk through all its successors that haven’t been visited yet.

Walk Through an Unweithed Graph
In order to walk through an unweithed graph using DFS, we chose consecutively each successor of node i!

So in DFS in particular we started from left to right in the array above. So the first node that has to be explored is vertex “1”.

0: [0, 1, 0, 0, 1, 1]

However sometimes, as I said above, we have weighted graphs, so the question is – is there any problem, regarding to the algorithm speed, if we go consecutively through all successors. The answer in general is yes, so we must modify a bit our code in order to continue not with the first but with the best matching successor. By best-matching we mean that the successor should match some criteria like – minimal or maximal value. Continue reading Computer Algorithms: Graph Best-First Search →

Computer Algorithms: Graph Depth-First Search

algorithms, data structures, , , , , , , , , , , ,

Introduction

Along with breadth-first search, depth-first search is one of the two main methods to walk through a graph. This approach though is different. Breadth-first search (BFS) looks pretty much like starting from a vertex and expanding the searching process level by level. This means that first we get some information of all the successors of the given node and then we go further with the next level. In other words BFS is like a wave. Depth-first search is based on a different approach, which can be very useful in some specific algorithms.

DFS vs. BFS
Depth-first and breadth-first search are the two main ways to explore a graph!

Both methods can be useful in solving different tasks. Continue reading Computer Algorithms: Graph Depth-First Search →

Computer Algorithms: Graph Breadth First Search

algorithms, data structures, , , , , , , , , , , ,

Introduction

Since we already know how to represent graphs, we can go further for some very simple approaches of walking through them. Passing by all the vertices of a graph is a fundamental technique for most of the graph algorithms, such as finding shortest/longest paths, etc.

First thing to note is that graphs are not trees, in most of the cases, so walking through them can’t start from a root, as we do with trees. What we must do first is to decide from where to start – in other words – choosing a starting vertex.

BFS Choosing a Starting Point
It’s clear that depending on the starting point we can get different passes through the graph. Thus choosing a starting point can be very important for our algorithm!

After that we need to know how to proceed. There are two approaches mostly known as “breadth first” and “depth first” search. While depth first search start from a vertex and goes as far as possible, then walks back and passes through vertices that haven’t been visited yet, breath first search is an approach of passing through all the neighbors of the node first, and then go to the next level.
Continue reading Computer Algorithms: Graph Breadth First Search →

Computer Algorithms: Graphs and their Representation

algorithms, data structures, , , , , , , , , , , , ,

Introduction

Although this post is supposed to be about algorithms I’ll cover more on graphs and their computer representation. I consider this very important, because there are lots of problems solved by using graphs and it is important to understand different types of representation.

First of all let’s try to explain what is a graph?

A graph is a specific data structure known in the computer science, that is often used to give a model of different kind of problems where a set of objects relate to each other in some way . For instance, trees are mainly used in order to represent a well-structured hierarchy, but that isn’t enough when modeling objects of the same type. Their relation isn’t always hierarchical! A typical example of graph is a geo map, where we have cities and the roads connecting them. In fact most of the problems solved with graphs relate to finding the shortest or longest path.

Although this is one very typical example actually a huge set of problems is can be solved by using graphs.

Graph & Tree
 

Continue reading Computer Algorithms: Graphs and their Representation →

Computer Algorithms: Heap and Heapsort

algorithms, data structures, , , , , , , , , , , , , ,

Introduction

Heapsort is one of the general sorting algorithms that performs in O(n.log(n)) in the worst-case, just like merge sort and quicksort, but sorts in place – as quicksort. Although quicksort’s worst-case sorting time is O(n2) it’s often considered that it beats other sorting algorithms in practice. Thus in practice quicksort is “faster” than heapsort. In the same time developers tend to consider heapsort as more difficult to implement than other n.log(n) sorting algorithms.

In the other hand heapsort uses a special data structure, called heap, in order to sort items in place and this data structure is quite useful in some specific cases. Thus to understand heapsort we first need to understand what is a heap.

So first let’s take a look at what is a heap.

Overview

A heap is a complete binary tree, where all the parents are greater than their children (max heap). If all the children are greater than their parents it is considered to call the heap a min-heap. But first what is a complete binary tree? Well, this is a binary tree, where all the levels are full, except the last one, where all the items are placed on the left (just like on the image below).

Complete Binary Tree
A complete binary tree is a structure where all the levels are completely full, except the last level, where all the items are placed on the left!
Continue reading Computer Algorithms: Heap and Heapsort →