DSA
sparse vs dense
few vs many edges relative to V²
Source board
This definition comes from the board below. Open it to see the term in context.
GraphsDSAMore terms from this board
- A*Dijkstra + heuristic
- adjacency listvertex→neighbours (O(V+E), sparse)
- adjacency matrixV×V grid (O(V²), O(1) edge test, dense)
- Bellman-Fordhandles negatives
- BFSlevel-order via a queue (shortest unweighted)
- DAGdirected acyclic graph
- DFSdeep-first via a stack/recursion
- Dijkstramin-cost path via a priority queue (non-negative weights, O((V+E)log V))
- directed vs undirectedone-way vs mutual
- in-degreeincoming edges
- MSTminimum spanning tree (Kruskal/Prim)
- relax an edgeupdate a node's best-known distance
- topological sorta dependency-respecting order of a DAG (DFS post-order or Kahn's)
- union-findfast connected-components
- weightededges carry a cost