Graph (data structure)

Types of graphs

• Directed / Undirected — edges are directed (A→B) or not (A—B)
• Weighted — edges have a weight (distance, cost)
• Cyclic / Acyclic — contains cycles or not
• DAG (Directed Acyclic Graph) — directed with no cycles. The npm/composer dependency graph

Representations

• Adjacency Matrix — 2D array. O(1) edge lookup, O(V²) memory
• Adjacency List — list of neighbours. O(V+E) memory, usually more efficient

Traversal algorithms

• BFS (Breadth-First Search) — level by level, queue. Shortest path in an unweighted graph
• DFS (Depth-First Search) — in-depth, stack. Cycle detection, topological sort