Dijkstra’s algorithm is the most popular algorithm to find the shortest paths from a certain vertex in a weighted graph.In fact, the algorithm will find the shortest paths to every vertex from the start vertex.The algorithm takes both greedy and dynamic programming approach that it will try to find local optimum paths first and use READ MORE
Month: March 2020
Basics of C++ Class
C++ class is a custom data type user defines, which is called user-defined type.A data type in C++ represents certain types of data.For example, there are built-in types such as int and double which represent integer and decimal numbers.Declaring a variable with a data type requires memory and you can perform operations such as addition, READ MORE
Python – best practices using else block
Typical use case of else block is with if in many programming languages.It usually serves as branch control such if it doesn’t meet certain conditions in if block it will just execute else block instead of if block.And it is the same case for python else block too. However, python extended else block usage more READ MORE
C++ Filestream
In C++, you can interact (read/write) with disk files using filestream classes.The C++ filestream is very similar to standard cin and cout streams.Just like cin and cout, there are two classes for filestream: ifstream for input and ofstream for output.For the input stream, you can imagine there is a stream connected to disk file and READ MORE
Intro to Union-Find Data Structure
Union-Find is a data structure that mimics tree data structure except that nodes point to their parent instead of children. The union-find is very useful for set operations such as the following.1. find – find the root of the current node2. same component – check if two trees have the same root node. (belongs to READ MORE
C++ Standard Library C-string Functions
C-string is a char array terminated with a null byte(‘\0’), which is the original string that was used since C and early C++.C/C++ standard library provides useful C-string functions.The header you need to include to use C-string functions is <cstring>.In this post, I am going to explain some popular C-string functions with example codes. Before READ MORE
How to detect a loop (cycle) in a linked list
Traversing linked list is easy but what would happen if there is a cycle in the linked list?It will just fall into an infinity loop if traversing is implemented without a cycle prevention code.Thankfully, there is already a known algorithm for this kind of problem. How to detect if a cycle exists? Suppose there is READ MORE
Intro to Topological Sort
Topological sort is an important algorithm in DAG – directed acyclic graphs. It orders each vertex in line from left to right such that left most vertex could be considered as the highest level or root or entrance of the graph and rightmost as the lowest of the graph. In the end, topological sort tells READ MORE
Intro to Depth First Search (DFS)
Depth first search is one of the popular graph traversal algorithms that work well for certain purposes.As you can infer from the name DFS is quite different from BFS – breadth first search.Therefore the applications of DFS are different from BFS.In this post, I am going to discuss how DFS works with examples.Please refer to READ MORE
Intro to Breadth First Search (BFS)
When dealing with a graph it might be necessary to traverse the graph.Graph traversal is a systemic method to traverse the graph.Breadth first search is one of the most popular graph traversal algorithms that work very well for certain purposes.Today, I am going to introduce breadth first search in this post. How does breadth first READ MORE