This repository contains Python implementations of various graph algorithms, including Breadth-First Search (BFS), Depth-First Search (DFS), Bellman-Ford, Dijkstra's, Prim's, Warshall's, and Topological Sort algorithms.
Graph algorithms are fundamental in computer science, allowing us to solve various problems related to graphs and networks. This repository showcases efficient Python implementations of popular graph algorithms for traversal, shortest path, minimum spanning tree, transitive closure, and topological ordering.
- Performs a level-order traversal of a graph, visiting all the neighbors of a node before moving to the next level.
- Explores as far as possible along each branch before backtracking, useful in finding connected components and cycles in a graph.
- Finds the shortest path in a weighted graph with negative edge weights, detecting negative cycles.
- Determines the shortest path from a single source to all other nodes in a graph with non-negative edge weights.
- Constructs a minimum spanning tree in a connected and undirected graph, minimizing the total edge weight.
- Computes the transitive closure of a directed graph, determining paths between all pairs of vertices.
- Sorts the vertices of a directed acyclic graph (DAG) in such a way that for every directed edge from vertex A to vertex B, A comes before B in the ordering.
Clone the repository and explore each algorithm implementations:
git clone https://github.com/AhmedHoussamBouzine/graph-algorithms-implementation-in-python.git