{
    "nbformat": 4,
    "nbformat_minor": 5,
    "metadata": {
        "kernelspec": {
            "display_name": "Python",
            "language": "python",
            "name": "python"
        },
        "language_info": {
            "name": "python"
        }
    },
    "cells": [
        {
            "id": "1323f141",
            "cell_type": "markdown",
            "source": "<div class='alert alert-warning'>\n\nSciPy's interactive examples with Jupyterlite are experimental and may not always work as expected. Execution of cells containing imports may result in large downloads (up to 60MB of content for the first import from SciPy). Load times when importing from SciPy may take roughly 10-20 seconds. If you notice any problems, feel free to open an [issue](https://github.com/scipy/scipy/issues/new/choose).\n\n</div>",
            "metadata": {}
        },
        {
            "id": "7b9a910c",
            "cell_type": "markdown",
            "source": "The following example shows the computation of a depth-first tree\nover a simple four-component graph, starting at node 0\n```\n\ninput graph          breadth first tree from (0)\n\n(0)                         (0)\n/   \\                       /   \\\n3     8                     3     8\n/       \\                   /       \\\n(3)---5---(1)               (3)       (1)\n\\       /                           /\n6     2                           2\n\\   /                           /\n(2)                         (2)\n\n```\nIn compressed sparse representation, the solution looks like this:\n",
            "metadata": {}
        },
        {
            "id": "1a6efa83",
            "cell_type": "code",
            "metadata": {},
            "execution_count": null,
            "source": "from scipy.sparse import csr_array\nfrom scipy.sparse.csgraph import breadth_first_tree\nX = csr_array([[0, 8, 0, 3],\n               [0, 0, 2, 5],\n               [0, 0, 0, 6],\n               [0, 0, 0, 0]])\nTcsr = breadth_first_tree(X, 0, directed=False)\nTcsr.toarray().astype(int)",
            "outputs": [
                {
                    "output_type": "execute_result",
                    "metadata": {},
                    "data": {
                        "text/plain": "array([[0, 8, 0, 3],\n       [0, 0, 2, 0],\n       [0, 0, 0, 0],\n       [0, 0, 0, 0]])"
                    },
                    "execution_count": null
                }
            ]
        },
        {
            "id": "b001c677",
            "cell_type": "markdown",
            "source": "Note that the resulting graph is a Directed Acyclic Graph which spans\nthe graph.  A breadth-first tree from a given node is unique.",
            "metadata": {}
        }
    ]
}