Graph
গ্রাফ
`G = (V, E)` — কিছু vertex আর তাদের মধ্যে কিছু edge। Network, dependency, control flow, filesystem, git history — সবই graph।
also: digraph, directed graph
Undirected graph = symmetric [[relation]]। Directed graph = যেকোনো relation। DAG = irreflexive + antisymmetric + acyclic।
Handshake lemma: Σ deg(v) = 2|E|, তাই বিজোড় degree-র
vertex সংখ্যা সবসময় জোড় — একটা সস্তা config sanity check।
Representation — trade-off বাস্তব:
| Operation | Matrix | List |
|---|---|---|
has_edge | O(1) | O(deg) |
| প্রতিবেশী ঘোরা | O(n) | O(deg) |
| BFS/DFS | O(n²) | O(n+m) |
| Memory | O(n²) | O(n+m) |
১০ লক্ষ user, গড়ে ২০০ বন্ধু: matrix ১২৫ GB, list ১.৬ GB। বাস্তব graph প্রায় সবসময় sparse, তাই list প্রায় সবসময় সঠিক। Static graph-এ CSR আরো ভালো — একই memory, অনেক ভালো cache locality।
BFS আর DFS একই algorithm — শুধু queue বনাম stack। BFS unweighted shortest path দেয়, DFS দেয় না।
Mᵏ-এর (i,j) ঘর = i থেকে j-তে ঠিক k দৈর্ঘ্যের
walk-এর সংখ্যা। Semiring বদলালে একই operation reachability,
shortest path বা probability দেয়।