# Graph Algorithm Problems in LeetCodeAnimation: Complete BFS and DFS Coverage

> Explore LeetCode graph algorithm problems with animated BFS and DFS solutions. MisterBooo covers tree traversals, island detection, and more.

- Repository: [吴师兄学算法/LeetCodeAnimation](https://github.com/MisterBooo/LeetCodeAnimation)
- Tags: deep-dive
- Published: 2026-03-01

---

**The LeetCodeAnimation repository provides animated solutions to seven core LeetCode graph algorithm problems utilizing Breadth-First Search (BFS) and Depth-First Search (DFS), covering tree traversals, island detection, graph cloning, and string state exploration.**

The **MisterBooo/LeetCodeAnimation** repository is a curated collection of visual explanations for fundamental graph algorithm problems. Each markdown article pairs algorithmic theory with C++ implementations to demonstrate how BFS and DFS traversals solve complex interview questions. This guide examines every graph-related problem in the repository, detailing which traversal strategy each employs and where to find the source explanations.

## BFS Graph Algorithm Solutions

Breadth-First Search implementations in the repository focus on **level-order processing**, **shortest-path discovery in unweighted state spaces**, and **iterative graph exploration** using queues.

### Level Order Traversal (Problem 102)

In [`0102-Binary-Tree-Level-Order-Traversal/Article/0102-Binary-Tree-Level-Order-Traversal.md`](https://github.com/MisterBooo/LeetCodeAnimation/blob/main/0102-Binary-Tree-Level-Order-Traversal/Article/0102-Binary-Tree-Level-Order-Traversal.md), the solution demonstrates classic BFS on a binary tree. The algorithm uses a `queue` storing `pair<TreeNode*, int>` objects to track nodes and their depths, dequeuing in FIFO order to produce level-wise output.

```cpp
/// BFS
/// Time Complexity: O(n), Space Complexity: O(n)
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> res;
        if (!root) return res;
        queue<pair<TreeNode*,int>> q;
        q.push({root,0});

        while (!q.empty()){
            auto [node, lvl] = q.front(); q.pop();
            if (lvl == (int)res.size()) res.emplace_back();
            res[lvl].push_back(node->val);
            if (node->left)  q.push({node->left,  lvl+1});
            if (node->right) q.push({node->right, lvl+1});
        }
        return res;
    }
};

```

### Remove Invalid Parentheses (Problem 301)

The solution in `notes/LeetCode第301号问题：删除无效的括号.md` applies BFS to a string state graph. Starting from the original string, the algorithm generates all possible strings by removing one parenthesis per level, stopping at the first level that yields a valid expression—guaranteeing the minimum removal count.

### Clone Graph (Problem 133)

As documented in [`0133-Clone-Graph/Article/0133-Clone-Graph.md`](https://github.com/MisterBooo/LeetCodeAnimation/blob/main/0133-Clone-Graph/Article/0133-Clone-Graph.md), the BFS approach traverses the original graph using a queue while maintaining an `unordered_map<Node*, Node*>` to track cloned nodes. Each neighbor is cloned on first visit and enqueued for subsequent processing.

```cpp
Node* cloneGraph(Node* node){
    if (!node) return nullptr;
    unordered_map<Node*,Node*> mp;
    queue<Node*> q; q.push(node);
    mp[node] = new Node(node->val);
    while (!q.empty()){
        Node* cur = q.front(); q.pop();
        for (Node* nb : cur->neighbors){
            if (!mp.count(nb)){
                mp[nb] = new Node(nb->val);
                q.push(nb);
            }
            mp[cur]->neighbors.push_back(mp[nb]);
        }
    }
    return mp[node];
}

```

## DFS Graph Algorithm Solutions

Depth-First Search implementations emphasize **recursive traversal**, **flood-fill algorithms**, and **backtracking** for exploring all possible paths or connected components.

### Number of Islands (Problem 200)

The [`0200-Number-of-Islands/Article/0200-Number-of-Islands.md`](https://github.com/MisterBooo/LeetCodeAnimation/blob/main/0200-Number-of-Islands/Article/0200-Number-of-Islands.md) article implements a flood-fill DFS. Each unvisited `'1'` triggers a recursive exploration that marks the entire island by changing cell values to `'2'`, effectively counting connected components in a 2D grid.

```cpp
void dfs(vector<vector<char>>& grid, int r, int c){
    if (r<0 || r>=grid.size() || c<0 || c>=grid[0].size() || grid[r][c]!='1')
        return;
    grid[r][c] = '2';                     // mark visited
    dfs(grid, r-1, c); dfs(grid, r+1, c);
    dfs(grid, r, c-1); dfs(grid, r, c+1);
}
int numIslands(vector<vector<char>>& grid){
    int cnt = 0;
    for (int i=0;i<grid.size();++i)
        for (int j=0;j<grid[0].size();++j)
            if (grid[i][j]=='1'){ dfs(grid,i,j); ++cnt; }
    return cnt;
}

```

### Max Area of Island (Problem 695)

Found in [`0695-Max-Area-of-Island/Article/0695-Max-Area-of-Island.md`](https://github.com/MisterBooo/LeetCodeAnimation/blob/main/0695-Max-Area-of-Island/Article/0695-Max-Area-of-Island.md), this solution extends the flood-fill pattern to calculate island area. The DFS returns the size of each connected component, allowing the algorithm to track the maximum area encountered.

### Maximum Depth of Binary Tree (Problem 104)

The article at [`0104-Maximum-Depth-Of-Binary-Tree/Article/0104-Maximum-Depth-Of-Binary-Tree.md`](https://github.com/MisterBooo/LeetCodeAnimation/blob/main/0104-Maximum-Depth-Of-Binary-Tree/Article/0104-Maximum-Depth-Of-Binary-Tree.md) presents DFS as a post-order recursive traversal. The function computes depth by returning `1 + max(left_depth, right_depth)` for each node, traversing to leaf nodes before calculating height.

## Problems Supporting Both BFS and DFS

Several articles demonstrate both traversal strategies side-by-side, highlighting trade-offs between **iterative queue-based** and **recursive stack-based** approaches.

### Palindrome Partitioning (Problem 131)

In [`0131-Palindrome-Partitioning/Article/0131-Palindrome-Partitioning.md`](https://github.com/MisterBooo/LeetCodeAnimation/blob/main/0131-Palindrome-Partitioning/Article/0131-Palindrome-Partitioning.md), the repository illustrates both methods: **DFS** explores all partition possibilities recursively through backtracking, while **BFS** can build partitions level-by-level, offering alternative perspectives on the state space exploration.

### Clone Graph and Maximum Depth (Problems 133 and 104)

Both problems include dual-approach discussions. While the BFS implementations use explicit queues to avoid recursion depth limits, the DFS variants leverage the call stack for more concise code, as noted in [`0133-Clone-Graph/Article/0133-Clone-Graph.md`](https://github.com/MisterBooo/LeetCodeAnimation/blob/main/0133-Clone-Graph/Article/0133-Clone-Graph.md) and [`0104-Maximum-Depth-Of-Binary-Tree/Article/0104-Maximum-Depth-Of-Binary-Tree.md`](https://github.com/MisterBooo/LeetCodeAnimation/blob/main/0104-Maximum-Depth-Of-Binary-Tree/Article/0104-Maximum-Depth-Of-Binary-Tree.md).

## Summary

- **Seven graph algorithm problems** are covered: 102, 104, 131, 133, 200, 301, and 695
- **BFS-specific problems**: Level Order Traversal (102), Remove Invalid Parentheses (301), and Clone Graph (133) primarily demonstrate queue-based iteration
- **DFS-specific problems**: Number of Islands (200) and Max Area of Island (695) utilize recursive flood-fill; Maximum Depth (104) uses post-order recursion
- **Dual-approach demonstrations**: Palindrome Partitioning (131), Clone Graph (133), and Maximum Depth (104) explicitly compare both strategies
- **Animation framework**: All solutions utilize the `anima/` package ([`anima/base.py`](https://github.com/MisterBooo/LeetCodeAnimation/blob/main/anima/base.py), [`anima/create.py`](https://github.com/MisterBooo/LeetCodeAnimation/blob/main/anima/create.py), [`anima/model.py`](https://github.com/MisterBooo/LeetCodeAnimation/blob/main/anima/model.py)) to generate visual step-by-step traversals

## Frequently Asked Questions

### Which LeetCode graph problems in the repository use BFS exclusively?

**Problem 102 (Binary Tree Level Order Traversal)** and **Problem 301 (Remove Invalid Parentheses)** utilize BFS as their primary solution strategy. The level order traversal relies on a FIFO queue to process nodes by depth, while the parentheses removal treats each string modification as a level in an implicit state graph, guaranteeing minimal removals by stopping at the first valid level.

### How does the repository visualize DFS recursion and BFS queues?

According to the source code structure, the `anima/` directory contains the animation engine ([`anima/base.py`](https://github.com/MisterBooo/LeetCodeAnimation/blob/main/anima/base.py), [`anima/create.py`](https://github.com/MisterBooo/LeetCodeAnimation/blob/main/anima/create.py), [`anima/model.py`](https://github.com/MisterBooo/LeetCodeAnimation/blob/main/anima/model.py)) which generates visual steps for both traversals. For BFS, it visualizes queue operations and node visits by level; for DFS, it illustrates recursion unwinding, stack depth changes, and visited node marking—particularly evident in the island-flood-fill animations.

### Are the implementations language-specific or abstract pseudocode?

While the repository stores concrete **C++ implementations** for all solutions, each markdown article (such as [`0102-Binary-Tree-Level-Order-Traversal/Article/0102-Binary-Tree-Level-Order-Traversal.md`](https://github.com/MisterBooo/LeetCodeAnimation/blob/main/0102-Binary-Tree-Level-Order-Traversal/Article/0102-Binary-Tree-Level-Order-Traversal.md)) abstracts the algorithm with language-neutral descriptions before presenting the code. This dual-format approach ensures readers understand the graph theory independently of syntax.

### What distinguishes the BFS and DFS approaches for cloning a graph in Problem 133?

The **BFS approach** in [`0133-Clone-Graph/Article/0133-Clone-Graph.md`](https://github.com/MisterBooo/LeetCodeAnimation/blob/main/0133-Clone-Graph/Article/0133-Clone-Graph.md) uses an explicit `queue` and an `unordered_map` to iteratively clone nodes, avoiding stack overflow on deep graphs. The **DFS approach** uses the call stack to recursively visit neighbors, resulting in more compact code but potentially hitting recursion depth limits on large connected components—trade-offs explicitly discussed in the article.