data structure.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3\n"
     ]
    }
   ],
   "source": [
    "# 最基础的遍历无序列表的查找算法\n",
    "# 时间复杂度O(n)\n",
    "\n",
    "def sequential_search(lis, key):\n",
    "    length = len(lis)\n",
    "    for i in range(length):\n",
    "        if lis[i] == key:\n",
    "            return i\n",
    "    return False\n",
    "        \n",
    "if __name__ == '__main__':\n",
    "    LIST = [1, 5, 8, 123, 22, 54, 7, 99, 300, 222]\n",
    "    result = sequential_search(LIST, 123)\n",
    "    print(result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "times: 4\n",
      "9\n"
     ]
    }
   ],
   "source": [
    "# 针对有序查找线表的二分查找算法\n",
    "# 时间复杂度O(log(n))\n",
    "\n",
    "def binary_search(lis, key):\n",
    "    low = 0\n",
    "    high = len(lis) - 1\n",
    "    time = 0\n",
    "    while low <= high:\n",
    "        time += 1\n",
    "        mid = int((low + high) / 2)\n",
    "        if key < lis[mid]:\n",
    "            high = mid -1\n",
    "        elif key > lis[mid]:\n",
    "            low = mid + 1\n",
    "        else:\n",
    "            # 打印折半的次数\n",
    "            print(\"times: %s\" % time)\n",
    "            return mid\n",
    "    print(\"times: %s\" % time)\n",
    "    return False\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    LIST = [1, 5, 7, 8, 22, 54, 66, 99, 123, 200, 222, 444]\n",
    "    result = binary_search(LIST, 200)\n",
    "    print(result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "times: 4\n",
      "9\n"
     ]
    }
   ],
   "source": [
    "# 插值查找算法\n",
    "# 时间复杂度O(log(n))\n",
    "\n",
    "def binary_search(lis, key):\n",
    "    low = 0\n",
    "    high = len(lis) - 1\n",
    "    time = 0\n",
    "    while low <= high:\n",
    "        time += 1\n",
    "        # 计算mid值是插值算法的核心代码\n",
    "        mid = low + int((high - low) * (key - lis[low])/(lis[high] - lis[low]))\n",
    "        if key < lis[mid]:\n",
    "            high = mid -1\n",
    "        elif key > lis[mid]:\n",
    "            low = mid + 1\n",
    "        else:\n",
    "            # 打印折半的次数\n",
    "            print(\"times: %s\" % time)\n",
    "            return mid\n",
    "    print(\"times: %s\" % time)\n",
    "    return False\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    LIST = [1, 5, 7, 8, 22, 54, 66, 99, 123, 200, 222, 444]\n",
    "    result = binary_search(LIST, 200)\n",
    "    print(result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "6\n",
      "[1, 5, 7, 8, 22, 54, 99, 123, 200, 222, 444, 444, 444]\n",
      "low=0, mid=7, high=10\n",
      "low=8, mid=10, high=10\n",
      "times: 2\n",
      "10\n"
     ]
    }
   ],
   "source": [
    "# 斐波那契查找算法\n",
    "# 时间复杂度O(log(n))\n",
    " \n",
    "def fibonacci_search(lis, key):\n",
    "    # 需要一个现成的斐波那契列表。其最大元素的值必须超过查找表中元素个数的数值。\n",
    "    F = [1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144,\n",
    "         233, 377, 610, 987, 1597, 2584, 4181, 6765,\n",
    "         10946, 17711, 28657, 46368]\n",
    "    low = 0\n",
    "    high = len(lis) - 1\n",
    "    \n",
    "    # 为了方便线表满足斐波那契特性，在表的最后添加几个相同的值\n",
    "    # 这个值是原查找表的最后那个元素的值\n",
    "    # 添加的个数由F[k]-1-high决定\n",
    "    k = 0\n",
    "    while high > F[k]-1:\n",
    "        k += 1\n",
    "    print(k)\n",
    "    i = high\n",
    "    while F[k]-1 > i:\n",
    "        lis.append(lis[high])\n",
    "        i += 1\n",
    "    print(lis)\n",
    "    \n",
    "    # 算法主逻辑。 time用于展示循环的次数。\n",
    "    time = 0\n",
    "    while low <= high:\n",
    "        time += 1\n",
    "        # 为了防止F列表下标溢出，设置if和else\n",
    "        if k < 2:\n",
    "            mid = low\n",
    "        else:\n",
    "            mid = low + F[k-1]-1\n",
    "        \n",
    "        print(\"low=%s, mid=%s, high=%s\" % (low, mid, high))\n",
    "        if key < lis[mid]:\n",
    "            high = mid + 1\n",
    "            k -= 2\n",
    "        elif key > lis[mid]:\n",
    "            low = mid + 1\n",
    "            k -= 2\n",
    "        else:\n",
    "            if mid <= high:\n",
    "                # 打印查找的次数\n",
    "                print(\"times: %s\" % time)\n",
    "                return mid\n",
    "            else:\n",
    "                print(\"times: %s\" % time)\n",
    "                return high\n",
    "    print(\"times: %s\" % time)\n",
    "    return False\n",
    "    \n",
    "if __name__ == '__main__':\n",
    "    LIST = [1, 5, 7, 8, 22, 54, 99, 123, 200, 222, 444]\n",
    "    result = fibonacci_search(LIST, 444)\n",
    "    print(result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "29, \n",
      "35, \n",
      "36, \n",
      "37, \n",
      "48, \n",
      "49, \n",
      "50, \n",
      "51, \n",
      "56, \n",
      "62, \n",
      "73, \n",
      "88, \n",
      "93, \n",
      "99, \n",
      "100, \n"
     ]
    }
   ],
   "source": [
    "class BSTNode:\n",
    "    \"\"\"\n",
    "    定义一个二叉树节点类\n",
    "    \"\"\"\n",
    "    def __init__(self, data, left=None, right=None):\n",
    "        \"\"\"\n",
    "        初始化\n",
    "        ：param data: 节点储存的数据\n",
    "        ：param left: 节点左子树\n",
    "        ：param right: 节点右子树\n",
    "        \"\"\"\n",
    "        self.data = data\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "        \n",
    "class BinarySortTree:\n",
    "    \"\"\"\n",
    "    基于BSTNode类的二叉树。维护一个根节点的指针。\n",
    "    \"\"\"\n",
    "    def __init__(self):\n",
    "        self._root = None\n",
    "        \n",
    "    def is_empty(self):\n",
    "        return self._root is None\n",
    "    \n",
    "    def search(self, key):\n",
    "        \"\"\"\n",
    "        关键码检索\n",
    "        ：param key: 关键码\n",
    "        ：return: 查询节点或None\n",
    "        \"\"\"\n",
    "        bt = self._root\n",
    "        while bt:\n",
    "            entry = bt.data\n",
    "            if key < entry:\n",
    "                bt = bt.left\n",
    "            elif key > entry:\n",
    "                bt = bt.right\n",
    "            else:\n",
    "                return entry\n",
    "        return None\n",
    "    \n",
    "    def insert(self, key):\n",
    "        \"\"\"\n",
    "        插入操作\n",
    "        ：param key：关键码\n",
    "        ：return：布尔值\n",
    "        \"\"\"\n",
    "        bt = self._root\n",
    "        if not bt:\n",
    "            self._root = BSTNode(key)\n",
    "            return\n",
    "        while True:\n",
    "            entry = bt.data\n",
    "            if key < entry:\n",
    "                if bt.left is None:\n",
    "                    bt.left = BSTNode(key)\n",
    "                    return\n",
    "                bt = bt.left\n",
    "            elif key > entry:\n",
    "                if bt.right is None:\n",
    "                    bt.right = BSTNode(key)\n",
    "                    return\n",
    "                bt = bt.right\n",
    "            else:\n",
    "                bt.data = key\n",
    "                return\n",
    "            \n",
    "    def delete(self, key):\n",
    "        \"\"\"\n",
    "        二叉排序树最复杂的方法\n",
    "        ：param key: 关键码\n",
    "        ：return：布尔值\n",
    "        \"\"\"\n",
    "        p, q = None, self._root #维持p为q的父节点，用于后面的链接操作\n",
    "        if not q:\n",
    "            print(\"empty tree!\")\n",
    "            return\n",
    "        while q and q.data != key:\n",
    "            p = q\n",
    "            if key < q.data:\n",
    "                q = q.left\n",
    "            else:\n",
    "                q = q.right\n",
    "            if not q:          # 当树中没有关键码key时， 结束退出。\n",
    "                return\n",
    "        # 上面已将找到了要删除的节点，用q引用。而p则是q的父节点或者None(q为根节点时)。\n",
    "        if not q.left:\n",
    "            if p is None:\n",
    "                self._root = q.right\n",
    "            elif q is p.left:\n",
    "                p.left = q.right\n",
    "            else:\n",
    "                p.right = q.right\n",
    "            return\n",
    "        # 查找节点q的左子树的最右节点，将q的右子树链接为该节点的右子树\n",
    "        # 该方法可能会增大树的深度，效率并不算高，可以设计其他的方法。\n",
    "        r = q.left\n",
    "        while r.right:\n",
    "            r = r.right\n",
    "        r.right = q.right\n",
    "        if p is None:\n",
    "            self._root = q.left\n",
    "        elif p.left is q:\n",
    "            p.left = q.left\n",
    "        else:\n",
    "            p.right = q.left\n",
    "            \n",
    "    def __iter__(self):\n",
    "        \"\"\"\n",
    "        实现二叉树的中序遍历算法，\n",
    "        展示我们创建的二叉排序树。\n",
    "        直接使用python内置的列表作为一个栈\n",
    "        ：return： data\n",
    "        \"\"\"\n",
    "        stack = []\n",
    "        node = self._root\n",
    "        while node or stack:\n",
    "            while node:\n",
    "                stack.append(node)\n",
    "                node = node.left\n",
    "            node = stack.pop()\n",
    "            yield node.data\n",
    "            node = node.right\n",
    "\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    lis = [62, 58, 88, 48, 73, 99, 35, 51, 93, 29, 37, 49, 56, 36, 50]\n",
    "    bs_tree = BinarySortTree()\n",
    "    for i in range(len(lis)):\n",
    "        bs_tree.insert(lis[i])\n",
    "    bs_tree.insert(100)\n",
    "    bs_tree.delete(58)\n",
    "    for i in bs_tree:\n",
    "        print(str(i)+', ')\n",
    "    # print(\"\\n\", bs_tree.search(4))\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(12, 0)\n",
      "(25, 1)\n",
      "(37, 2)\n",
      "(15, 3)\n",
      "(16, 4)\n",
      "(29, 5)\n",
      "(48, 6)\n",
      "(67, 7)\n",
      "(56, 8)\n",
      "(34, 9)\n",
      "(22, 10)\n",
      "(47, 11)\n",
      "n\n",
      "True\n",
      "False\n"
     ]
    }
   ],
   "source": [
    "# 忽略了对数据类型， 元素溢出等问题的判断。\n",
    "\n",
    "class HashTable:\n",
    "    def __init__(self, size):\n",
    "        self.elem = [None for i in range(size)] # 使用list数据结构作为哈希表元素保存方法\n",
    "        self.count = size # 最大表长\n",
    "        \n",
    "    def hash(self, key):\n",
    "        return key % self.count # 数列函数采用除留除数法\n",
    "    \n",
    "    def insert_hash(self, key):\n",
    "        \"\"\"插入关键字到hash表中\"\"\"\n",
    "        address = self.hash(key) # 求散列地址\n",
    "        while self.elem[address]: # 当前位置已经有数据了，发生冲突。\n",
    "            address = (address+1) % self.count # 线性探测下一地址是否可用。\n",
    "        self.elem[address] = key # 没有冲突直接保存。\n",
    "        \n",
    "    def search_hash(self, key):\n",
    "        \"\"\"查找关键字，返回布尔值\"\"\"\n",
    "        star = address = self.hash(key)\n",
    "        while self.elem[address] != key:\n",
    "            address = (address + 1) % self.count\n",
    "            if not self.elem[address] or address == star: # 说明没找到或者循环到了开始的位置\n",
    "                return False\n",
    "        return True\n",
    "    \n",
    "\n",
    "if __name__ == '__main__':\n",
    "    list_a = [12, 67, 56, 16, 25, 37, 22, 29, 15, 47, 48, 34]\n",
    "    hash_table = HashTable(12)\n",
    "    for i in list_a:\n",
    "        hash_table.insert_hash(i)\n",
    " \n",
    "    for i in hash_table.elem:\n",
    "        if i:\n",
    "            print((i, hash_table.elem.index(i)))\n",
    "    print(\"n\")\n",
    " \n",
    "    print(hash_table.search_hash(15))\n",
    "    print(hash_table.search_hash(33))\n",
    "        \n",
    " \n",
    "               "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      ". . . . . X . . \n",
      ". . . X . . . . \n",
      ". . . . . . X . \n",
      "X . . . . . . . \n",
      ". . . . . . . X \n",
      ". X . . . . . . \n",
      ". . . . X . . . \n",
      ". . X . . . . . \n"
     ]
    }
   ],
   "source": [
    "# 八皇后问题\n",
    "import random\n",
    "#冲突检查，在定义state时，采用state来标志每个皇后的位置，其中索引用来表示横坐标，基对应的值表示纵坐标，例如： state[0]=3，表示该皇后位于第1行的第4列上\n",
    "def conflict(state, nextX):\n",
    "    nextY = len(state)\n",
    "    for i in range(nextY):\n",
    "        #如果下一个皇后的位置与当前的皇后位置相邻（包括上下，左右）或在同一对角线上，则说明有冲突，需要重新摆放\n",
    "        if abs(state[i]-nextX) in (0, nextY-i):\n",
    "            return True\n",
    "    return False\n",
    "\n",
    "#采用生成器的方式来产生每一个皇后的位置，并用递归来实现下一个皇后的位置。\n",
    "def queens(num, state=()):\n",
    "    for pos in range(num):\n",
    "        if not conflict(state, pos):\n",
    "            #产生当前皇后的位置信息\n",
    "            if len(state) == num-1:\n",
    "                yield (pos, )\n",
    "            #否则，把当前皇后的位置信息，添加到状态列表里，并传递给下一皇后。\n",
    "            else:\n",
    "                for result in queens(num, state+(pos,)):\n",
    "                    yield (pos, ) + result\n",
    "\n",
    "\n",
    "#为了直观表现棋盘，用X表示每个皇后的位置\n",
    "def prettyprint(solution):\n",
    "    def line(pos, length=len(solution)):\n",
    "        return '. ' * (pos) + 'X ' + '. '*(length-pos-1)\n",
    "    for pos in solution:\n",
    "        print line(pos)\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    prettyprint(random.choice(list(queens(8))))\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n",
      "False\n",
      "2\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "'dog'"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "class Queue:\n",
    "    \"\"\"模拟队列\"\"\"\n",
    "    def __init__(self):\n",
    "        self.items = []\n",
    "        \n",
    "    def isEmpty(self):\n",
    "        if self.items == []:\n",
    "            print 'True'\n",
    "        else:\n",
    "            print 'False'\n",
    "    \n",
    "    def enqueue(self, item):\n",
    "        self.items.insert(0, item)\n",
    "        \n",
    "    def dequeue(self):\n",
    "        return self.items.pop()\n",
    "    \n",
    "    def size(self):\n",
    "        print len(self.items)\n",
    "    \n",
    "q=Queue()\n",
    "q.isEmpty()\n",
    "\n",
    "q.enqueue('dog')\n",
    "q.enqueue(4)\n",
    "q.isEmpty()\n",
    "q.size()\n",
    "q.dequeue()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n",
      "dog\n",
      "3\n",
      "False\n",
      "8.4\n",
      "True\n",
      "2\n"
     ]
    }
   ],
   "source": [
    "class Stack: \n",
    "    \"\"\"模拟栈\"\"\" \n",
    "    def __init__(self): \n",
    "        self.items = [] \n",
    "\n",
    "    def isEmpty(self): \n",
    "        return len(self.items)==0  \n",
    "\n",
    "    def push(self, item): \n",
    "        self.items.append(item) \n",
    "\n",
    "    def pop(self): \n",
    "        return self.items.pop()  \n",
    "\n",
    "    def peek(self): \n",
    "        if not self.isEmpty(): \n",
    "            return self.items[len(self.items)-1] \n",
    "\n",
    "    def size(self): \n",
    "        return len(self.items) \n",
    "    \n",
    "s=Stack() \n",
    "print(s.isEmpty()) \n",
    "s.push(4) \n",
    "s.push('dog') \n",
    "print(s.peek()) \n",
    "s.push(True) \n",
    "print(s.size()) \n",
    "print(s.isEmpty()) \n",
    "s.push(8.4) \n",
    "print(s.pop()) \n",
    "print(s.pop()) \n",
    "print(s.size()) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class LinkedList():\n",
    "    def __init__(self, value=None):\n",
    "        self.value = value\n",
    "        # 前驱\n",
    "        self.before = None\n",
    "        # 后继\n",
    "        self.behind = None\n",
    "    \n",
    "    def __str__(self):\n",
    "        if self.value is not None:\n",
    "            return str(self.value)\n",
    "        else:\n",
    "            return 'None'\n",
    "    \n",
    "def init():\n",
    "    return LinkedList('HEAD')\n",
    "\n",
    "\n",
    "def delete(linked_list):\n",
    "    if isinstance(linked_list, LinkedList):\n",
    "        if linked_list.behind is not None:\n",
    "            delete(linked_list.behind)\n",
    "            linked_list.behind = None\n",
    "            linked_list.before = None\n",
    "        linked_list.value = None\n",
    "        \n",
    "    \n",
    "def insert(linked_list, index, node):\n",
    "    node = LinkedList(node)\n",
    "    if isinstance(linked_list, LinkedList):\n",
    "        i = 0\n",
    "        while linked_list.behind is not None:\n",
    "            if i == index:\n",
    "                break\n",
    "            i += 1\n",
    "            linked_list = linked_list.behind\n",
    "        if linked_list.behind is not None:\n",
    "            node.behind = linked_list.behind\n",
    "            linked_list.behind.before = node\n",
    "        node.before, linked_list.behind = linked_list, node\n",
    "        \n",
    "\n",
    "def remove(linked_list, index):\n",
    "    if isinstance(linked_list, LinkedList):\n",
    "        i = 0\n",
    "        while linked_list.behind is not None:\n",
    "            if i == index:\n",
    "                break\n",
    "            i += 1\n",
    "            linked_list = linked_list.behind\n",
    "    if linked_list.behind is not None:\n",
    "        linked_list.behind.before = linked_list.before\n",
    "    if linked_list.before is not None:\n",
    "        linked_list.before.behind = linked_list.behind\n",
    "    linked_list.behind = None\n",
    "    linked.list.before = None\n",
    "    linked_list.value = None\n",
    "    \n",
    "\n",
    "def trave(linked_list):\n",
    "    if isinstance(linked_list, LinkedList):\n",
    "        print(linked_list)\n",
    "        if linked_list.behind is not None:\n",
    "            trave(linked_list.behind)\n",
    "            \n",
    "        \n",
    "def find(linked_list, index):\n",
    "    if isinstance(linked_list, LinkedList):\n",
    "        i = 0\n",
    "        while linked_list.behind is not None:\n",
    "            if i == index:\n",
    "                return linked_list\n",
    "            i += 1\n",
    "            linked_list = linked_list.behind\n",
    "    else:\n",
    "        if i< index:\n",
    "            raise Exception(404)\n",
    "        return linked_list\n",
    "    \n",
    "linked_list = init()\n",
    "trave(linked_list)\n",
    "insert(linked_list, 1, 2)\n",
    "trave(linked_list)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[5, 6, 1, 3, 8, 6, 9, 7]\n",
      "[5, 1, 6, 3, 8, 6, 9, 7]\n",
      "[1, 5, 6, 3, 8, 6, 9, 7]\n",
      "[1, 5, 3, 6, 8, 6, 9, 7]\n",
      "[1, 3, 5, 6, 8, 6, 9, 7]\n",
      "[1, 3, 5, 6, 6, 8, 9, 7]\n",
      "[1, 3, 5, 6, 6, 8, 7, 9]\n",
      "[1, 3, 5, 6, 6, 7, 8, 9]\n"
     ]
    }
   ],
   "source": [
    "# 插入排序 O(n^2)\n",
    "def insert_sort(lists):\n",
    "    count = len(lists)\n",
    "    for i in range(1, count):\n",
    "        key = lists[i]\n",
    "        j = i - 1\n",
    "        while j >= 0:\n",
    "            if lists[j] > key:\n",
    "                print lists\n",
    "                lists[j + 1] = lists[j]\n",
    "                lists[j] = key\n",
    "            j -= 1\n",
    "    return lists\n",
    "\n",
    "list = [5, 6, 1, 3, 8, 6, 9, 7]\n",
    "print insert_sort(list)    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[5, 6, 1, 3, 8, 6, 9, 7]\n",
      "[1, 6, 5, 3, 8, 6, 9, 7]\n",
      "[1, 3, 5, 6, 8, 6, 9, 7]\n",
      "[1, 3, 5, 6, 6, 8, 9, 7]\n",
      "[1, 3, 5, 6, 6, 8, 7, 9]\n",
      "[1, 3, 5, 6, 6, 7, 8, 9]\n"
     ]
    }
   ],
   "source": [
    "# 希尔排序\n",
    "def shell_sort(lists):\n",
    "    count = len(lists)\n",
    "    step = 2\n",
    "    group = count / step\n",
    "    while group > 0:\n",
    "        for i in range(0, group):\n",
    "            j = i + group\n",
    "            while j < count:\n",
    "                k = j - group\n",
    "                key = lists[j]\n",
    "                while k >= 0:\n",
    "                    if lists[k] > key:\n",
    "                        print lists\n",
    "                        lists[k + group] = lists[k]\n",
    "                        lists[k] = key\n",
    "                    k -= group\n",
    "                j += group\n",
    "        group /= step\n",
    "    return lists\n",
    "\n",
    "list = [5, 6, 1, 3, 8, 6, 9, 7]\n",
    "print shell_sort(list)   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[5, 6, 1, 3, 8, 6, 9, 7]\n",
      "[1, 6, 5, 3, 8, 6, 9, 7]\n",
      "[1, 3, 5, 6, 8, 6, 9, 7]\n",
      "[1, 3, 5, 6, 6, 8, 9, 7]\n",
      "[1, 3, 5, 6, 6, 8, 7, 9]\n",
      "[1, 3, 5, 6, 6, 7, 8, 9]\n"
     ]
    }
   ],
   "source": [
    "# 冒泡排序\n",
    "def bubble_sort(lists):\n",
    "    count = len(lists)\n",
    "    for i in range(0, count):\n",
    "        for j in range(i+1, count):\n",
    "            if lists[i] > lists[j]:\n",
    "                print lists\n",
    "                lists[i], lists[j] = lists[j], lists[i]\n",
    "    return lists\n",
    "\n",
    "list = [5, 6, 1, 3, 8, 6, 9, 7]\n",
    "print shell_sort(list)   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[3, 6, 1, 3, 8, 6, 9, 7]\n",
      "[3, 6, 1, 6, 8, 6, 9, 7]\n",
      "[3, 1, 1, 6, 8, 6, 9, 7]\n",
      "[3, 1, 1, 6, 8, 6, 9, 7]\n",
      "[1, 1, 5, 6, 8, 6, 9, 7]\n",
      "[1, 1, 5, 6, 8, 6, 9, 7]\n",
      "[1, 3, 5, 6, 8, 6, 9, 7]\n",
      "[1, 3, 5, 6, 8, 6, 9, 7]\n",
      "[1, 3, 5, 6, 7, 6, 9, 7]\n",
      "[1, 3, 5, 6, 7, 6, 9, 9]\n",
      "[1, 3, 5, 6, 7, 6, 9, 9]\n",
      "[1, 3, 5, 6, 7, 6, 9, 9]\n",
      "[1, 3, 5, 6, 6, 6, 8, 9]\n",
      "[1, 3, 5, 6, 6, 6, 8, 9]\n",
      "[1, 3, 5, 6, 6, 7, 8, 9]\n"
     ]
    }
   ],
   "source": [
    "# 快速排序\n",
    "def quick_sort(lists, left, right):\n",
    "    if left >= right:\n",
    "        return lists\n",
    "    key = lists[left]\n",
    "    low = left\n",
    "    high = right\n",
    "    while left < right:\n",
    "        while left < right and lists[right] >= key:\n",
    "            right -= 1\n",
    "        lists[left] = lists[right]\n",
    "        print lists\n",
    "        while left < right and lists[left] <= key:\n",
    "            left += 1\n",
    "        lists[right] = lists[left]\n",
    "        print lists\n",
    "    lists[right] = key\n",
    "    quick_sort(lists, low, left - 1)\n",
    "    quick_sort(lists, left + 1, high)\n",
    "    return lists\n",
    "\n",
    "list = [5, 6, 1, 3, 8, 6, 9, 7]\n",
    "print quick_sort(list, 0, 7)   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[5, 6, 1, 3, 8, 6, 9, 7]\n",
      "[1, 6, 5, 3, 8, 6, 9, 7]\n",
      "[1, 3, 5, 6, 8, 6, 9, 7]\n",
      "[1, 3, 5, 6, 8, 6, 9, 7]\n",
      "[1, 3, 5, 6, 8, 6, 9, 7]\n",
      "[1, 3, 5, 6, 6, 8, 9, 7]\n",
      "[1, 3, 5, 6, 6, 7, 9, 8]\n",
      "[1, 3, 5, 6, 6, 7, 8, 9]\n",
      "[1, 3, 5, 6, 6, 7, 8, 9]\n"
     ]
    }
   ],
   "source": [
    "# 直接选择排序\n",
    "def select_sort(lists):\n",
    "    count = len(lists)\n",
    "    for i in range(0, count):\n",
    "        min = i\n",
    "        for j in range(i + 1, count):\n",
    "            if lists[min] > lists[j]:\n",
    "                min = j\n",
    "        print lists\n",
    "        lists[min], lists[i] = lists[i], lists[min]\n",
    "    return lists\n",
    "\n",
    "list = [5, 6, 1, 3, 8, 6, 9, 7]\n",
    "print select_sort(list)   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[9, 8, 6, 7, 6, 5, 1, 3]\n",
      "[8, 7, 6, 3, 6, 5, 1, 9]\n",
      "[7, 6, 6, 3, 1, 5, 8, 9]\n",
      "[6, 5, 6, 3, 1, 7, 8, 9]\n",
      "[6, 5, 1, 3, 6, 7, 8, 9]\n",
      "[5, 3, 1, 6, 6, 7, 8, 9]\n",
      "[3, 1, 5, 6, 6, 7, 8, 9]\n",
      "[1, 3, 5, 6, 6, 7, 8, 9]\n",
      "None\n"
     ]
    }
   ],
   "source": [
    "# 堆排序\n",
    "def adjust_heap(lists, i, size):\n",
    "    lchild = 2 * i + 1\n",
    "    rchild = 2 * i + 2\n",
    "    max = i \n",
    "    if i < size / 2:\n",
    "        if lchild < size and lists[lchild] > lists[max]:\n",
    "            max = lchild\n",
    "        if rchild < size and lists[rchild] > lists[max]:\n",
    "            max = rchild\n",
    "        if max != i:\n",
    "            lists[max], lists[i] = lists[i], lists[max]\n",
    "            adjust_heap(lists, max, size)\n",
    "            \n",
    "            \n",
    "def build_heap(lists, size):\n",
    "    for i in range(0, (size/2))[::-1]:\n",
    "        adjust_heap(lists, i, size)\n",
    "        \n",
    "def heap_sort(lists):\n",
    "    size = len(lists)\n",
    "    build_heap(lists, size)\n",
    "    for i in range(0, size)[::-1]:\n",
    "        print lists\n",
    "        lists[0], lists[i] = lists[i], lists[0]\n",
    "        adjust_heap(lists, 0, i)\n",
    "        \n",
    "list = [5, 6, 1, 3, 8, 6, 9, 7]\n",
    "print heap_sort(list)  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "------------\n",
      "[5]\n",
      "[5, 6]\n",
      "------------\n",
      "[1]\n",
      "[1, 3]\n",
      "------------\n",
      "[1]\n",
      "[1, 3]\n",
      "[1, 3, 5, 6]\n",
      "------------\n",
      "[6]\n",
      "[6, 8]\n",
      "------------\n",
      "[7]\n",
      "[7, 9]\n",
      "------------\n",
      "[6]\n",
      "[6, 7]\n",
      "[6, 7, 8]\n",
      "[6, 7, 8, 9]\n",
      "------------\n",
      "[1]\n",
      "[1, 3]\n",
      "[1, 3, 5]\n",
      "[1, 3, 5, 6]\n",
      "[1, 3, 5, 6, 6, 7, 8, 9]\n",
      "[1, 3, 5, 6, 6, 7, 8, 9]\n"
     ]
    }
   ],
   "source": [
    "# 归并排序\n",
    "def merge(left, right):\n",
    "    i, j = 0, 0\n",
    "    result = []\n",
    "    print '------------'\n",
    "    while i < len(left) and j < len(right):\n",
    "        if left[i] <= right[j]:\n",
    "            result.append(left[i])\n",
    "            i += 1\n",
    "        else:\n",
    "            result.append(right[j])\n",
    "            j += 1\n",
    "        print result\n",
    "    result += left[i:]\n",
    "    result += right[j:]\n",
    "    print result\n",
    "    return result\n",
    "\n",
    "def merge_sort(lists):\n",
    "    if len(lists) <= 1:\n",
    "        return lists\n",
    "    num = len(lists) / 2\n",
    "    left = merge_sort(lists[:num])\n",
    "    right = merge_sort(lists[num:])\n",
    "    return merge(left, right)\n",
    "\n",
    "list = [5, 6, 1, 3, 8, 6, 9, 7]\n",
    "print merge_sort(list)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "9\n",
      "0.954242509439\n",
      "1\n",
      "---------\n",
      "5\n",
      "[[], [], [], [], [], [5], [], [], [], []]\n",
      "6\n",
      "[[], [], [], [], [], [5], [6], [], [], []]\n",
      "1\n",
      "[[], [1], [], [], [], [5], [6], [], [], []]\n",
      "3\n",
      "[[], [1], [], [3], [], [5], [6], [], [], []]\n",
      "8\n",
      "[[], [1], [], [3], [], [5], [6], [], [8], []]\n",
      "6\n",
      "[[], [1], [], [3], [], [5], [6, 6], [], [8], []]\n",
      "9\n",
      "[[], [1], [], [3], [], [5], [6, 6], [], [8], [9]]\n",
      "7\n",
      "[[], [1], [], [3], [], [5], [6, 6], [7], [8], [9]]\n",
      "----------\n",
      "[]\n",
      "[1]\n",
      "[1]\n",
      "[1, 3]\n",
      "[1, 3]\n",
      "[1, 3, 5]\n",
      "[1, 3, 5, 6, 6]\n",
      "[1, 3, 5, 6, 6, 7]\n",
      "[1, 3, 5, 6, 6, 7, 8]\n",
      "[1, 3, 5, 6, 6, 7, 8, 9]\n",
      "[1, 3, 5, 6, 6, 7, 8, 9]\n"
     ]
    }
   ],
   "source": [
    "# 基数排序\n",
    "# O(nlog(r)m)\n",
    "\n",
    "import math\n",
    "def radix_sort(lists, radix=10):\n",
    "    print max(lists)\n",
    "    print math.log(max(lists), radix)\n",
    "    k = int(math.ceil(math.log(max(lists), radix)))\n",
    "    print k\n",
    "    print '---------'\n",
    "    bucket = [[] for i in range(radix)]\n",
    "    for i in range(1, k+1):\n",
    "        for j in lists:\n",
    "            print j/(radix**(i-1)) % (radix**i)\n",
    "            bucket[j/(radix**(i-1)) % (radix**i)].append(j)\n",
    "            print bucket\n",
    "        print '----------'\n",
    "        del lists[:]\n",
    "        for z in bucket:\n",
    "            lists += z\n",
    "            print lists\n",
    "            del z[:]\n",
    "    return lists\n",
    "\n",
    "list = [5, 6, 1, 3, 8, 6, 9, 7]\n",
    "print radix_sort(list)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3\n",
      "****NLR:\n",
      "3 |  2 |  1 |  4 |  6 |  5 |  7 |  8 |  \n",
      "****LNR\n",
      "1 |  2 |  3 |  4 |  5 |  6 |  7 |  8 |  \n",
      "****LRN\n",
      "1 |  2 |  5 |  8 |  7 |  6 |  4 |  3 |  \n",
      "****LayerTraversal\n",
      "3 |  2 |  4 |  1 |  6 |  5 |  7 |  8 | \n"
     ]
    }
   ],
   "source": [
    "import math\n",
    "\n",
    "class BTNode(object):\n",
    "    \"\"\"docstring for BTNode\"\"\"\n",
    "    def __init__(self, data):\n",
    "        self.data = data\n",
    "        self.leftChild = None\n",
    "        self.rightChild = None\n",
    "        \n",
    "# insert element\n",
    "def InsertElementBinaryTree(root, node):\n",
    "    if root:\n",
    "        if node.data < root.data:\n",
    "            if root.leftChild:\n",
    "                InsertElementBinaryTree(root.leftChild, node)\n",
    "            else:\n",
    "                root.leftChild = node\n",
    "        else:\n",
    "            if root.rightChild:\n",
    "                InsertElementBinaryTree(root.rightChild, node)\n",
    "            else:\n",
    "                root.rightChild = node\n",
    "    else:\n",
    "        return 0\n",
    "    \n",
    "# init a tree\n",
    "def InitBinaryTree(dataSource, length):\n",
    "    root = BTNode(dataSource[0])\n",
    "    \n",
    "    for x in xrange(1, length):\n",
    "        node = BTNode(dataSource[x])\n",
    "        InsertElementBinaryTree(root, node)\n",
    "    return root\n",
    "    print 'Done...'\n",
    "    \n",
    "# pre-order\n",
    "def PreorderTraversalBinaryTree(root):\n",
    "    if root:\n",
    "        print '%d | ' % root.data,\n",
    "        PreorderTraversalBinaryTree(root.leftChild)\n",
    "        PreorderTraversalBinaryTree(root.rightChild)\n",
    "        \n",
    "# in-order\n",
    "def InorderTraversalBinaryTree(root):\n",
    "    if root:\n",
    "        InorderTraversalBinaryTree(root.leftChild)\n",
    "        print '%d | ' % root.data,\n",
    "        InorderTraversalBinaryTree(root.rightChild)\n",
    "        \n",
    "# post-order\n",
    "def PostorderTraversalBinaryTree(root):\n",
    "    if root:\n",
    "        PostorderTraversalBinaryTree(root.leftChild)\n",
    "        PostorderTraversalBinaryTree(root.rightChild)\n",
    "        print '%d | ' % root.data,\n",
    "        \n",
    "# layer-order\n",
    "def TraversalByLayer(root, length):\n",
    "    stack = []\n",
    "    stack.append(root)\n",
    "    for x in xrange(length):\n",
    "        node = stack[x]\n",
    "        print '%d | ' % node.data,\n",
    "        if node.leftChild:\n",
    "            stack.append(node.leftChild)\n",
    "        if node.rightChild:\n",
    "            stack.append(node.rightChild)\n",
    "            \n",
    "\n",
    "if __name__ == '__main__':\n",
    "    dataSource = [3, 4, 2, 6, 7, 1, 8, 5]\n",
    "    length = len(dataSource)\n",
    "    BTree = InitBinaryTree(dataSource, length)\n",
    "    print BTree.data\n",
    "    print '****NLR:'\n",
    "    PreorderTraversalBinaryTree(BTree)\n",
    "    print '\\n****LNR'\n",
    "    InorderTraversalBinaryTree(BTree)\n",
    "    print '\\n****LRN'\n",
    "    PostorderTraversalBinaryTree(BTree)\n",
    "    print '\\n****LayerTraversal'\n",
    "    TraversalByLayer(BTree, length)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "('depth:', 4)\n",
      "('width:', 3)\n"
     ]
    }
   ],
   "source": [
    "import Queue\n",
    "\n",
    "class Node:\n",
    "    def __init__(self, value=None, left=None, right=None):\n",
    "        self.value = value\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "        \n",
    "def treeDepth(tree):\n",
    "    if tree == None:\n",
    "        return 0\n",
    "    leftDepth = treeDepth(tree.left)\n",
    "    rightDepth = treeDepth(tree.right)\n",
    "    if leftDepth > rightDepth:\n",
    "        return leftDepth + 1\n",
    "    if rightDepth >= leftDepth:\n",
    "        return rightDepth + 1\n",
    "    \n",
    "def treeWidth(tree):\n",
    "    curwidth = 1\n",
    "    maxwidth = 0\n",
    "    q = Queue.Queue()\n",
    "    q.put(tree)\n",
    "    while not q.empty():\n",
    "        n = curwidth\n",
    "        for i in range(n):\n",
    "            tmp = q.get()\n",
    "            curwidth -= 1\n",
    "            if tmp.left:\n",
    "                q.put(tmp.left)\n",
    "                curwidth += 1\n",
    "            if tmp.right:\n",
    "                q.put(tmp.right)\n",
    "                curwidth += 1\n",
    "        if curwidth > maxwidth:\n",
    "            maxwidth = curwidth\n",
    "    return maxwidth\n",
    "\n",
    "if __name__=='__main__':\n",
    "    root = Node('D', Node('B', Node('A'), Node('C')), Node('E', right=Node('G', Node('F'))))\n",
    "    depth = treeDepth(root)\n",
    "    width = treeWidth(root)\n",
    "    print('depth:', depth)\n",
    "    print('width:', width)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{1: 999, 2: 999, 3: 999, 4: 999, 5: 999, 6: 999}\n",
      "{1: 0, 2: 999, 3: 999, 4: 999, 5: 999, 6: 999}\n",
      "------------\n",
      "1\n",
      "{1: 0, 2: 1, 3: 12}\n",
      "0\n",
      "0\n",
      "0\n",
      "----------\n",
      "0\n",
      "1\n",
      "999\n",
      "----------\n",
      "0\n",
      "12\n",
      "999\n",
      "----------\n",
      "------------\n",
      "2\n",
      "{2: 0, 3: 9, 4: 3}\n",
      "1\n",
      "0\n",
      "1\n",
      "----------\n",
      "1\n",
      "9\n",
      "12\n",
      "----------\n",
      "1\n",
      "3\n",
      "999\n",
      "----------\n",
      "------------\n",
      "4\n",
      "{3: 4, 4: 0, 5: 13, 6: 15}\n",
      "4\n",
      "4\n",
      "10\n",
      "----------\n",
      "4\n",
      "0\n",
      "4\n",
      "----------\n",
      "4\n",
      "13\n",
      "999\n",
      "----------\n",
      "4\n",
      "15\n",
      "999\n",
      "----------\n",
      "------------\n",
      "3\n",
      "{3: 0, 5: 5}\n",
      "8\n",
      "0\n",
      "8\n",
      "----------\n",
      "8\n",
      "5\n",
      "17\n",
      "----------\n",
      "------------\n",
      "5\n",
      "{5: 0, 6: 4}\n",
      "13\n",
      "0\n",
      "13\n",
      "----------\n",
      "13\n",
      "4\n",
      "19\n",
      "----------\n",
      "------------\n",
      "6\n",
      "{6: 0}\n",
      "17\n",
      "0\n",
      "17\n",
      "----------\n",
      "[0, 1, 8, 4, 13, 17]\n"
     ]
    }
   ],
   "source": [
    "# Dijkstra算法————通过边实现松弛\n",
    "# 指定一个点到其他各项点的路径————单源最短路径\n",
    "\n",
    "# 初始化图参数\n",
    "G = {1: {1:0, 2:1, 3:12},\n",
    "     2: {2:0, 3:9, 4:3},\n",
    "     3: {3:0, 5:5},\n",
    "     4: {3:4, 4:0, 5:13, 6:15},\n",
    "     5: {5:0, 6:4},\n",
    "     6: {6:0}}\n",
    "\n",
    "# 每次找到离源点最近的一个顶点， 然后以该顶点为重心进行扩展\n",
    "# 最终的到源点到其余所有点的最短路径\n",
    "# 一种贪婪算法\n",
    "\n",
    "def Dijkstra(G, v0, INF=999):\n",
    "    \"\"\" 使用 Dijkstra 算法计算指定点 v0 到图 G 中任意点的最短路径的距离\n",
    "        INF 为设定的无限远距离值\n",
    "        此方法不能解决负权值边的图\n",
    "    \"\"\"\n",
    "    book = set()\n",
    "    minv = v0\n",
    "    \n",
    "    dis = dict((k, INF) for k in G.keys())\n",
    "    print dis\n",
    "    dis[v0] = 0\n",
    "    print dis\n",
    "    \n",
    "    while len(book)<len(G):\n",
    "        book.add(minv)    # 确定当期顶点的距离\n",
    "        print '------------'\n",
    "        print minv\n",
    "        print G[minv]\n",
    "        for w in G[minv]:   # 以当前点的中心向外扩散\n",
    "            print dis[minv]\n",
    "            print G[minv][w]\n",
    "            print dis[w]\n",
    "            print '----------'\n",
    "            if dis[minv] + G[minv][w] < dis[w]: # 如果从当前点扩展到某一点的距离小于已知最短距离\n",
    "                dis[w] = dis[minv] + G[minv][w] # 对已知距离进行更新\n",
    "        new = INF # 从剩下的未确定点中选择最小距离点作为新的扩散点\n",
    "        for v in dis.keys():\n",
    "            if v in book:\n",
    "                continue\n",
    "            if dis[v] < new:\n",
    "                new = dis[v]\n",
    "                minv = v\n",
    "    return dis\n",
    "\n",
    "dis = Dijkstra(G, v0=1)\n",
    "print dis.values()\n",
    "        \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "nodes: [1, 2, 3, 4, 5, 6, 7, 8]\n",
      "[1, 2, 4, 8, 5, 3, 6, 7]\n"
     ]
    }
   ],
   "source": [
    "class Graph(object):\n",
    "    def __init__(self, *args, **kwargs):\n",
    "        self.node_neighbors = {}\n",
    "        self.visited = {}\n",
    "    \n",
    "    def add_nodes(self, nodelist):\n",
    "        for node in nodelist:\n",
    "            self.add_node(node)\n",
    "            \n",
    "    def add_node(self, node):\n",
    "        if not node in self.nodes():\n",
    "            self.node_neighbors[node] = []\n",
    "            \n",
    "    def add_edge(self, edge):\n",
    "        u, v = edge\n",
    "        if (v not in self.node_neighbors[u]) and (u not in self.node_neighbors[v]):\n",
    "            self.node_neighbors[u].append(v)\n",
    "            if (u != v):\n",
    "                self.node_neighbors[v].append(u)\n",
    "                \n",
    "    def nodes(self):\n",
    "        return self.node_neighbors.keys()\n",
    "    \n",
    "    def depth_first_search(self, root=None):\n",
    "        order = []\n",
    "        def dfs(node):\n",
    "            self.visited[node] = True\n",
    "            order.append(node)\n",
    "            for n in self.node_neighbors[node]:\n",
    "                if not n in self.visited:\n",
    "                    dfs(n)\n",
    "                \n",
    "        if root:\n",
    "            dfs(root)\n",
    "            \n",
    "        for node in self.nodes():\n",
    "            if not node in self.visited:\n",
    "                dfs(node)\n",
    "        print order\n",
    "        return order\n",
    "    \n",
    "    def breadth_first_search(self, root=None):\n",
    "        queue = []\n",
    "        order = []\n",
    "        def bfs():\n",
    "            while len(queue) > 0:\n",
    "                node = queue.pop(0)\n",
    "                self.visited[node] = True\n",
    "                for n in self.node_neighbors[node]:\n",
    "                    if (not n in self.visited) and (not n in queue):\n",
    "                        queue.append(n)\n",
    "                        order.append(n)\n",
    "            if root:\n",
    "                queue.append(root)\n",
    "                order.append(root)\n",
    "                bfs()\n",
    "            for node in self.nodes():\n",
    "                if not node in self.visited:\n",
    "                    queue.append(node)\n",
    "                    order.append(node)\n",
    "                    bfs()\n",
    "            print order\n",
    "            return order\n",
    "if __name__ == '__main__':\n",
    "    g = Graph()\n",
    "    g.add_nodes([i+1 for i in range(8)])\n",
    "    g.add_edge((1, 2))\n",
    "    g.add_edge((1, 3))\n",
    "    g.add_edge((2, 4))\n",
    "    g.add_edge((2, 5))\n",
    "    g.add_edge((4, 8))\n",
    "    g.add_edge((5, 8))\n",
    "    g.add_edge((3, 6))\n",
    "    g.add_edge((3, 7))\n",
    "    g.add_edge((6, 7))\n",
    "    print \"nodes:\", g.nodes()\n",
    "    order = g.breadth_first_search(1)\n",
    "    order = g.depth_first_search(1)            \n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['A', 'B', 'C', 'D']\n",
      "[['A', 'B', 'C', 'D'], ['A', 'B', 'D'], ['A', 'C', 'D']]\n",
      "['A', 'B', 'D']\n"
     ]
    }
   ],
   "source": [
    "graph = {'A': ['B', 'C'],\n",
    "         'B': ['C', 'D'],\n",
    "         'C': ['D'],\n",
    "         'D': ['C'],\n",
    "         'E': ['F'],\n",
    "         'F': ['C']}\n",
    "\n",
    "# find a path\n",
    "def find_path(graph, start, end, path=[]):\n",
    "    path = path + [start]\n",
    "    if start == end:\n",
    "        return path\n",
    "    if not graph.has_key(start):\n",
    "        return None\n",
    "    for node in graph[start]:\n",
    "        if node not in path:\n",
    "            newpath = find_path(graph, node, end, path)\n",
    "            if newpath:\n",
    "                return newpath\n",
    "    return None\n",
    "\n",
    "# find all paths\n",
    "def find_all_paths(graph, start, end, path=[]):\n",
    "    path = path + [start]\n",
    "    if start == end:\n",
    "        return [path]\n",
    "    if not graph.has_key(start):\n",
    "        return []\n",
    "    paths = []\n",
    "    for node in graph[start]:\n",
    "        newpaths = find_all_paths(graph, node, end, path)\n",
    "        for newpath in newpaths:\n",
    "            paths.append(newpath)\n",
    "    return paths\n",
    "\n",
    "# find shortest path\n",
    "def find_shortest_path(graph, start, end, path=[]):\n",
    "    path = path + [start]\n",
    "    if start == end:\n",
    "        return path\n",
    "    if not graph.has_key(start):\n",
    "        return None\n",
    "    shortest = None\n",
    "    for node in graph[start]:\n",
    "        if node not in path:\n",
    "            newpath = find_shortest_path(graph, node, end, path)\n",
    "            if newpath:\n",
    "                if not shortest or len(newpath) < len(shortest):\n",
    "                    shortest = newpath\n",
    "    return shortest\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    print find_path(graph, 'A', 'D')\n",
    "    print find_all_paths(graph, 'A', 'D')\n",
    "    print find_shortest_path(graph, 'A', 'D')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from pylab import *\n",
    "\n",
    "INFINITY = 65535                        #代表无穷大\n",
    "D = array([[0,10,INFINITY,INFINITY,INFINITY,11,INFINITY,INFINITY,INFINITY],#邻接矩阵\n",
    "        [10,0,18,INFINITY,INFINITY,INFINITY,16,INFINITY,12],\n",
    "        [INFINITY,18,0,22,INFINITY,INFINITY,INFINITY,INFINITY,8],\n",
    "        [INFINITY,INFINITY,22,0,20,INFINITY,INFINITY,16,21],\n",
    "        [INFINITY,INFINITY,INFINITY,20,0,26,INFINITY,7,INFINITY],\n",
    "        [11,INFINITY,INFINITY,INFINITY,26,0,17,INFINITY,INFINITY],\n",
    "        [INFINITY,16,INFINITY,24,INFINITY,17,0,19,INFINITY],\n",
    "        [INFINITY,INFINITY,INFINITY,16,7,INFINITY,19,0,INFINITY],\n",
    "        [INFINITY,12,8,21,INFINITY,INFINITY,INFINITY,INFINITY,0]])\n",
    "lengthD = len(D)                    #邻接矩阵大小\n",
    "p = list(range(lengthD))\n",
    "P = []\n",
    "for i in range(lengthD):\n",
    "    P.append(p)\n",
    "P = array(P)\n",
    "\n",
    "for i in range(lengthD):\n",
    "    for j in range(lengthD):\n",
    "        for k in range(lengthD):\n",
    "            if(D[i,j] > D[i,k]+D[j,k]):         #两个顶点直接较小的间接路径替换较大的直接路径\n",
    "                P[i,j] = P[j,k]                 #记录新路径的前驱\n",
    "print(P)\n",
    "print(D)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}