Graph Algorithms
Everything on SkillVeris tagged Graph Algorithms — collected across the glossary, study notes, blog, and cheat sheets.
38 resources across 2 libraries
Cheat Sheets(1)
Interview Questions(37)
BFS vs DFS: What is the Difference?
BFS (breadth-first search) explores a graph level by level using a queue, while DFS (depth-first search) explores as deep as possible along one path before bac…
What is a Graph?
A graph is a data structure made of nodes (vertices) connected by edges, used to model relationships and connections such as networks, maps, or dependencies, a…
What is Dijkstra’s Algorithm?
Dijkstra’s algorithm finds the shortest path from a single source vertex to every other vertex in a weighted graph with non-negative edge weights, using a gree…
What is the Bellman-Ford Algorithm?
Bellman-Ford finds shortest paths from a single source to every other vertex in a weighted graph by relaxing all edges repeatedly for V-1 rounds, and unlike Di…
What is the Floyd-Warshall Algorithm?
Floyd-Warshall is a dynamic programming algorithm that computes the shortest path between every pair of vertices in a weighted graph in O(V^3) time by progress…
What is Kruskal's Algorithm?
Kruskal's algorithm builds a minimum spanning tree by sorting all edges by weight ascending and greedily adding each edge that connects two previously disconne…
What is Prim's Algorithm?
Prim's algorithm builds a minimum spanning tree by growing a single connected tree from an arbitrary start vertex, at each step adding the cheapest edge that c…
What is the A* Search Algorithm?
A* search finds the shortest path between two specific nodes by combining Dijkstra's guaranteed-shortest exploration with a heuristic estimate of remaining dis…
What is Union-Find (Disjoint Set Union)?
Union-Find, or Disjoint Set Union (DSU), is a data structure that tracks a collection of non-overlapping sets and answers "are these two elements in the same g…
What is Kosaraju's Algorithm?
Kosaraju's algorithm finds all strongly connected components (SCCs) of a directed graph in O(V + E) time using two depth-first search passes: one on the origin…
What is Tarjan's Algorithm?
Tarjan's algorithm finds all strongly connected components (SCCs) of a directed graph in a single O(V + E) DFS pass by tracking each vertex's discovery time an…
What is Level-Order Tree Traversal?
Level-order traversal visits a binary tree one depth level at a time, left to right, by pushing the root into a FIFO queue and repeatedly dequeuing a node, vis…
Word Ladder Problem: How Would You Solve It?
Word ladder is solved with BFS over an implicit graph where each word is a node and an edge connects two words differing by exactly one letter, because BFS exp…
Number of Islands Problem: How Would You Solve It?
Number of islands is solved by scanning the grid and, each time an unvisited land cell is found, running a flood-fill (DFS or BFS) that marks every orthogonall…
What is the Flood Fill Algorithm?
Flood fill is a traversal algorithm that starts at a given cell in a grid and recursively or iteratively spreads to all orthogonally (or optionally diagonally)…
Course Schedule Problem: How Would You Solve It?
Course schedule is a cycle-detection problem on a directed graph where each course is a node and a prerequisite relationship is a directed edge, and all course…
What is the Graph Coloring Problem?
Graph coloring assigns a label, or color, to every vertex of a graph so that no two adjacent vertices share the same color, and the goal is usually to do it wi…
What is the Hamiltonian Path Problem?
A Hamiltonian path is a path through a graph that visits every vertex exactly once, and finding one (or deciding one exists) is NP-complete in general, solved…
What is the Traveling Salesman Problem?
The Traveling Salesman Problem (TSP) asks for the shortest possible route that visits every city exactly once and returns to the start, and it is NP-hard, mean…
What is a Minimum Spanning Tree?
A minimum spanning tree (MST) is a subset of a connected, weighted, undirected graph's edges that connects every vertex together, contains no cycles, and has t…
How Do You Find the Shortest Path in an Unweighted Graph?
The shortest path between two vertices in an unweighted graph is found with breadth-first search (BFS), which explores the graph level by level from the source…
What is the Single-Source Shortest Path Problem?
Single-source shortest path (SSSP) finds the minimum-cost route from one fixed source vertex to every other reachable vertex in a graph, solved with BFS for un…
What is the All-Pairs Shortest Path Problem?
All-pairs shortest path (APSP) computes the minimum-cost route between every pair of vertices in a graph at once, typically solved with the Floyd-Warshall algo…
What are Strongly Connected Components?
A strongly connected component (SCC) is a maximal set of vertices in a directed graph where every vertex can reach every other vertex in the set via a directed…
Showing 24 of 37.