9 docs tagged with "graph-theory"

An overview of the Bellman-Ford algorithm, including its implementation in C++, Java, and Python, time complexity analysis, and comparison with Dijkstra's algorithm.

The Bron-Kerbosch algorithm is a backtracking algorithm used to find all maximal cliques in an undirected graph. Known for its efficiency, especially on sparse graphs, it is widely applied in social network analysis, bioinformatics, and computational chemistry. The algorithm can be optimized with pivoting to reduce recursive calls and improve performance.

An overview of the Disjoint Set Union (Union Find) data structure, including implementations in C++, Java, and Python, complexity analysis, and applications.

The Edmonds-Karp algorithm is a flow network algorithm used to compute the maximum flow between a source and a sink in a flow network. It is an implementation of the Ford-Fulkerson method that uses breadth-first search (BFS) to find augmenting paths.

This post explores Eulerian graphs, their properties, and algorithms for detecting and constructing Eulerian paths and circuits.

Hamiltonian Path and Cycle problems are a classic graph theory problem where the task is to find a path or cycle that visits every vertex exactly once. These problems are NP-complete and are widely used in various applications such as route planning, logistics, and genome sequencing.

Prim's algorithm is a greedy algorithm that finds the Minimum Spanning Tree (MST)

Tarjan's algorithm is an efficient method for finding strongly connected components in a directed graph.

Topological Sorting is a linear ordering of vertices in a directed acyclic graph (DAG) such that for every directed edge u -> v, vertex u comes before v.