From 0c74c26085737f273fcfd86a8a0792b851e92c85 Mon Sep 17 00:00:00 2001 From: mo khan Date: Sat, 26 Sep 2020 13:15:39 -0600 Subject: docs: add visualization of dfs --- src/03/05/README.md | 223 ++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 223 insertions(+) diff --git a/src/03/05/README.md b/src/03/05/README.md index 1525a42..8251e9f 100644 --- a/src/03/05/README.md +++ b/src/03/05/README.md @@ -19,3 +19,226 @@ Given the graph shown below, answer the following questions: | \ |/ | (m) \(n)---(o)---(p) ``` + +# Depth First Traversal + +Order: g, h, o, p, l, k, n, i, m, j, f, c, d, b, a, e + +```plaintext + +1. [g] + +(a)---(b)---(c)---(d) + | \ / / + | \ / / +(e) \(f)/ (*)/--(h) + | | / | / + | | / | / +(i)---(j)/ (k) / (l) + | \ | / | + | \ |/ | +(m) \(n)---(o)---(p) + +2. [g, h] + +(a)---(b)---(c)---(d) + | \ / / + | \ / / +(e) \(f)/ (*)/--(*) + | | / | / + | | / | / +(i)---(j)/ (k) / (l) + | \ | / | + | \ |/ | +(m) \(n)---(o)---(p) + +3. [g, h, o] + +(a)---(b)---(c)---(d) + | \ / / + | \ / / +(e) \(f)/ (*)/--(*) + | | / | / + | | / | / +(i)---(j)/ (k) / (l) + | \ | / | + | \ |/ | +(m) \(n)---(*)---(p) + +4. [g, h, o, p] + +(a)---(b)---(c)---(d) + | \ / / + | \ / / +(e) \(f)/ (*)/--(*) + | | / | / + | | / | / +(i)---(j)/ (k) / (l) + | \ | / | + | \ |/ | +(m) \(n)---(*)---(*) + +5. [g, h, o, p, l] + +(a)---(b)---(c)---(d) + | \ / / + | \ / / +(e) \(f)/ (*)/--(*) + | | / | / + | | / | / +(i)---(j)/ (k) / (*) + | \ | / | + | \ |/ | +(m) \(n)---(*)---(*) + +6. [g, h, o, p, l, k] + +(a)---(b)---(c)---(d) + | \ / / + | \ / / +(e) \(f)/ (*)/--(*) + | | / | / + | | / | / +(i)---(j)/ (*) / (*) + | \ | / | + | \ |/ | +(m) \(n)---(*)---(*) + +7. [g, h, o, p, l, k, n] + +(a)---(b)---(c)---(d) + | \ / / + | \ / / +(e) \(f)/ (*)/--(*) + | | / | / + | | / | / +(i)---(j)/ (*) / (*) + | \ | / | + | \ |/ | +(m) \(*)---(*)---(*) + +8. [g, h, o, p, l, k, n, i] + +(a)---(b)---(c)---(d) + | \ / / + | \ / / +(e) \(f)/ (*)/--(*) + | | / | / + | | / | / +(*)---(j)/ (*) / (*) + | \ | / | + | \ |/ | +(m) \(*)---(*)---(*) + +9. [g, h, o, p, l, k, n, i, m] + +(a)---(b)---(c)---(d) + | \ / / + | \ / / +(e) \(f)/ (*)/--(*) + | | / | / + | | / | / +(*)---(j)/ (*) / (*) + | \ | / | + | \ |/ | +(*) \(*)---(*)---(*) + +10. [g, h, o, p, l, k, n, i, m, j] + +(a)---(b)---(c)---(d) + | \ / / + | \ / / +(e) \(f)/ (*)/--(*) + | | / | / + | | / | / +(*)---(*)/ (*) / (*) + | \ | / | + | \ |/ | +(*) \(*)---(*)---(*) + +11. [g, h, o, p, l, k, n, i, m, j, f] + +(a)---(b)---(c)---(d) + | \ / / + | \ / / +(e) \(*)/ (*)/--(*) + | | / | / + | | / | / +(*)---(*)/ (*) / (*) + | \ | / | + | \ |/ | +(*) \(*)---(*)---(*) + +12. [g, h, o, p, l, k, n, i, m, j, f, c] + +(a)---(b)---(*)---(d) + | \ / / + | \ / / +(e) \(*)/ (*)/--(*) + | | / | / + | | / | / +(*)---(*)/ (*) / (*) + | \ | / | + | \ |/ | +(*) \(*)---(*)---(*) + +13. [g, h, o, p, l, k, n, i, m, j, f, c, d] + +(a)---(b)---(*)---(*) + | \ / / + | \ / / +(e) \(*)/ (*)/--(*) + | | / | / + | | / | / +(*)---(*)/ (*) / (*) + | \ | / | + | \ |/ | +(*) \(*)---(*)---(*) + +14. [g, h, o, p, l, k, n, i, m, j, f, c, d, b] + +(a)---(*)---(*)---(*) + | \ / / + | \ / / +(e) \(*)/ (*)/--(*) + | | / | / + | | / | / +(*)---(*)/ (*) / (*) + | \ | / | + | \ |/ | +(*) \(*)---(*)---(*) + +15. [g, h, o, p, l, k, n, i, m, j, f, c, d, b, a] + +(*)---(*)---(*)---(*) + | \ / / + | \ / / +(e) \(*)/ (*)/--(*) + | | / | / + | | / | / +(*)---(*)/ (*) / (*) + | \ | / | + | \ |/ | +(*) \(*)---(*)---(*) + +16. [g, h, o, p, l, k, n, i, m, j, f, c, d, b, a, e] + +(*)---(*)---(*)---(*) + | \ / / + | \ / / +(*) \(*)/ (*)/--(*) + | | / | / + | | / | / +(*)---(*)/ (*) / (*) + | \ | / | + | \ |/ | +(*) \(*)---(*)---(*) +``` + +# Breadth First Traversal + +# Adjacency List + +# Adjacency Matrix + +# Traverse Every Edge -- cgit v1.2.3