Part VI · Graph Algorithms and Tree-Graph Techniques
32. Graph Theory Basics and Representations
6 lessons•39 topics•Intermediate / Advanced
6 of 6 lessons published
32.0110 animated
Graph vocabulary
- Vertices
- Edges
- Degree
- In-degree/out-degree
- Paths
- Walks
- Trails
- Cycles
- Components
- Connectedness
32.028 animated
Graph taxonomy
- Directed/undirected
- Weighted/unweighted
- Simple/multigraph
- DAG
- Tree
- Bipartite
- Complete
- Sparse/dense
32.034 animated
Representations
- Adjacency matrix
- Adjacency list
- Edge list
- Incidence matrix
- Compressed sparse row (CSR)
32.046 animated
Graph construction
- 0-based/1-based indexing
- Duplicate edges
- Self-loops
- Weights
- Disconnected graphs
- Reversing edges
32.055 animated
Core graph properties
- Handshaking lemma
- Trees with n-1 edges
- Sum degrees
- Directed edge counts
- Graph complement
32.06Lesson
Choosing representation
- Time/memory complexity
- Edge lookup
- Iteration cost
- Dense vs sparse
- Java nested collection overhead