Depth First Search (DFS) in a Graph

Depth first search is an algorithm which searches or traverses all the vertices in a graph. It starts to traverse the graph based on a start vertex. The algorithm traverses the vertices in depth. As graphs can have cycles we should not visit any visited vertex twice. For this purpose the algorithm must know if …

Breadth First Search (BFS) in a Graph

Breadth first search is an algorithm which searches or traverses all the vertices in a graph. It starts to traverse the graph based on a start vertex. The algorithm traverses the vertices from closest ones to farthest ones. As graphs can have cycles we should not visit any visited vertex twice. For this purpose the …

Gale–Shapley algorithm (Stable matching)

The algorithm we are going to explain is called Gale-Shapley algorithm after mathematical economist David Gale and Lloyd Shapley who described and analyzed in 1962. In this algorithm individuals are making choices that are all individually reasonable in order to come out with a globally acceptable solution also called stable matching. Let's clarify what stable …

Heap Sort

We explained heap and priority queue in one of our previous posts which you can check here. We will describe how heap sort algorithm works based on what we have learned about heap data structure. If you remember heap data structure is a complete binary tree which satisfies the heap properties of min or max …

Dijkstra’s Algorithm

Dijkstra's algorithm is a popular algorithm created by Edsger W. Dijkstra in 1956 to find the shortest path between two vertices in a weighted graph, where edges have weight or distance which shows the distance/weight between two vertices. The algorithm has many applications in real world like in maps finding the shortest route between two locations, …