Depth-First Search (DFS)
DFS explores a graph by visiting nodes as deeply as possible before backtracking, using recursion or a stack.
Exploration Algorithms
Breadth-First Search (BFS)
BFS explores a graph level by level, starting from a source node, using a queue to keep track of nodes to visit.
Shortest Path Algorithms
Dijkstra's Algorithm
Finds the shortest path from a source node to all other nodes in a graph with non-negative edge weights, using a priority queue.
A* Search Algorithm
Extends Dijkstra's Algorithm by using heuristics to guide its search towards a destination node.
Bellman-Ford Algorithm
Finds shortest paths from a source node to all other nodes, handling negative edge weights and detecting negative weight cycles.
Floyd-Warshall Algorithm
Computes shortest paths between all pairs of nodes in a weighted graph, including graphs with negative weights but no negative cycles.
Minimum Spanning Tree (MST) Algorithms
Kruskal's Algorithm
Finds a minimum spanning tree by selecting edges with the smallest weights while avoiding cycles.
Prim's Algorithm
Builds a minimum spanning tree by starting from an arbitrary node and adding the smallest edge that connects the tree to a new vertex.
Topological Ordering
Kahn's Algorithm
Performs topological sorting on a directed acyclic graph (DAG), ordering nodes linearly without violating edge directions.
Advanced Algorithms
⚠️ Advanced Territory Ahead! These algorithms are more advanced and included for completeness.
Tarjan's Algorithm
Finds strongly connected components in a directed graph using depth-first search and low-link values.
Kosaraju's Algorithm
Identifies strongly connected components by performing two passes of depth-first search.
Edmonds-Karp Algorithm
Computes the maximum flow in a flow network using BFS to find augmenting paths in the Ford-Fulkerson method.