DAG

Source board

This definition comes from the board below. Open it to see the term in context.

GraphsDSA

More 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)
• 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
• sparse vs densefew vs many edges relative to V²
• topological sorta dependency-respecting order of a DAG (DFS post-order or Kahn's)
• union-findfast connected-components
• weightededges carry a cost