Hamiltonian graphs and Hamiltonian cycles.

This article discusses Eulerian circuits and trails in graphs. An Eulerian circuit is a closed trail that contains every edge of a graph, and an Eulerian trail is an open trail that contains all the edges of a graph but doesn't end in the same start vertex. This article also explains the Königsberg Bridge Problem and why it's impossible to find a trail in it. Finally, there are two implementations in C++ to find Eulerian trails in directed and undirected graphs.

Given a weighted graph $G$ with $V$ vertices and $E$ edges, where all the weights are non-negative, and a source vertex $s$, the single-source shortest path problem consists of finding the distance from $s$ to all other vertices. In this article, I describe the problem in a weighted and unweighted graph, as well as implementations using BFS for unweighted graphs and Dijkstra's algorithm for weighted graphs using an array and a priority queue.

An introduction to trees in graph theory.

A strongly connected component of a directed graph is a subgraph in which there exists a path from every vertex to every other vertex in the subgraph. In this article, I implement Tarjan's algorithm to find strongly connected components in a graph.

This article covers the minimum spanning tree (MST). MSTs have important applications; for example, they can be used to minimize the cost of building a communication network or to identify important features or patterns in a dataset. I implement the Prim and Kruskal algorithms to find the minimum spanning tree in a graph, with different implementations for sparse and dense graphs. With the theory covered, I also implement an algorithm to find the number of minimal spanning trees in a graph.

A vertex $v$ in a connected graph $G$ is called a **cut-vertex** if $G - v$ results in a disconnected graph. Note that $G - v$ is an induced subgraph of $G$ (meaning that $G - v$ contains all the vertices of $G$ except $v$ and a set of edges $G - E_v$, where $E_v$ consists of all the edges incident to $v$). In this article, I implement an algorithm to find the articulation points in an undirected graph. I also explain biconnected components in an undirected graph and concepts such as edge connectivity and vertex connectivity.

An edge $e = uv$ of a connected graph $G$ is called a bridge if $G - e$ is disconnected (it increases the number of components). In this article, I implement an algorithm to find the bridges of an undirected graph using DFS. Next, I describe an algorithm to find strong bridges in directed graphs.

Topological sorting is a linear ordering of the vertices of a directed acyclic graph (DAG) such that for every directed edge (u, v), vertex u comes before vertex v in the ordering. In other words, it is a way to order the vertices of a DAG such that there are no directed cycles. In this article, I implement the topological sorting algorithm and provide an example of how to use it to find the shortest path in a directed acyclic graph.

There are many ways to traverse a graph. For example, through breadth-first search and depth-first search. Exploring it with a breadth-first search has interesting properties, like implicitly computing the distance from a source $s$ to all the reachable vertices. Exploring it with a depth-first search has properties related to edges, like finding back edges, forward edges, and cross edges. This article has implementations for both BFS and DFS.

Graph theory has numerous applications in real life. It can be used in problems found in social networks, transportation networks, the internet, chemistry, computer science, and electrical networks, among others. In general, any problem that involves relationships between objects can be modeled as a graph.