Tutorial by Examples

A topological ordering, or a topological sort, orders the vertices in a directed acyclic graph on a line, i.e. in a list, such that all directed edges go from left to right. Such an ordering cannot exist if the graph contains a directed cycle because there is no way that you can keep going right ...

Thorup's algorithm for single source shortest path for undirected graph has the time complexity O(m), lower than Dijkstra. Basic ideas are the following. (Sorry, I didn't try implementing it yet, so I might miss some minor details. And the original paper is paywalled so I tried to reconstruct it fr...

A cycle in a directed graph exists if there's a back edge discovered during a DFS. A back edge is an edge from a node to itself or one of the ancestors in a DFS tree. For a disconnected graph, we get a DFS forest, so you have to iterate through all vertices in the graph to find disjoint DFS trees. ...

Graph Theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects. Did you know, almost all the problems of planet Earth can be converted into problems of Roads and Cities, and solved? Graph Theory was invented many years ago, even before the in...

To store a graph, two methods are common: Adjacency Matrix Adjacency List An adjacency matrix is a square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph. Adjacent means 'next to or adjoining something el...

Adjacency list is a collection of unordered lists used to represent a finite graph. Each list describes the set of neighbors of a vertex in a graph. It takes less memory to store graphs. Let's see a graph, and its adjacency matrix: Now we create a list using these values. This is called adjacen...