# Example Gallery

This gallery showcases various animations for popular algorithms, created using the manim_dsa plugin. Each example is accompanied by code snippets and a brief explanation to help you understand how the algorithms are visualized and how to implement them in your own scenes.

## Bubble Sort

Bubble Sort is a simple sorting algorithm that repeatedly steps through the list to be sorted, compares adjacent elements, and swaps them if they are in the wrong order. The process continues until the list is completely sorted.

Below is an animated visualization of Bubble Sort, where the comparison and swapping of elements are highlighted to make it easier to understand the sorting process. The animation also marks the sorted elements to clearly indicate progress.

<div id="bubblesort" class="admonition admonition-manim-example">
<p class="admonition-title">Example: BubbleSort <a class="headerlink" href="#bubblesort">¶</a></p><video
    class="manim-video"
    controls
    loop
    autoplay
    src="./BubbleSort-1.mp4">
</video>
```python
from manim import *

from manim_dsa import *

class BubbleSort(Scene):
    def bubblesort(self, arr):
        mArray = (
            MArray(arr, style=MArrayStyle.BLUE)
            .add_indexes()
        )
        self.play(Create(mArray))
        for i in range(len(arr)):
            for j in range(0, len(arr) - i - 1):
                # Highlight the elements being compared
                self.play(
                    mArray[j].animate.highlight(),
                    mArray[j+1].animate.highlight()
                )
                # Unhighlight after comparison
                self.play(
                    mArray[j].animate.unhighlight(),
                    mArray[j+1].animate.unhighlight()
                )
                # Swap if necessary
                if arr[j] > arr[j + 1]:
                    self.play(mArray.animate.swap(j, j+1))
                    arr[j], arr[j+1] = arr[j+1], arr[j]
            # Mark sorted element
            self.play(mArray[len(arr) - i - 1].square.animate.set_fill(GREEN))

    def construct(self):
        arr = [39, 85, 10, 2, 18]
        title = Text("Bubble Sort", font="Cascadia Code").scale(1.5).to_edge(UP)
        self.play(Create(title))
        self.bubblesort(arr)
```

<pre data-manim-binder data-manim-classname="BubbleSort">
from manim_dsa import \*

class BubbleSort(Scene):
    def bubblesort(self, arr):
        mArray = (
            MArray(arr, style=MArrayStyle.BLUE)
            .add_indexes()
        )
        self.play(Create(mArray))
        for i in range(len(arr)):
            for j in range(0, len(arr) - i - 1):
                # Highlight the elements being compared
                self.play(
                    mArray[j].animate.highlight(),
                    mArray[j+1].animate.highlight()
                )
                # Unhighlight after comparison
                self.play(
                    mArray[j].animate.unhighlight(),
                    mArray[j+1].animate.unhighlight()
                )
                # Swap if necessary
                if arr[j] > arr[j + 1]:
                    self.play(mArray.animate.swap(j, j+1))
                    arr[j], arr[j+1] = arr[j+1], arr[j]
            # Mark sorted element
            self.play(mArray[len(arr) - i - 1].square.animate.set_fill(GREEN))

    def construct(self):
        arr = [39, 85, 10, 2, 18]
        title = Text("Bubble Sort", font="Cascadia Code").scale(1.5).to_edge(UP)
        self.play(Create(title))
        self.bubblesort(arr)

</pre></div>

## Depth-First Search in a graph

Depth-First Search (DFS) is a graph traversal algorithm that starts at a source node and explores as far as possible along each branch before backtracking. DFS can be implemented using recursion or an explicit stack.
The following animations demonstrate both an iterative implementation of DFS using an explicit stack and a recursive implementation.

<div id="iterativedfs" class="admonition admonition-manim-example">
<p class="admonition-title">Example: IterativeDfs <a class="headerlink" href="#iterativedfs">¶</a></p><video
    class="manim-video"
    controls
    loop
    autoplay
    src="./IterativeDfs-1.mp4">
</video>
```python
from manim import *

from manim_dsa import *

class IterativeDfs(Scene):
    def dfs(self, graph, start):
        mGraph = (
            MGraph(graph, style=MGraphStyle.PURPLE)
            .scale(0.7).node_layout().to_edge(LEFT).shift(DR)
        )
        mStack = (
            MStack(style=MStackStyle.BLUE)
            .scale(0.7).to_edge(RIGHT).shift(DL)
        )
        self.play(Create(mGraph))
        self.play(Create(mStack))
        visited = {}
        stack = [start]
        prevList = [None]
        self.play(mStack.animate.append(start))
        for node in graph:
            visited[node] = False
        while stack:
            node = stack.pop()
            self.play(mStack.animate.pop())
            prev = prevList.pop()
            if prev and not visited[node]:
                self.play(mGraph[(prev, node)].animate.highlight())
            if not visited[node]:
                self.play(mGraph[node].animate.highlight())
            visited[node] = True
            for neighbor in graph[node]:
                if not visited[neighbor]:
                    stack.append(neighbor)
                    self.play(mStack.animate.append(neighbor))
                    prevList.append(node)

    def construct(self):
        graph = {
            '0': ['1', '2'], '1': ['0', '2', '3', '4'], '2': ['0', '1'],
            '3': ['1', '5'], '4': ['1'], '5': ['3', '6', '7', '8'], '6': ['5'],
            '7': ['5', '8'], '8': ['5', '7', '9'], '9': ['8']
        }
        start = '0'
        title = Text("Depth-First Search in a graph", font="Cascadia Code").to_edge(UP)
        self.play(Create(title))
        self.dfs(graph, start)
        self.wait()
```

<pre data-manim-binder data-manim-classname="IterativeDfs">
from manim_dsa import \*

class IterativeDfs(Scene):
    def dfs(self, graph, start):
        mGraph = (
            MGraph(graph, style=MGraphStyle.PURPLE)
            .scale(0.7).node_layout().to_edge(LEFT).shift(DR)
        )
        mStack = (
            MStack(style=MStackStyle.BLUE)
            .scale(0.7).to_edge(RIGHT).shift(DL)
        )
        self.play(Create(mGraph))
        self.play(Create(mStack))
        visited = {}
        stack = [start]
        prevList = [None]
        self.play(mStack.animate.append(start))
        for node in graph:
            visited[node] = False
        while stack:
            node = stack.pop()
            self.play(mStack.animate.pop())
            prev = prevList.pop()
            if prev and not visited[node]:
                self.play(mGraph[(prev, node)].animate.highlight())
            if not visited[node]:
                self.play(mGraph[node].animate.highlight())
            visited[node] = True
            for neighbor in graph[node]:
                if not visited[neighbor]:
                    stack.append(neighbor)
                    self.play(mStack.animate.append(neighbor))
                    prevList.append(node)

    def construct(self):
        graph = {
            '0': ['1', '2'], '1': ['0', '2', '3', '4'], '2': ['0', '1'],
            '3': ['1', '5'], '4': ['1'], '5': ['3', '6', '7', '8'], '6': ['5'],
            '7': ['5', '8'], '8': ['5', '7', '9'], '9': ['8']
        }
        start = '0'
        title = Text("Depth-First Search in a graph", font="Cascadia Code").to_edge(UP)
        self.play(Create(title))
        self.dfs(graph, start)
        self.wait()

</pre></div><div id="recursivedfs" class="admonition admonition-manim-example">
<p class="admonition-title">Example: RecursiveDfs <a class="headerlink" href="#recursivedfs">¶</a></p><video
    class="manim-video"
    controls
    loop
    autoplay
    src="./RecursiveDfs-1.mp4">
</video>
```python
from manim import *

from manim_dsa import *

class RecursiveDfs(Scene):
    def dfs_helper(self, graph, mGraph, visited, prev, root):
        visited[root] = True
        self.play(mGraph[root].animate.highlight())
        for adj in graph[root]:
            if(not visited[adj]):
                self.play(mGraph[(root, adj)].animate.highlight())
                self.dfs_helper(graph, mGraph, visited, prev, adj)
                self.play(mGraph[(root, adj)].animate.unhighlight())
        self.play(mGraph[root].animate.unhighlight())

    def dfs(self, graph, mGraph):
        visited = {}

        for node in graph:
            visited[node] = False

        for node in graph:
            if(not visited[node]):
                self.dfs_helper(graph, mGraph, visited, None, node)

    def construct(self):
        graph = {
            '0': ['1', '2'],
            '1': ['0', '2', '3', '4'],
            '2': ['0', '1'],
            '3': ['1', '5'],
            '4': ['1'],
            '5': ['3', '6', '7', '8'],
            '6': ['5'],
            '7': ['5', '8'],
            '8': ['5', '7', '9'],
            '9': ['8']
        }

        nodes_and_positions = {
            '0': LEFT * 6,
            '1': LEFT * 4 + UP,
            '2': LEFT * 4 + DOWN,
            '3': LEFT * 2,
            '4': LEFT * 2 + UP * 2,
            '5': ORIGIN,
            '6': LEFT * 2 + DOWN * 2,
            '7': RIGHT * 2 + DOWN * 2,
            '8': RIGHT * 2 + UP * 2,
            '9': RIGHT * 4 + UP * 2,
        }

        mGraph = MGraph(graph, nodes_and_positions, style=MGraphStyle.BLUE).move_to(ORIGIN).shift(DOWN/2)

        title = Text("Depth-First Search in a graph", font="Cascadia Code").to_edge(UP)

        self.play(Create(title))
        self.play(Create(mGraph))

        self.dfs(graph, mGraph)
        self.wait()
```

<pre data-manim-binder data-manim-classname="RecursiveDfs">
from manim_dsa import \*

class RecursiveDfs(Scene):
    def dfs_helper(self, graph, mGraph, visited, prev, root):
        visited[root] = True
        self.play(mGraph[root].animate.highlight())
        for adj in graph[root]:
            if(not visited[adj]):
                self.play(mGraph[(root, adj)].animate.highlight())
                self.dfs_helper(graph, mGraph, visited, prev, adj)
                self.play(mGraph[(root, adj)].animate.unhighlight())
        self.play(mGraph[root].animate.unhighlight())

    def dfs(self, graph, mGraph):
        visited = {}

        for node in graph:
            visited[node] = False

        for node in graph:
            if(not visited[node]):
                self.dfs_helper(graph, mGraph, visited, None, node)

    def construct(self):
        graph = {
            '0': ['1', '2'],
            '1': ['0', '2', '3', '4'],
            '2': ['0', '1'],
            '3': ['1', '5'],
            '4': ['1'],
            '5': ['3', '6', '7', '8'],
            '6': ['5'],
            '7': ['5', '8'],
            '8': ['5', '7', '9'],
            '9': ['8']
        }

        nodes_and_positions = {
            '0': LEFT \* 6,
            '1': LEFT \* 4 + UP,
            '2': LEFT \* 4 + DOWN,
            '3': LEFT \* 2,
            '4': LEFT \* 2 + UP \* 2,
            '5': ORIGIN,
            '6': LEFT \* 2 + DOWN \* 2,
            '7': RIGHT \* 2 + DOWN \* 2,
            '8': RIGHT \* 2 + UP \* 2,
            '9': RIGHT \* 4 + UP \* 2,
        }

        mGraph = MGraph(graph, nodes_and_positions, style=MGraphStyle.BLUE).move_to(ORIGIN).shift(DOWN/2)

        title = Text("Depth-First Search in a graph", font="Cascadia Code").to_edge(UP)

        self.play(Create(title))
        self.play(Create(mGraph))

        self.dfs(graph, mGraph)
        self.wait()

</pre></div>

## Prim’s Algorithm for Minimum Spanning Tree in a graph

Prim’s Algorithm is a greedy algorithm that finds a minimum spanning tree for a weighted undirected graph. The algorithm starts with an arbitrary node and grows the tree by adding the minimum weight edge that connects the tree to a new node. The process continues until all nodes are included in the tree.

In the animation below, green edges represent the edges that are part of the minimum spanning tree, blue edges indicate the edges currently being considered in the iteration, and red edges denote the edges that are not part of the minimum spanning tree. In the end, the total weight of the minimum spanning tree is displayed.

<div id="prim" class="admonition admonition-manim-example">
<p class="admonition-title">Example: Prim <a class="headerlink" href="#prim">¶</a></p><video
    class="manim-video"
    controls
    loop
    autoplay
    src="./Prim-1.mp4">
</video>
```python
from manim import *

from manim_dsa import *
import heapq

class Prim(Scene):
    def prim(self, graph, nodes_and_positions, start):
        pq = []
        visited = {}

        mGraph = MGraph(graph, nodes_and_positions, style=MGraphStyle.PURPLE).move_to(ORIGIN)
        self.play(Create(mGraph))

        for node in graph:
            visited[node] = False

        res = 0

        heapq.heappush(pq, (0, None, start))

        while pq:
            wt, prev_node, u = heapq.heappop(pq)
            if visited[u]:
                self.play(mGraph[(prev_node, u)].animate.highlight(RED))
                continue

            visited[u] = True
            res += wt

            if prev_node is not None:
                self.play(mGraph[(prev_node, u)].animate.highlight(GREEN))

            self.play(mGraph[u].animate.highlight(GREEN))

            for adj in graph[u]:
                v, weight = adj
                if not visited[v]:
                    heapq.heappush(pq, (weight, u, v))
                    self.play(mGraph[(u, v)].animate.highlight(BLUE))

        return res

    def construct(self):
        graph = {
            '0': [('1', 2), ('2', 4)],
            '1': [('0', 2), ('2', 1), ('3', 5), ('4', 5)],
            '2': [('0', 4), ('1', 1)],
            '3': [('1', 5), ('5', 2)],
            '4': [('1', 5)],
            '5': [('3', 2), ('6', 7), ('7', 2), ('8', 1)],
            '6': [('5', 7)],
            '7': [('5', 2), ('8', 6)],
            '8': [('5', 1), ('7', 6), ('9', 3)],
            '9': [('8', 3)]
        }

        nodes_and_positions = {
            '0': LEFT * 6,
            '1': LEFT * 4 + UP,
            '2': LEFT * 4 + DOWN,
            '3': LEFT * 2,
            '4': LEFT * 2 + UP * 2,
            '5': ORIGIN,
            '6': LEFT * 2 + DOWN * 2,
            '7': RIGHT * 2 + DOWN * 2,
            '8': RIGHT * 2 + UP * 2,
            '9': RIGHT * 4 + UP * 2,
        }

        title = (
            Text("Prim's Algorithm for Minimum Spanning Tree", font="Cascadia Code")
            .scale(0.7).to_edge(UP)
        )
        self.play(Create(title))

        total_weight = self.prim(graph, nodes_and_positions, '0')

        text = (
            Text("Total: " + str(total_weight), font="Cascadia Code")
            .to_edge(DOWN)
        )
        self.play(Create(text))
        self.wait()
```

<pre data-manim-binder data-manim-classname="Prim">
from manim_dsa import \*
import heapq

class Prim(Scene):
    def prim(self, graph, nodes_and_positions, start):
        pq = []
        visited = {}

        mGraph = MGraph(graph, nodes_and_positions, style=MGraphStyle.PURPLE).move_to(ORIGIN)
        self.play(Create(mGraph))

        for node in graph:
            visited[node] = False

        res = 0

        heapq.heappush(pq, (0, None, start))

        while pq:
            wt, prev_node, u = heapq.heappop(pq)
            if visited[u]:
                self.play(mGraph[(prev_node, u)].animate.highlight(RED))
                continue

            visited[u] = True
            res += wt

            if prev_node is not None:
                self.play(mGraph[(prev_node, u)].animate.highlight(GREEN))

            self.play(mGraph[u].animate.highlight(GREEN))

            for adj in graph[u]:
                v, weight = adj
                if not visited[v]:
                    heapq.heappush(pq, (weight, u, v))
                    self.play(mGraph[(u, v)].animate.highlight(BLUE))

        return res

    def construct(self):
        graph = {
            '0': [('1', 2), ('2', 4)],
            '1': [('0', 2), ('2', 1), ('3', 5), ('4', 5)],
            '2': [('0', 4), ('1', 1)],
            '3': [('1', 5), ('5', 2)],
            '4': [('1', 5)],
            '5': [('3', 2), ('6', 7), ('7', 2), ('8', 1)],
            '6': [('5', 7)],
            '7': [('5', 2), ('8', 6)],
            '8': [('5', 1), ('7', 6), ('9', 3)],
            '9': [('8', 3)]
        }

        nodes_and_positions = {
            '0': LEFT \* 6,
            '1': LEFT \* 4 + UP,
            '2': LEFT \* 4 + DOWN,
            '3': LEFT \* 2,
            '4': LEFT \* 2 + UP \* 2,
            '5': ORIGIN,
            '6': LEFT \* 2 + DOWN \* 2,
            '7': RIGHT \* 2 + DOWN \* 2,
            '8': RIGHT \* 2 + UP \* 2,
            '9': RIGHT \* 4 + UP \* 2,
        }

        title = (
            Text("Prim's Algorithm for Minimum Spanning Tree", font="Cascadia Code")
            .scale(0.7).to_edge(UP)
        )
        self.play(Create(title))

        total_weight = self.prim(graph, nodes_and_positions, '0')

        text = (
            Text("Total: " + str(total_weight), font="Cascadia Code")
            .to_edge(DOWN)
        )
        self.play(Create(text))
        self.wait()

</pre></div>

## Kruskal’s Algorithm for Minimum Spanning Tree in a graph

Kruskal’s Algorithm is a greedy algorithm that finds a minimum spanning tree for a weighted undirected graph. The algorithm starts with an empty tree and adds the minimum weight edge that does not form a cycle in the tree. The process continues until all nodes are included in the tree.

In the animation below, green edges represent the edges that are part of the minimum spanning tree and red edges denote the edges that are not part of the minimum spanning tree. In the end, the total weight of the minimum spanning tree is displayed.

<div id="kruskal" class="admonition admonition-manim-example">
<p class="admonition-title">Example: Kruskal <a class="headerlink" href="#kruskal">¶</a></p><video
    class="manim-video"
    controls
    loop
    autoplay
    src="./Kruskal-1.mp4">
</video>
```python
from manim import *

from manim_dsa import *
import heapq

class Kruskal(Scene):
    def find(self, parent, i):
        if parent[i] == i:
            return i
        return self.find(parent, parent[i])

    def union(self, parent, rank, x, y):
        xroot = self.find(parent, x)
        yroot = self.find(parent, y)
        if rank[xroot] < rank[yroot]:
            parent[xroot] = yroot
        elif rank[xroot] > rank[yroot]:
            parent[yroot] = xroot
        else:
            parent[yroot] = xroot
            rank[xroot] += 1

    def kruskal(self, graph, nodes_and_positions):
        mGraph = MGraph(graph, nodes_and_positions, style=MGraphStyle.PURPLE).move_to(ORIGIN)
        self.play(Create(mGraph))

        edges = []
        for u in graph:
            for v, weight in graph[u]:
                if (weight, u, v) not in edges and (weight, v, u) not in edges:
                    edges.append((weight, u, v))
        edges.sort()

        parent = {}
        rank = {}

        for node in graph:
            parent[node] = node
            rank[node] = 0

        mst_weight = 0

        for edge in edges:
            wt, u, v = edge
            x = self.find(parent, u)
            y = self.find(parent, v)
            if x != y:
                self.play(mGraph[(u, v)].animate.highlight(GREEN, 12))
                mst_weight += wt
                self.union(parent, rank, x, y)
            else:
                self.play(mGraph[(u, v)].animate.highlight(RED, 12))

        return mst_weight


    def construct(self):
        graph = {
            '0': [('1', 2), ('2', 4)],
            '1': [('0', 2), ('2', 1), ('3', 5), ('4', 5)],
            '2': [('0', 4), ('1', 1)],
            '3': [('1', 5), ('5', 2)],
            '4': [('1', 5)],
            '5': [('3', 2), ('6', 7), ('7', 2), ('8', 1)],
            '6': [('5', 7)],
            '7': [('5', 2), ('8', 6)],
            '8': [('5', 1), ('7', 6), ('9', 3)],
            '9': [('8', 3)]
        }

        nodes_and_positions = {
            '0': LEFT * 6,
            '1': LEFT * 4 + UP * 2,
            '2': LEFT * 4 + DOWN * 2,
            '3': LEFT * 2,
            '4': LEFT * 2 + UP * 2,
            '5': ORIGIN + RIGHT,
            '6': LEFT + DOWN * 2,
            '7': RIGHT * 3 + DOWN * 2,
            '8': RIGHT * 3 + UP * 2,
            '9': RIGHT * 5 + UP * 2,
        }

        title = Text("Kruskal’s Algorithm for Minimum Spanning Tree", font="Cascadia Code").scale(0.7).to_edge(UP)
        self.play(Create(title))
        total_weight = self.kruskal(graph, nodes_and_positions)
        text = Text("Total: " + str(total_weight), font="Cascadia Code").to_edge(DOWN)
        self.play(Create(text))
        self.wait()
```

<pre data-manim-binder data-manim-classname="Kruskal">
from manim_dsa import \*
import heapq

class Kruskal(Scene):
    def find(self, parent, i):
        if parent[i] == i:
            return i
        return self.find(parent, parent[i])

    def union(self, parent, rank, x, y):
        xroot = self.find(parent, x)
        yroot = self.find(parent, y)
        if rank[xroot] < rank[yroot]:
            parent[xroot] = yroot
        elif rank[xroot] > rank[yroot]:
            parent[yroot] = xroot
        else:
            parent[yroot] = xroot
            rank[xroot] += 1

    def kruskal(self, graph, nodes_and_positions):
        mGraph = MGraph(graph, nodes_and_positions, style=MGraphStyle.PURPLE).move_to(ORIGIN)
        self.play(Create(mGraph))

        edges = []
        for u in graph:
            for v, weight in graph[u]:
                if (weight, u, v) not in edges and (weight, v, u) not in edges:
                    edges.append((weight, u, v))
        edges.sort()

        parent = {}
        rank = {}

        for node in graph:
            parent[node] = node
            rank[node] = 0

        mst_weight = 0

        for edge in edges:
            wt, u, v = edge
            x = self.find(parent, u)
            y = self.find(parent, v)
            if x != y:
                self.play(mGraph[(u, v)].animate.highlight(GREEN, 12))
                mst_weight += wt
                self.union(parent, rank, x, y)
            else:
                self.play(mGraph[(u, v)].animate.highlight(RED, 12))

        return mst_weight


    def construct(self):
        graph = {
            '0': [('1', 2), ('2', 4)],
            '1': [('0', 2), ('2', 1), ('3', 5), ('4', 5)],
            '2': [('0', 4), ('1', 1)],
            '3': [('1', 5), ('5', 2)],
            '4': [('1', 5)],
            '5': [('3', 2), ('6', 7), ('7', 2), ('8', 1)],
            '6': [('5', 7)],
            '7': [('5', 2), ('8', 6)],
            '8': [('5', 1), ('7', 6), ('9', 3)],
            '9': [('8', 3)]
        }

        nodes_and_positions = {
            '0': LEFT \* 6,
            '1': LEFT \* 4 + UP \* 2,
            '2': LEFT \* 4 + DOWN \* 2,
            '3': LEFT \* 2,
            '4': LEFT \* 2 + UP \* 2,
            '5': ORIGIN + RIGHT,
            '6': LEFT + DOWN \* 2,
            '7': RIGHT \* 3 + DOWN \* 2,
            '8': RIGHT \* 3 + UP \* 2,
            '9': RIGHT \* 5 + UP \* 2,
        }

        title = Text("Kruskal’s Algorithm for Minimum Spanning Tree", font="Cascadia Code").scale(0.7).to_edge(UP)
        self.play(Create(title))
        total_weight = self.kruskal(graph, nodes_and_positions)
        text = Text("Total: " + str(total_weight), font="Cascadia Code").to_edge(DOWN)
        self.play(Create(text))
        self.wait()

</pre></div>