Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
BFS implements using Python
{
"cells": [
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"class Node:\n",
" \n",
" def __init__(self, name):\n",
" self.name = name\n",
" self.visited = False\n",
" self.neighbors = []\n",
" \n",
" def __repr__(self):\n",
" return 'Node(name={})'.format(self.name)"
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {},
"outputs": [],
"source": [
"class BFS:\n",
" \"\"\"\n",
" For BFS, use queue; For DFS, use stack or recursion\n",
" \"\"\"\n",
" def __init__(self, start):\n",
" self.queue = []\n",
" self.start = start\n",
" \n",
" def traversal(self):\n",
" self.start.visited = True\n",
" self.queue.append(self.start)\n",
" \n",
" while self.queue:\n",
" \n",
" node = self.queue.pop(0)\n",
" yield node\n",
" \n",
" for n in node.neighbors:\n",
" if not n.visited:\n",
" n.visited = True\n",
" self.queue.append(n) "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"![image](https://storage.googleapis.com/ssivart/super9-blog/level-order-traversal.png)\n",
"[圖片來源](http://alrightchiu.github.io/SecondRound/graph-breadth-first-searchbfsguang-du-you-xian-sou-xun.html)"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [],
"source": [
"na = Node('A')\n",
"nb = Node('B')\n",
"nc = Node('C')\n",
"nd = Node('D')\n",
"ne = Node('E')\n",
"nf = Node('F')\n",
"\n",
"na.neighbors = [nb, nc]\n",
"nb.neighbors = [nd, ne]\n",
"nc.neighbors = [nf]"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {},
"outputs": [],
"source": [
"bfs = BFS(na)"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Node(name=A)\n",
"Node(name=B)\n",
"Node(name=C)\n",
"Node(name=D)\n",
"Node(name=E)\n",
"Node(name=F)\n"
]
}
],
"source": [
"for node in bfs.traversal():\n",
" print(node)"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.5.2"
}
},
"nbformat": 4,
"nbformat_minor": 2
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.