Graph Variants

Graph-Based Data Structures

Type	Description	Key Characteristic	Typical Use Case	Access Pattern	Memory Behavior	Notes
Graph	Vertices + edges	General relationship model	Networks	Traversal-based	Node-based	Base concept
Adjacency List	Edge lists per vertex	Space efficient	Sparse graphs	Neighbor-based	Pointer-based	Common representation
Adjacency Matrix	2D edge table	Fast edge lookup	Dense graphs	Indexed	Contiguous	O(V²) space
Directed Graph	Edges have direction	One-way relationships	Dependencies	Traversal-based	Node-based	Asymmetric
Directed Acyclic Graph	No cycles	Topological order	Scheduling	Path-based	Node-based	No loops
Propositional DAG	Logical expression DAG	Boolean optimization	Compilers	Path-based	Node-based	Logic graphs
Multigraph	Multiple edges allowed	Parallel edges	Transport networks	Traversal-based	Node-based	Self-loops allowed
Hypergraph	Edges connect many nodes	Multi-node relations	VLSI, databases	Set-based	Node-based	Generalizes graphs
Graph-structured Stack	Stack with graph links	Multiple predecessors	Parsing	Path-based	Node-based	Control-flow
Scene Graph	Hierarchical graph	Spatial relationships	Graphics engines	Traversal-based	Tree-like	DAG variant
Decision Tree	Conditional graph	Rule-based paths	ML models	Path-based	Tree-based	Interpretable
Binary Decision Diagram	Reduced decision graph	Canonical form	Hardware verification	Path-based	Node-based	DAG optimized
Zero-suppressed BDD	Sparse BDD variant	Efficient zeros	Combinatorics	Path-based	Node-based	Set manipulation
And-Inverter Graph	Boolean circuit graph	AND + NOT nodes	Logic synthesis	Signal-based	Node-based	Hardware design