# graph theory

There's a total of 11 articles.

### Hamiltonian Graphs → Read more...

Hamiltonian graphs and hamiltonian cycles.

### Eulerian Graph and Eulerian Trails → Read more...

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 how it’s impossible to find a trail on it. Finally there are two implementations in C++ to find Eulerian trails in directed and underected graphs.

### Single Source Shortest Path (SSSP) in a graph → Read more...

Given a weighted graph $G$ with $V$ vertices and $E$ edges where all the weights are non-negative and given a source vertex $s$, the single source shortest path problem consists in finding the distance from $s$ to all the 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.

### Introduction to Trees in Graph Theory → Read more...

Introduction to trees in Graph Theory

### Strongly Connected Components in Graph Theory → Read more...

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.

### Minimum Spanning Tree → Read more...

This article covers minimum spanning tree (MST), MSTs have important applications, MST can be used to minimize the cost of building a communication network, or it can be used 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, also with the theory covered I also implement an algorithm to find the number of nimal spanning trees in a graph.

### Cut-vertices (articulation points) in Graph Theory → Read more...

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$ but $v$ and a set of edges $G - V$ where $V$ consists of all the edges incident to $v$).

In this article I implement an algorthm to find the articulation points in an undirected graph, also I explain biconnected components in an undirected graph and explain concepts such as edge connectivity and vertex connectivity.

### Cut-edges (bridges) in Graph Theory → Read more...

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 algorthm to find the bridges of an undirected graph using DFS. Next I describe an algorithm to find strong bridges in directed graphs.

### Topological sorting of a graph → Read more...

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 as well as an example of how to use it to find the shortest path in a directed acyclic graph.

### Traversal of graphs → Read more...

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 about edges like finding back edges, forward edges and cross edges.