Last active
April 4, 2018 08:04
-
-
Save zhu327/a48125753ed12acb5ad386f1a26ccd20 to your computer and use it in GitHub Desktop.
data structure
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| # coding: utf-8 | |
| u""" | |
| 线性数据结构, 栈, 队列, deques, 容器结构, 数据项之间存在相对的位置 | |
| """ | |
| class Stack(object): | |
| u""" | |
| 栈 先进后出 | |
| """ | |
| def __init__(self): | |
| self.items = [] | |
| def push(self, item): | |
| self.items.append(item) # O(1) | |
| def pop(self): | |
| return self.items.pop() # O(1) | |
| def peek(self): | |
| return self.items[-1] | |
| def isEmpty(self): | |
| return self.items == [] | |
| def size(self): | |
| return len(self.items) | |
| u""" | |
| 全括号匹配 | |
| ((())) | |
| ()(())() | |
| """ | |
| def parChecker(symbolString): | |
| stack = Stack() | |
| index = 0 | |
| while index < len(symbolString): | |
| sym = symbolString[index] | |
| if sym == '(': | |
| stack.push(sym) | |
| else: | |
| if stack.isEmpty(): | |
| return False | |
| else: | |
| stack.pop() | |
| index += 1 | |
| if stack.isEmpty(): | |
| return True | |
| return False | |
| u""" | |
| 代码括号匹配 | |
| """ | |
| def codeChecker(symbolString): | |
| stack = Stack() | |
| index = 0 | |
| while index < len(symbolString): | |
| sym = symbolString[index] | |
| if sym in '([{': | |
| stack.push(sym) | |
| elif sym in ')]}': | |
| if stack.isEmpty(): | |
| return False | |
| else: | |
| if not matches(stack.pop(), sym): | |
| return False | |
| index += 1 | |
| if stack.isEmpty(): | |
| return True | |
| return False | |
| def matches(open, close): | |
| opens = '([{' | |
| closes = ')]}' | |
| return opens.index(open) == closes.index(close) | |
| u""" | |
| 任意进制转换 | |
| """ | |
| def baseConverter(decNumber, base): | |
| digits = '0123456789ABCDEF' | |
| stack = Stack() | |
| while decNumber > 0: | |
| stack.push(digits[decNumber % base]) | |
| decNumber = decNumber // base | |
| string = '' | |
| while not stack.isEmpty(): | |
| string += stack.pop() | |
| return string | |
| class Queue(object): | |
| u""" | |
| 队列 先进先出 | |
| """ | |
| def __init(self): | |
| self.items = [] | |
| def isEmpty(self): | |
| return self.items == [] | |
| def size(self): | |
| return len(self.items) | |
| def enqueue(self, item): | |
| self.items.insert(0, item) # O(n) | |
| def dequeue(self): | |
| return self.items.pop() # O(1) | |
| u""" | |
| 烫手山芋 循环传递n次 淘汰一个 直到最后幸存一个 | |
| """ | |
| def hotPotato(namelist, num): | |
| queue = Queue() | |
| for name in namelist: | |
| queue.enqueue(name) | |
| while queue.size() > 1: | |
| for i in range(num): | |
| queue.enqueue(queue.dequeue()) | |
| queue.dequeue() | |
| return queue.dequeue() | |
| class Deque(object): | |
| u""" | |
| 双端队列 可以同时从2端 进出 | |
| """ | |
| def __init__(self): | |
| self.items = [] | |
| def isEmpty(self): | |
| return self.items == [] | |
| def size(self): | |
| return len(self.items) | |
| def addFront(self, item): | |
| self.items.insert(0, item) # O(n) | |
| def removeFront(self): | |
| return self.items.pop(0) # O(n) | |
| def addRear(self, item): | |
| self.items.append(item) # O(1) | |
| def removeRear(self): | |
| return self.items.pop() # O(1) | |
| u""" | |
| 回文检查 字符串前后一致 | |
| """ | |
| def palchecker(aString): | |
| deque = Deque() | |
| for i in aString: | |
| deque.addRear(i) | |
| while deque.size() > 1: | |
| if deque.removeFront() != deque.removeRear(): | |
| return False | |
| return True | |
| u""" | |
| 链表 节点包含数据本身，并保存指向下一个节点的指针 | |
| """ | |
| class Node(object): | |
| def __init__(self, initdata): | |
| self.data = initdata | |
| self.next = None | |
| def getData(self): | |
| return self.data | |
| def getNext(self): | |
| return self.next | |
| def setData(self, data): | |
| self.data = data | |
| def setNext(self, node): | |
| self.next = node | |
| u""" | |
| 无序链表 | |
| """ | |
| class UnorderedList(object): | |
| def __init__(self): | |
| self.head = None | |
| def isEmpty(self): # O(1) | |
| return self.head == None | |
| def add(self, item): # O(1) | |
| node = Node(item) | |
| node.setNext(self.head) | |
| self.head = node | |
| def size(self): # 遍历链 O(n) | |
| count = 0 | |
| current = self.head | |
| while current: | |
| count += 1 | |
| current = current.getNext() | |
| return count | |
| def search(self, item): # O(n) | |
| current = self.head | |
| while current: | |
| if current.getData() == item: | |
| return True | |
| current = current.getNext() | |
| return False | |
| def remove(self, item): # O(n) | |
| previous = None | |
| current = self.head | |
| while current: | |
| if current.getData() == item: | |
| if previous is None: | |
| self.head = current.getNext() | |
| else: | |
| previous.setNext(current.getNext()) | |
| return | |
| previous = current | |
| current = current.getNext() | |
| def append(self, item): # O(n) | |
| node = Node(item) | |
| if self.head is None: | |
| self.head = node | |
| return | |
| current = self.head | |
| while current.getNext(): | |
| current = current.getNext() | |
| current.setNext(node) | |
| def index(self, item): # O(n) | |
| count = 0 | |
| current = self.head | |
| while current: | |
| if current.getData() == item: | |
| return count | |
| current = current.getNext() | |
| count += 1 | |
| def insert(self, pos, item): # O(k) | |
| node = Node(item) | |
| current = self.head | |
| previous = None | |
| for _ in range(pos): | |
| previous = current | |
| current = current.getNext() | |
| node.setNext(current) | |
| if previous is None: | |
| self.head = node | |
| else: | |
| previous.setNext(node) | |
| def pop(self, pos=None): # O(n) | |
| current = self.head | |
| previous = None | |
| if pos is None: | |
| while current.getNext(): | |
| previous = current | |
| current = current.getNext() | |
| else: | |
| for _ in range(pos): | |
| previous = current | |
| current = current.getNext() | |
| if previous is None: | |
| self.head = current.getNext() | |
| else: | |
| previous.setNext(current.getNext()) | |
| return current.getData() | |
| u""" | |
| 有序链表 | |
| """ | |
| class OrderedList(UnorderedList): | |
| def add(self, item): # O(n) | |
| previous = None | |
| current = self.head | |
| while current: | |
| if current.getData() > item: | |
| break | |
| previous = current | |
| current = current.getNext() | |
| node = Node(item) | |
| node.setNext(current) | |
| if previous is None: | |
| self.head = node | |
| else: | |
| previous.setNext(node) | |
| def search(self, item): # O(n) | |
| current = self.head | |
| while current: | |
| if current.getData() == item: | |
| return True | |
| elif current.getData() > item: | |
| break | |
| current = current.getNext() | |
| return False | |
| u""" | |
| 递归 | |
| 1. 递归算法必须具有基本情况 | |
| 2. 递归算法必须改变状态并靠近其基本情况 | |
| 3. 递归算法必须递归方式调用自身 | |
| """ | |
| u""" | |
| 递归算法 整数转字符串 | |
| """ | |
| def toStr(n, base): | |
| digits = '0123456789ABCDEF' | |
| if n < base: | |
| return digits[n] | |
| else: | |
| return toStr(n // base, base) + digits[n % base] | |
| u""" | |
| 河内塔 | |
| 1. 把上层的所有盘子移动到中间 | |
| 2. 把最后一个移动到目标 | |
| 3. 把中间的所有盘子移动到目标 | |
| """ | |
| def moveTower(height, fromPole, toPole, withPole): | |
| if height >= 1: | |
| moveTower(height-1, fromPole, withPole, toPole) | |
| moveDisk(fromPole, toPole) | |
| moveTower(height-1, withPole, toPole, fromPole) | |
| def moveDisk(fp,tp): | |
| print 'move disk from ' + fp + ' to ' + tp | |
| u""" | |
| 探索迷宫 | |
| 1. 向北边走一格, 递归 | |
| 2. 如果向北不能走, 向南走一格, 递归 | |
| 3. 如果向南不能走, 向东走一格, 递归 | |
| 4. 如果向东不能走, 向西走一格, 递归 | |
| 先走一格, 然后继续向不同方向递归, 直到找到出口 | |
| def searchFrom(maze, startRow, startColumn): | |
| maze.updatePosition(startRow, startColumn) | |
| # Check for base cases: | |
| # 1. We have run into an obstacle, return false | |
| if maze[startRow][startColumn] == OBSTACLE : # 碰到墙壁 | |
| return False | |
| # 2. We have found a square that has already been explored | |
| if maze[startRow][startColumn] == TRIED: # 已经来过 | |
| return False | |
| # 3. Success, an outside edge not occupied by an obstacle | |
| if maze.isExit(startRow,startColumn): | |
| maze.updatePosition(startRow, startColumn, PART_OF_PATH) | |
| return True # 判断为出口 | |
| maze.updatePosition(startRow, startColumn, TRIED) # 设置来过 | |
| # Otherwise, use logical short circuiting to try each | |
| # direction in turn (if needed) | |
| found = searchFrom(maze, startRow-1, startColumn) or \ | |
| searchFrom(maze, startRow+1, startColumn) or \ | |
| searchFrom(maze, startRow, startColumn-1) or \ | |
| searchFrom(maze, startRow, startColumn+1) | |
| if found: | |
| maze.updatePosition(startRow, startColumn, PART_OF_PATH) | |
| else: | |
| maze.updatePosition(startRow, startColumn, DEAD_END) | |
| return found | |
| """ | |
| u""" | |
| 动态规划 | |
| 硬币找零问题 找到最小可能的硬币数 | |
| """ | |
| def recMC(coinValueList, change): | |
| minCoins = change | |
| if change in coinValueList: | |
| return 1 | |
| else: | |
| for i in [c for c in coinValueList if c <= change]: | |
| num = 1 + recMC(coinValueList, change-i) | |
| if num < minCoins: | |
| minCoins = num | |
| return minCoins | |
| u""" | |
| 以上算法由于计算了大量的重复数据, 所以低效, 可以对已有的数据缓存, 避免重复计算 | |
| 从顶至下 | |
| """ | |
| def recDC(coinValueList, change, knownResults): | |
| minCoins = change | |
| if change in coinValueList: | |
| knownResults[change] = 1 | |
| return 1 | |
| elif knownResults[change] > 0: | |
| return knownResults[change] | |
| else: | |
| for i in [c for c in coinValueList if c <= change]: | |
| num = 1 + recDC(coinValueList, change-i, knownResults) | |
| if num < minCoins: | |
| minCoins = num | |
| knownResults[change] = minCoins | |
| return minCoins | |
| u""" | |
| 动态规划 | |
| 1. 最小最优解 | |
| 2. 从小到大, 使用已有的计算结果， 从底至上 | |
| """ | |
| def dpMakeChange(coinValueList, change, minCoins, coinsUsed): | |
| for cents in range(change+1): | |
| coinCount = cents | |
| newCoin = 1 | |
| for i in [c for c in coinValueList if c <= cents]: | |
| if minCoins[cents-i] + 1 < coinCount: | |
| coinCount = minCoins[cents-i] + 1 | |
| newCoin = i | |
| minCoins[cents] = coinCount | |
| coinsUsed[cents] = newCoin | |
| return minCoins[change] | |
| # 打印最佳组合的各个值 | |
| def printCoins(coinsUsed, change): | |
| l = [] | |
| while change: | |
| l.append(coinsUsed[change]) | |
| change -= coinsUsed[change] | |
| print l | |
| u""" | |
| 背包问题 | |
| n=5是物品的数量，c=10是书包能承受的重量，w=[2,2,6,5,4]是每个物品的重量，v=[6,3,5,4,6]是每个物品的价值 | |
| """ | |
| def bag(n, c, w, v): | |
| res=[[-1 for j in range(c + 1)] for i in range(n + 1)] | |
| for j in range(c + 1): | |
| res[0][j]=0 # 把第一列初始化 0 | |
| for i in range(1, n + 1): # 行 1~5 | |
| for j in range(1, c + 1): # 列 1~10 | |
| res[i][j] = res[i - 1][j] # 先把上一行的值赋值个当前 | |
| if j >= w[i-1] and res[i][j] < res[i-1][j - w[i-1]] + v[i - 1]: | |
| # 如果重量大于物品的行重量且当前价值小于物品价值+前一个物品重量,则重算最大重量 | |
| res[i][j] = res[i-1][j-w[i-1]] + v[i-1] | |
| return res | |
| def show(n, c, w, res): | |
| print '最大价值', res[n][c] | |
| x = [False for _ in w] | |
| j = c | |
| for i in range(1, n+1): | |
| if res[i][j] > res[i-1][j]: | |
| x[i-1] = True | |
| j -= w[i-1] | |
| for i, j in enumerate(x): | |
| if j: | |
| print '第{}个'.format(i+1) | |
| u""" | |
| 二分查找 | |
| """ | |
| def binarySearch(alist, item): | |
| first = 0 | |
| last = len(alist) - 1 | |
| found = False | |
| while first <= last and not found: | |
| mid = first + (last - first) // 2 | |
| if alist[mid] == item: | |
| found = True | |
| elif alist[mid] > item: | |
| last = mid - 1 | |
| else: | |
| first = mid + 1 | |
| return found | |
| # 递归版 | |
| def binarySearch2(alist, item): # O( log^n ) | |
| if len(alist) == 0: | |
| return False | |
| else: | |
| mid = len(alist) // 2 | |
| if alist[mid] == item: | |
| return True | |
| elif alist[mid] > item: | |
| return binarySearch2(alist[:mid], item) | |
| else: | |
| return binarySearch2(alist[mid+1:], item) | |
| u""" | |
| 哈希表 | |
| 1. 大小为m的哈希表，有从0~m-1为编号的槽 可以用数组表示 | |
| 2. 项与编号的映射方法叫 hash 函数，简单的示例可以用取余 | |
| ＊ 如果多个项经过 hash 函数得到的编号相同，则称为碰撞 | |
| ＊ 分组求和 把项的多个数字分组求和再取m的余 | |
| ＊ 平方取中 算项的平方值并去中间的某几位 再取m的余 | |
| 3. 项数/表大小m 的值 称为 负载因子 | |
| 4. 冲突解决 重新散列 | |
| ＊ 开放寻址 如果槽已被占用，则顺序往槽的下一个槽查找，直到找到空槽(线性探测) | |
| ＊ 使用链式存储，在同一个编号上存储多个项 | |
| """ | |
| class HashTable(object): | |
| def __init__(self): | |
| self.size = 11 # 要为质数 | |
| self.slots = [None]*self.size | |
| self.data = [None]*self.size | |
| def _hash(self, key): | |
| return key % self.size | |
| def _rehash(self, oldhash): | |
| return (oldhash+1)%self.size | |
| def put(self, key, data): | |
| hashvalue = self._hash(key) | |
| if self.slots[hashvalue] is None: # 新增 | |
| self.slots[hashvalue] = key | |
| self.data[hashvalue] = data | |
| elif self.slots[hashvalue] == key: # 修改 | |
| self.data[hashvalue] = data | |
| else: | |
| nextslot = self._rehash(hashvalue) | |
| while self.slots[nextslot] != None and self.slots[nextslot] != key: | |
| nextslot = self._rehash(hashvalue) | |
| if self.slots[nextslot] is None: | |
| self.slots[nextslot] = key | |
| self.data[nextslot] = data | |
| def get(self, key): | |
| position = self._get_position(key) | |
| return self.data[position] if position is not None else None | |
| def _get_position(self, key): # 理想的情况下 O(1) 最差 O(n) | |
| startslot = self._hash(key) | |
| position = startslot | |
| while self.slots[position] != None: | |
| if self.slots[position] == key: | |
| return position | |
| else: | |
| position = self._rehash(position) | |
| if position == startslot: | |
| return None | |
| return None | |
| def __getitem__(self, key): | |
| return self.get(key) | |
| def __setitem__(self, key, data): | |
| self.put(key, data) | |
| def __len__(self): | |
| count = 0 | |
| for i in self.slots: | |
| if i is not None: | |
| count += 1 | |
| return count | |
| def __delitem__(self, key): | |
| position = self._get_position(key) | |
| if position is not None: | |
| self.slots[position] = None | |
| self.data[position] = None | |
| def __contains__(self, key): | |
| position = self._get_position(key) | |
| return False if position is None else True | |
| u""" | |
| 冒泡排序 | |
| """ | |
| def bubbleSort(alist): # O(n^2) | |
| for passnum in range(len(alist)-1, 0, -1): | |
| for i in range(passnum): | |
| if alist[i] > alist[i+1]: | |
| alist[i], alist[i+1] = alist[i+1], alist[i] | |
| u""" | |
| 短冒泡排序 | |
| 前一次遍历如果没有发生交换，证明整个序列以排序 | |
| """ | |
| def shortBubbleSort(alist): | |
| passnum = len(alist) - 1 | |
| exchange = True | |
| while passnum > 0 and exchange: | |
| exchange = False | |
| for i in range(passnum): | |
| if alist[i] > alist[i+1]: | |
| exchange = True | |
| alist[i], alist[i+1] = alist[i+1], alist[i] | |
| passnum -= 1 | |
| u""" | |
| 选择排序 | |
| 同冒泡排序，只是减少的交换次数 | |
| """ | |
| def selectionSort(alist): | |
| for passnum in range(len(alist)-1, 0, -1): | |
| maxPositon = 0 | |
| for i in range(1, passnum+1): | |
| if alist[i] > alist[maxPositon]: | |
| maxPositon = i | |
| alist[passnum], alist[maxPositon] = alist[maxPositon], alist[passnum] | |
| u""" | |
| 插入排序 O(n^2) | |
| 维持最小的已排序序列，迭代未排序项，插入到合适的位置 | |
| """ | |
| def insertionSort(alist): | |
| for i in range(1, len(alist)): | |
| current = alist[i] | |
| position = i | |
| while position > 0 and alist[position-1] > current: | |
| alist[position] = alist[position-1] | |
| position -= 1 | |
| alist[position] = current | |
| u""" | |
| shell 排序 | |
| 通过gap间隔来划分子序列，先对所有的子序列进行插入排序，然后再对整个序列插入排序 | |
| O(n^3/2) 稍稍好于插入排序 | |
| """ | |
| def shellSort(alist): | |
| count = len(alist) // 2 # 选择gap | |
| while count > 0: | |
| for i in range(count): | |
| gapInsertionSort(alist, i, count) | |
| count = count // 2 | |
| def gapInsertionSort(alist, start, gap): | |
| for i in range(start+gap, len(alist), gap): | |
| current = alist[i] | |
| position = i | |
| while position > start and alist[position-gap] > current: | |
| alist[position] = alist[position-gap] | |
| position -= gap | |
| alist[position] = current | |
| u""" | |
| 归并排序 | |
| 递归算法，分治，把序列切割成最小的部分并排序，然后逐步合并已排序的结果 O(nlog^n) | |
| """ | |
| def mergeSort(alist): | |
| if len(alist) > 1: | |
| mid = len(alist)//2 # 二分 log^n | |
| left = alist[:mid] | |
| right = alist[mid:] | |
| mergeSort(left) # 递归排序，最小部分为 长度为1的列表 | |
| mergeSort(right) | |
| # 合并已排序的片段 最大花费n次 | |
| i = j = k = 0 | |
| while i < len(left) and j < len(right): | |
| if left[i] < right[j]: | |
| alist[k] = left[i] | |
| i += 1 | |
| else: | |
| alist[k] = right[j] | |
| j += 1 | |
| k += 1 | |
| while i < len(left): | |
| alist[k] = left[i] | |
| i += 1 | |
| k += 1 | |
| while j < len(right): | |
| alist[k] = right[j] | |
| j += 1 | |
| k += 1 | |
| u""" | |
| 快速排序 O(nlogn) | |
| """ | |
| def quickSort(alist): | |
| quickSortHelper(alist,0,len(alist)-1) | |
| def quickSortHelper(alist, first, last): | |
| if first < last: | |
| i, j = first, last | |
| current = alist[first] | |
| while i < j: | |
| while i < j and alist[j] >= current: | |
| j -= 1 | |
| alist[i] = alist[j] | |
| while i < j and alist[i] <= current: | |
| i += 1 | |
| alist[j] = alist[i] | |
| alist[i] = current | |
| quickSortHelper(alist,first,i-1) | |
| quickSortHelper(alist,i+1,last) | |
| u""" | |
| 树 | |
| 节点 树的基础部分 可以有附加属性,称为有效载荷 key | |
| 边 表示节点之间的联系, 除了 根节点 其它节点都有从父节点来的边(传入边) | |
| 根 没有传入边的节点 | |
| 路径 由边连接的节点的有序序列 | |
| 子节点 传入边为相同父节点 | |
| 父节点 | |
| 兄弟 | |
| 子树 由父节点 与 子孙节点组成的一组节点与边 | |
| 叶节点 没有子节点的节点 | |
| 层数 由根到节点之间边的条数 | |
| 高度 最大的叶子节点层数 | |
| 定义 树由一组节点和连接节点的边组成 | |
| - 树的一个节点指定为根节点 | |
| - 除了根,没有节点n通过边与p相连,n是p的子节点 | |
| - 从根遍历到某个节点的路径唯一 | |
| 定义 树是由根与一系列子树组成,子数的根与根相连,递归定义 | |
| """ | |
| u""" | |
| 列表表示 二叉树 | |
| """ | |
| def binaryTree(r): | |
| return [r, [], []] | |
| def insertLeft(root,newBranch): | |
| node = root.pop(1) | |
| if node: | |
| root.insert(1, [newBranch, node, []]) | |
| else: | |
| root.insert(1, [newBranch, [], []]) | |
| return root | |
| def insertRight(root,newBranch): | |
| node = root.pop(2) | |
| if node: | |
| root.insert(2, [newBranch, [], node]) | |
| else: | |
| root.insert(2, [newBranch, [], []]) | |
| return root | |
| def getRootVal(root): | |
| return root[0] | |
| def setRootVal(root,newVal): | |
| root[0] = newVal | |
| def getLeftChild(root): | |
| return root[1] | |
| def getRightChild(root): | |
| return root[2] | |
| u""" | |
| 节点表示 | |
| """ | |
| class BinaryTree(object): | |
| def __init__(self, val): | |
| self.key = val | |
| self.left = None | |
| self.right = None | |
| def insertLeft(self, val): | |
| node = BinaryTree(val) | |
| if self.left is None: | |
| self.left = node | |
| else: | |
| node.left = self.left | |
| self.left = node | |
| def insertRight(self, val): | |
| node = BinaryTree(val) | |
| if self.right is None: | |
| self.right = node | |
| else: | |
| node.right = self.right | |
| self.right = node | |
| def getRootVal(self): | |
| return self.key | |
| def setRootVal(self, val): | |
| self.key = val | |
| def getLeftChild(self): | |
| return self.left | |
| def getRightChild(self): | |
| return self.right | |
| def preorder(self): | |
| print self.key | |
| if self.left: | |
| self.left.preorder() | |
| if self.right: | |
| self.right.preorder() | |
| u""" | |
| 使用树构建数值运算 | |
| ( 1 + ( 4 * 3 ) ) | |
| """ | |
| def buildParseTree(fpexp): | |
| fplist = fpexp.split() | |
| pstack = Stack() | |
| etree = BinaryTree('') | |
| pstack.push(etree) | |
| current = etree | |
| for i in fplist: | |
| if i == '(': | |
| current.insertLeft('') | |
| pstack.push(current) | |
| current = current.getLeftChild() | |
| elif i not in ['+', '-', '*', '*', ')']: | |
| current.setRootVal(int(i)) | |
| current = pstack.pop() | |
| elif i in ['+', '-', '*', '*']: | |
| current.setRootVal(i) | |
| current.insertRight('') | |
| pstack.push(current) | |
| current = current.getRightChild() | |
| elif i == ')': | |
| current = pstack.pop() | |
| print current.getRootVal() | |
| return etree | |
| import operator | |
| u""" | |
| 递归算式树求值 | |
| """ | |
| def evaluate(parseTree): | |
| opers = {'+':operator.add, '-':operator.sub, '*':operator.mul, '/':operator.truediv} | |
| left = parseTree.getLeftChild() | |
| right = parseTree.getRightChild() | |
| if left and right: | |
| fn = opers[parseTree.getRootVal()] | |
| return fn(evaluate(left), evaluate(right)) | |
| else: | |
| return parseTree.getRootVal() | |
| u""" | |
| 树的遍历 | |
| 前序 返问根,递归前序遍历左子树,递归前序遍历右子树 | |
| 中序 递归中序遍历左子树,返问根,递归中序遍历右子树 | |
| 后序 递归后序遍历左子树,递归后序遍历右子树,返问根 | |
| """ | |
| def preorder(tree): # 前序 | |
| if tree: | |
| print tree.getRootVal() | |
| preorder(tree.getLeftChild()) | |
| preorder(tree.getRightChild()) | |
| def postorder(tree): # 后序 | |
| if tree: | |
| postorder(tree.getLeftChild()) | |
| postorder(tree.getRightChild()) | |
| print tree.getRootVal() | |
| u""" | |
| 遍历求值 | |
| """ | |
| def postordereval(tree): | |
| opers = {'+':operator.add, '-':operator.sub, '*':operator.mul, '/':operator.truediv} | |
| res1 = None | |
| res2 = None | |
| if tree: | |
| res1 = postordereval(tree.getLeftChild()) | |
| res2 = postordereval(tree.getRightChild()) | |
| if res1 and res2: | |
| return opers[tree.getRootVal()](res1, res2) | |
| else: | |
| return tree.getRootVal() | |
| def inorder(tree): # 中序 | |
| if tree: | |
| inorder(tree.getLeftChild()) | |
| print tree.getRootVal() | |
| inorder(tree.getRightChild()) | |
| u""" | |
| 打印原始分析树 | |
| """ | |
| def printexp(tree): | |
| s = '' | |
| if tree: | |
| s = '(' + printexp(tree.getLeftChild()) | |
| s = s + tree.getRootVal() | |
| s = printexp(tree.getRightChild()) + ')' | |
| return s | |
| u""" | |
| 二叉堆 最小堆 | |
| 子节点的一定小于父节点，根节点最小 | |
| 每层的最大节点个数为2^h，所以子节点一定是父节点的2n 2n＋1 | |
| """ | |
| class BinHeap(object): | |
| def __init__(self): | |
| self.heapList = [0] | |
| self.currentSize = 0 | |
| def insert(self, i): # O(log2^n) | |
| self.heapList.append(i) | |
| self.currentSize += 1 | |
| i = self.currentSize | |
| j = i // 2 # 找到父节点的位置 | |
| while j > 0: # 对比交换 | |
| if self.heapList[i] < self.heapList[j]: | |
| self.heapList[i], self.heapList[j] = self.heapList[j], self.heapList[i] | |
| i = j | |
| j = j // 2 | |
| def delMin(self): # O(log2^n) | |
| minVal = self.heapList[1] | |
| self.heapList[1] = self.heapList[-1] | |
| self.currentSize -= 1 | |
| self.heapList.pop() # 删除最小,把最大的移动到根 | |
| self._percDown(1) # 遍历比较，把合适的移动到根 | |
| return minVal | |
| def _minChild(self, i): | |
| if (i * 2) + 1 > self.currentSize: | |
| return i * 2 | |
| elif self.heapList[i*2] > self.heapList[i*2+1]: | |
| return i * 2 + 1 | |
| else: | |
| return i * 2 | |
| def _percDown(self, i): | |
| while (i * 2) <= self.currentSize: | |
| mc = self._minChild(i) | |
| if self.heapList[i] > self.heapList[mc]: | |
| self.heapList[i], self.heapList[mc] = self.heapList[mc], self.heapList[i] | |
| i = mc | |
| def buildHeap(self, alist): # O(n) | |
| self.currentSize = len(alist) | |
| self.heapList = [0] + alist[:] | |
| i = self.currentSize // 2 | |
| while i > 0: | |
| self._percDown(i) | |
| i -= 1 | |
| def isEmpty(self): | |
| return True if self.currentSize == 0 else False | |
| def size(self): | |
| return self.currentSize | |
| u""" | |
| 最大堆 | |
| """ | |
| class MaxBinHeap(object): | |
| def __init__(self): | |
| self.heapList = [0] | |
| self.currentSize = 0 | |
| def insert(self, i): | |
| self.heapList.append(i) | |
| self.currentSize += 1 | |
| i = self.currentSize | |
| j = i // 2 | |
| while j > 0: | |
| if self.heapList[i] > self.heapList[j]: | |
| self.heapList[i], self.heapList[j] = self.heapList[j], self.heapList[i] | |
| i = j | |
| j = j // 2 | |
| def delMax(self): | |
| maxVal = self.heapList[1] | |
| self.heapList[1] = self.heapList[-1] | |
| self.currentSize -= 1 | |
| self.heapList.pop() | |
| self._percUp(1) | |
| return maxVal | |
| def _maxChild(self, i): | |
| if (i * 2) + 1 > self.currentSize: | |
| return i * 2 | |
| elif self.heapList[i*2] < self.heapList[i*2+1]: | |
| return i * 2 + 1 | |
| else: | |
| return i * 2 | |
| def _percUp(self, i): | |
| while (i * 2) <= self.currentSize: | |
| mc = self._maxChild(i) | |
| if self.heapList[i] < self.heapList[mc]: | |
| self.heapList[i], self.heapList[mc] = self.heapList[mc], self.heapList[i] | |
| i = mc | |
| def buildHeap(self, alist): | |
| self.currentSize = len(alist) | |
| self.heapList = [0] + alist[:] | |
| i = self.currentSize // 2 | |
| while i > 0: | |
| self._percUp(i) | |
| i -= 1 | |
| def isEmpty(self): | |
| return True if self.currentSize == 0 else False | |
| def size(self): | |
| return self.currentSize | |
| u""" | |
| 堆排序 | |
| 构建最大堆 | |
| 把根交换到最后 | |
| 递归n－1构建最大堆，交换 O(nlogn) | |
| """ | |
| def heap_sort(lst): | |
| def sift_down(start, end): | |
| root = start | |
| while 1: | |
| child = 2 * root + 1 | |
| if child > end: | |
| break | |
| if child + 1 < end and lst[child] < lst[child+1]: | |
| child = child + 1 | |
| if lst[root] < lst[child]: | |
| lst[root], lst[child] = lst[child], lst[root] | |
| root = child | |
| else: | |
| break | |
| i = len(lst) // 2 # 构建最大堆 | |
| while i >= 0: | |
| sift_down(i, len(lst) - 1) | |
| i -= 1 | |
| for end in range(len(lst) - 1, 0, -1): | |
| lst[0], lst[end] = lst[end], lst[0] # 交换，重复构建 | |
| sift_down(0, end-1) | |
| u""" | |
| 二叉搜索树 | |
| 节点的左子节点必须小于节点的key | |
| 节点的右子节点必须大于节点的key | |
| get put delete 都是遍历高度 O(log2^n) | |
| 如果输入是有序的,那么就是最坏的结果O(n), 因为只会遍历左边或者右边 | |
| """ | |
| class BinarySearchTree(object): | |
| def __init__(self): | |
| self.root = None | |
| self.size = 0 | |
| def length(self): | |
| return self.size | |
| def __len__(self): | |
| return self.size | |
| def __iter__(self): | |
| return self.root.__iter__() | |
| def put(self, key, val): # 复杂度在于树的高度 O(log2^n) | |
| if self.root is None: | |
| self.root = TreeNode(key, val) | |
| else: | |
| self._put(key, val, self.root) | |
| self.size += 1 | |
| def _put(self, key, val, current): | |
| if key > current.key: | |
| if current.hasRightChild(): | |
| self._put(key, val, current.right) | |
| else: | |
| current.right = TreeNode(key, val, parent=current) | |
| elif key < current.key: | |
| if current.hasLeftChild(): | |
| self._put(key, val, current.left) | |
| else: | |
| current.left = TreeNode(key, val, parent=current) | |
| else: | |
| current.playload = val # key 相同时 直接替换值 | |
| def __setitem__(self, k, v): | |
| self.put(k, v) | |
| def get(self, key): # O(log2^n) | |
| if self.root: | |
| node = self._get(key, self.root) | |
| if node: | |
| return node.playload | |
| return None | |
| def _get(self, key, current): | |
| if not current: | |
| return None | |
| elif key > current.key: | |
| return self._get(key, current.right) | |
| elif key < current.key: | |
| return self._get(key, current.left) | |
| else: | |
| return current | |
| def __getitem__(self, k): | |
| return self.get(k) | |
| def __contains__(self, k): | |
| return bool(self._get(k, self.root)) | |
| def __delitem__(self, k): | |
| self.delete(k) | |
| def delete(self, key): # 虽然很复杂, 但是实际上向下遍历找到合适的节点, 所有最大还是高度 O(log2^n) | |
| if self.size > 1: | |
| node = self._get(key, self.root) | |
| if node: | |
| self.removeNode(node) | |
| self.size -= 1 | |
| else: | |
| raise KeyError(key) | |
| elif self.size == 1 and self.root.key == key: | |
| self.root = None | |
| self.size -= 1 | |
| else: | |
| raise KeyError(key) | |
| def removeNode(self, current): | |
| if current.isLeaf(): # 如果是叶子节点,直接删除 | |
| if current.isLeftChild(): | |
| current.parent.left = None | |
| else: | |
| current.parent.right = None | |
| elif current.hasBothChildren(): # 有2个子节点 | |
| succ = current.findSuccessor() | |
| succ.spliceOut() | |
| current.key = succ.key | |
| current.playload = succ.key | |
| else: # 有1个子节点 | |
| if current.hasLeftChild(): # 有左节点 | |
| if current.isLeftChild(): | |
| current.parent.left = current.left | |
| current.left.parent = current.parent | |
| elif current.isRightChild(): | |
| current.parent.right = current.left | |
| current.left.parent = current.parent | |
| else: # 根节点,直接使用子节点的数据替换自己 | |
| current.replaceNodeData(current.left.key, current.left.playload, | |
| current.left.left, current.left.right) | |
| else: | |
| if current.isLeftChild(): | |
| current.parent.left = current.right | |
| current.right.parent = current.parent | |
| elif current.isRightChild(): | |
| current.parent.right = current.right | |
| current.right.parent = current.parent | |
| else: # 根节点 | |
| current.replaceNodeData(current.right.key, current.right.playload, | |
| current.right.left, current.right.right) | |
| class TreeNode(object): | |
| def __init__(self, key, val, left=None, right=None, parent=None): | |
| self.key = key | |
| self.playload = val | |
| self.left = left | |
| self.right = right | |
| self.parent = parent | |
| self.balanceFactor = 0 | |
| def hasLeftChild(self): | |
| return self.left | |
| def hasRightChild(self): | |
| return self.right | |
| def isLeftChild(self): | |
| return self.parent and self.parent.hasLeftChild() == self | |
| def isRightChild(self): | |
| return self.parent and self.parent.hasRightChild() == self | |
| def isRoot(self): | |
| return not self.parent | |
| def isLeaf(self): | |
| return not (self.left and self.right) | |
| def hasAnyChildren(self): | |
| return self.left or self.right | |
| def hasBothChildren(self): | |
| return self.left and self.right | |
| def replaceNodeData(self, key, value, lc, rc): | |
| self.key = key | |
| self.playload = value | |
| self.left = lc | |
| self.right = rc | |
| if self.hasLeftChild(): | |
| self.left.parent = self | |
| if self.hasRightChild(): | |
| self.right.parent = self | |
| def findSuccessor(self): | |
| succ = None | |
| if self.hasRightChild(): | |
| return self.right.findMin() | |
| else: | |
| if self.parent: | |
| if self.isLeftChild(): | |
| succ = self.parent | |
| else: # 如果没有右节点, 且自己是右节点, 父节点小于自己, 遍历向上找 | |
| self.parent.right = None # 可以肯定的是节点 右边节点一定会大于节点本身 | |
| succ = self.parent.findSuccessor() | |
| self.parent.right = self | |
| return succ | |
| def findMin(self): | |
| current = self | |
| while current.hasLeftChild(): | |
| current = current.left | |
| return current | |
| def spliceOut(self): | |
| if self.isLeaf(): | |
| if self.isLeftChild(): | |
| self.parent.left = None | |
| else: | |
| self.parent.right = None | |
| elif self.hasLeftChild(): | |
| if self.isLeftChild(): | |
| self.parent.left = self.left | |
| else: | |
| self.parent.right = self.left | |
| self.left.parent = self.parent | |
| else: | |
| if self.isLeftChild(): | |
| self.parent.left = self.right | |
| else: | |
| self.parent.right = self.right | |
| self.right.parent = self.parent | |
| def __iter__(self): | |
| if self: | |
| if self.hasLeftChild(): | |
| for ele in self.left: | |
| yield ele | |
| yield self.key | |
| if self.hasRightChild(): | |
| for ele in self.right: | |
| yield ele | |
| u""" | |
| 平衡二叉树 | |
| AVL树 自动保持平衡的树 | |
| 平衡 根的左子树与右子树的高度差不超过1 | |
| """ | |
| class AvlTree(BinarySearchTree): | |
| def _put(self, key, val, current): | |
| if key > current.key: | |
| if current.hasRightChild(): | |
| self._put(key, val, current.right) | |
| else: | |
| current.right = TreeNode(key, val, parent=current) | |
| self.updateBalance(current.right) | |
| elif key < current.key: | |
| if current.hasLeftChild(): | |
| self._put(key, val, current.left) | |
| else: | |
| current.left = TreeNode(key, val, parent=current) | |
| self.updateBalance(current.left) | |
| else: | |
| current.playload = val | |
| def updateBalance(self, node): | |
| u""" | |
| 1. 递归调用到树的根，直到找到平衡因子大于1的节点 | |
| 2. 父节点的平衡因子已调整为零。你应该说服自己，一旦一个子树的平衡因子为零，那么它的祖先节点的平衡不会改变。 | |
| """ | |
| if node.balanceFactor > 1 or node.balanceFactor < -1: | |
| self.rebalance(node) # 通过旋转可以保证节点平衡因子为0 | |
| return | |
| if node.parent != None: | |
| if node.isLeftChild(): | |
| node.parent.balanceFactor += 1 | |
| elif node.isRightChild(): | |
| node.parent.balanceFactor -= 1 | |
| if node.parent.balanceFactor != 0: | |
| self.updateBalance(node.parent) | |
| def rebalance(self, node): | |
| if node.balanceFactor < 0: | |
| if node.right.balanceFactor > 0: | |
| self.rotateRight(node.right) | |
| self.rotateLeft(node) | |
| elif node.balanceFactor > 0: | |
| if node.left.balanceFactor < 0: | |
| self.rotateLeft(node.left) | |
| self.rotateRight(node) | |
| def rotateLeft(self, rotRoot): # 左旋转 | |
| u""" | |
| 1. 提升右孩子（B）成为子树的根。 | |
| 2. 将旧根（A）移动为新根的左子节点。 | |
| 3. 如果新根（B）已经有一个左孩子，那么使它成为新左孩子（A）的右孩子。 | |
| 注意：由于新根（B）是A的右孩子，A 的右孩子在这一点上保证为空。 | |
| 这允许我们添加一个新的节点作为右孩子，不需进一步的考虑。 | |
| """ | |
| newRoot = rotRoot.right # 右节点为新根 | |
| rotRoot.right = newRoot.left # 新根的左节点称为旧根的右节点 | |
| if newRoot.hasLeftChild(): | |
| newRoot.left.parent = rotRoot | |
| newRoot.parent = rotRoot.parent | |
| if rotRoot.isRoot(): | |
| self.root = newRoot | |
| else: | |
| if rotRoot.isLeftChild(): | |
| rotRoot.parent.left = newRoot | |
| elif rotRoot.isRightChild(): | |
| rotRoot.parent.right = newRoot | |
| newRoot.left = rotRoot | |
| rotRoot.parent = newRoot | |
| rotRoot.balanceFactor = rotRoot.balanceFactor + 1 - min(newRoot.balanceFactor, 0) | |
| newRoot.balanceFactor = newRoot.balanceFactor + 1 + max(rotRoot.balanceFactor, 0) | |
| def rotateRight(self, rotRoot): # 右旋转 | |
| newRoot = rotRoot.left | |
| rotRoot.left = newRoot.right | |
| if newRoot.hasRightChild(): | |
| newRoot.right.parent = rotRoot | |
| newRoot.parent = rotRoot.parent | |
| if rotRoot.isRoot(): | |
| self.root = newRoot | |
| else: | |
| if rotRoot.isLeftChild(): | |
| rotRoot.parent.left = newRoot | |
| elif rotRoot.isRightChild(): | |
| rotRoot.parent.right = newRoot | |
| newRoot.right = rotRoot | |
| rotRoot.parent = newRoot | |
| rotRoot.balanceFactor = rotRoot.balanceFactor + 1 - min(newRoot.balanceFactor, 0) | |
| newRoot.balanceFactor = newRoot.balanceFactor + 1 + max(rotRoot.balanceFactor, 0) | |
| u""" | |
| 图 | |
| 顶点 同树中的节点 | |
| 边 连接2个顶点,可以是多个方向的,如果图中边都只有一个方法,则称为有向图 | |
| 权重 边可以被加权,表示顶点到顶点过去的成本 | |
| 路径 由边连接的顶点的序列, 未加权的路径长度n-1, 加权的为路径所有边权重的和 | |
| 循环 有向图的循环是同一顶点为起点和终点的路径, 没有循环的图称为非循环图形, 没有循环的有向图称为无环图 DAG | |
| 图 是由顶点集合与边集合组成的 G = (V, E) G 图 V 顶点集合 E 边的集合 | |
| """ | |
| u""" | |
| 邻接矩阵 | |
| 行与列存储了图的顶点,行与列的单元格存了边的加权值,如果2个顶点间的单元格值,则2个顶点相邻 | |
| 由于存在很多的空单元格,大部分情况下矩阵是稀疏的,但是对于边很多的情况下,领接矩阵很适合 | |
| 领接表 | |
| 适用于边很稀疏的情况 | |
| 对应于列的顶点列表,对每个顶点维护一个边的列表,保存了顶点与权重 | |
| 空间更高效,并且保存了顶点直接连接的其它顶点 | |
| """ | |
| import sys | |
| class Vertex: | |
| def __init__(self,num): | |
| self.id = num | |
| self.connectedTo = {} | |
| self.color = 'white' # 是否已访问 white 未访问 gray 正在访问 black 已访问 | |
| self.dist = sys.maxsize | |
| self.pred = None # 上级顶点 | |
| self.disc = 0 # 距离开始顶点的距离或者顶点标识为 gray 的时间 | |
| self.fin = 0 # 顶点标识为 black 的时间 | |
| def addNeighbor(self,nbr,weight=0): | |
| self.connectedTo[nbr] = weight | |
| def setColor(self,color): | |
| self.color = color | |
| def setDistance(self,d): | |
| self.dist = d | |
| def setPred(self,p): | |
| self.pred = p | |
| def setDiscovery(self,dtime): | |
| self.disc = dtime | |
| def setFinish(self,ftime): | |
| self.fin = ftime | |
| def getFinish(self): | |
| return self.fin | |
| def getDiscovery(self): | |
| return self.disc | |
| def getPred(self): | |
| return self.pred | |
| def getDistance(self): | |
| return self.dist | |
| def getColor(self): | |
| return self.color | |
| def getConnections(self): | |
| return self.connectedTo.keys() | |
| def getWeight(self,nbr): | |
| return self.connectedTo[nbr] | |
| def getId(self): | |
| return self.id | |
| class Graph(object): | |
| def __init__(self): | |
| self.vertList = {} | |
| self.numVertices = 0 | |
| def addVertex(self, key): | |
| ver = Vertex(key) | |
| self.numVertices += 1 | |
| self.vertList[key] = ver | |
| return ver | |
| def getVertex(self, n): | |
| if n in self.vertList: | |
| return self.vertList[n] | |
| return None | |
| def __contains__(self, n): | |
| return n in self.vertList | |
| def addEdge(self, f, t, cost=0): | |
| if f not in self.vertList: | |
| self.addVertex(f) | |
| if t not in self.vertList: | |
| self.addVertex(t) | |
| self.vertList[f].addNeighbor(self.vertList[t], cost) | |
| def getVertices(self): | |
| return self.vertList.keys() | |
| def __iter__(self): | |
| return iter(self.vertList.values()) | |
| u""" | |
| 构建字梯图 | |
| """ | |
| def buildGraph(words): # O(n^2) | |
| d = {} | |
| g = Graph() | |
| for word in words: | |
| for i in range(len(word)): | |
| bucket = word[:i] + '_' + word[i+1:] | |
| if bucket in d: | |
| d[bucket].append(word) | |
| else: | |
| d[bucket] = [word] | |
| for bucket in d.keys(): | |
| for word1 in d[bucket]: | |
| for word2 in d[bucket]: | |
| if word1 != word2: | |
| g.addEdge(word1, word2) | |
| return g | |
| u""" | |
| 广度优先 BFS | |
| """ | |
| def bfs(start): # O(V) 每个顶点只会访问一次 | |
| start.setDistance(0) | |
| start.setPred(None) | |
| vertQueue = Queue() | |
| vertQueue.enqueue(start) | |
| while (vertQueue.size() > 0): | |
| currentVert = vertQueue.dequeue() | |
| for nbr in currentVert.getConnections(): | |
| if (nbr.getColor() == 'white'): | |
| nbr.setColor('gray') | |
| nbr.setDistance(currentVert.getDistance() + 1) | |
| nbr.setPred(currentVert) | |
| vertQueue.enqueue(nbr) | |
| currentVert.setColor('black') | |
| def traverse(y): # 反向追踪找到路径 | |
| x = y | |
| while x.getPred(): | |
| print x.getId() | |
| x = x.getPred() | |
| u""" | |
| 骑士之旅 | |
| 棋盘上的每个单元格都需要访问到 | |
| """ | |
| def knightGraph(bdSize): | |
| graph = Graph() | |
| for row in range(bdSize): | |
| for col in range(bdSize): | |
| nodeId = posToNodeId(row, col, bdSize) | |
| newPositions = genLegalMoves(row, col, bdSize) | |
| for e in newPositions: | |
| nid = posToNodeId(e[0], e[1], bdSize) | |
| graph.addEdge(nodeId, nid) | |
| return graph | |
| def posToNodeId(row, column, board_size): | |
| return (row * board_size) + column | |
| def genLegalMoves(x, y, bdSize): | |
| newMoves = [] | |
| moveOffsets = [(-1,-2),(-1,2),(-2,-1),(-2,1), | |
| ( 1,-2),( 1,2),( 2,-1),( 2,1)] | |
| for i in moveOffsets: | |
| newX = x + i[0] | |
| newY = y + i[1] | |
| if legalCoord(newX, bdSize) and \ | |
| legalCoord(newY, bdSize): | |
| newMoves.append((newX, newY)) | |
| return newMoves | |
| def legalCoord(x, bdSize): | |
| if x >= 0 and x < bdSize: | |
| return True | |
| return False | |
| u""" | |
| 深度优先 DFS | |
| """ | |
| def knightTour(n, path, u, limit): | |
| u""" | |
| n: 搜索树中当前深度 | |
| path: 搜索路径节点列表 | |
| u: 希望找到的顶点 | |
| limit: 路径中的节点数，最大的深度 | |
| """ | |
| u.setColor('gray') | |
| path.append(u) | |
| if n < limit: | |
| # nbrList = list(u.getConnections()) | |
| nbrList = orderByAvail(u) | |
| i = 0 | |
| done = False | |
| while i < len(nbrList) and not done: | |
| if nbrList[i].getColor() == 'white': | |
| done = knightTour(n+1, path, nbrList[i], limit) | |
| i = i + 1 | |
| if not done: # prepare to backtrack | |
| path.pop() | |
| u.setColor('white') # 回溯，遍历下一个邻居 | |
| else: | |
| done = True | |
| return done | |
| u""" | |
| 启发式 | |
| 倾向与先遍历到有较少的可选的节点，这样骑士会先覆盖棋盘周边的方格，然后向中间， | |
| 避免在中间路径过多的选择, 由中间向周边发散会产生更多的短路径 | |
| """ | |
| def orderByAvail(n): | |
| resList = [] | |
| for v in n.getConnections(): | |
| if v.getColor() == 'white': | |
| c = 0 | |
| for w in v.getConnections(): | |
| if w.getColor() == 'white': | |
| c = c + 1 | |
| resList.append((c,v)) | |
| resList.sort(key=lambda x: x[0]) | |
| return [y[1] for y in resList] | |
| class DFSGraph(Graph): | |
| def __init__(self): | |
| super(DFSGraph, self).__init__() | |
| self.time = 0 | |
| def dfs(self): | |
| for aVertex in self: | |
| aVertex.setColor('white') | |
| aVertex.setPred(-1) | |
| for aVertex in self: | |
| if aVertex.getColor() == 'white': | |
| self.dfsvisit(aVertex) | |
| def dfsvisit(self, startVertex): # O(V + E) 覆盖每个顶点，并且每个边都会过一次 | |
| u""" | |
| 遍历过后的所有其它节点都能找到到开始节点的路径，构成深度优先森林 | |
| """ | |
| startVertex.setColor('gray') | |
| self.time += 1 | |
| startVertex.setDiscovery(self.time) # 开始遍历的时间 | |
| for nextVertex in startVertex.getConnections(): | |
| if nextVertex.getColor() == 'white': | |
| nextVertex.setPred(startVertex) | |
| self.dfsvisit(nextVertex) | |
| startVertex.setColor('black') | |
| self.time += 1 | |
| startVertex.setFinish(self.time) # 遍历完成的时间 | |
| u""" | |
| 拓扑排序 | |
| 有向无环图 | |
| 1. 对于某些图 g 调用 dfs(g)。我们想要调用深度优先搜索的主要原因是计算每个顶点的完成时间。 | |
| 2. 以完成时间的递减顺序将顶点存储在列表中。 | |
| 3. 返回有序列表作为拓扑排序的结果。得到正确的完成步骤 | |
| """ | |
| u""" | |
| 强联通分量 | |
| C 是 G 的子集, 并且 C 的每个顶点都是互通的(强联通) | |
| 1. 调用dfs计算G的每个顶点的完成时间 | |
| 2. 计算G^T 复制G,并翻转每个边的方向 | |
| 3. 为G^T调用dfs, 但在 DFS 的主循环中，以完成时间的递减顺序探查每个顶点。 | |
| 4. 在步骤 3 中计算的森林中的每个树是强连通分量。输出森林中每个树中每个顶点的顶点标识组件。 | |
| """ | |
| def buildSCC(): | |
| g = DFSGraph() | |
| g.addEdge('A', 'B') | |
| g.addEdge('B', 'C') | |
| g.addEdge('C', 'F') | |
| g.addEdge('F', 'H') | |
| g.addEdge('H', 'I') | |
| g.addEdge('I', 'F') | |
| g.addEdge('B', 'E') | |
| g.addEdge('E', 'D') | |
| g.addEdge('D', 'G') | |
| g.addEdge('G', 'E') | |
| g.addEdge('E', 'A') | |
| g.addEdge('D', 'B') | |
| g.dfs() | |
| return g | |
| def buildGT(g): | |
| newG = DFSGraph() | |
| for vert in g: # 构建G^T | |
| for nbr in vert.connectedTo.keys(): | |
| newG.addEdge(nbr.getId(), vert.getId()) | |
| verts = sorted(newG.vertList.values(), key=lambda vert: g.getVertex(vert.getId()).getFinish(), reverse=True) | |
| for aVertex in verts: | |
| aVertex.setColor('white') | |
| aVertex.setPred(-1) | |
| for aVertex in verts: | |
| if aVertex.getColor() == 'white': | |
| newG.dfsvisit(aVertex) # 构建的子树即为强连通分量 | |
| return newG | |
| u""" | |
| 最短路径问题 | |
| 针对加权边的图 | |
| """ | |
| class PriorityQueue(object): | |
| u""" | |
| 优先级队列 | |
| """ | |
| def __init__(self): | |
| self.heapArray = [(0,0)] | |
| self.currentSize = 0 | |
| def buildHeap(self,alist): | |
| self.currentSize = len(alist) | |
| self.heapArray = [(0,0)] | |
| for i in alist: | |
| self.heapArray.append(i) | |
| i = len(alist) // 2 | |
| while (i > 0): | |
| self.percDown(i) | |
| i = i - 1 | |
| def percDown(self,i): | |
| while (i * 2) <= self.currentSize: | |
| mc = self.minChild(i) | |
| if self.heapArray[i][0] > self.heapArray[mc][0]: | |
| tmp = self.heapArray[i] | |
| self.heapArray[i] = self.heapArray[mc] | |
| self.heapArray[mc] = tmp | |
| i = mc | |
| def minChild(self,i): | |
| if i*2 > self.currentSize: | |
| return -1 | |
| else: | |
| if i*2 + 1 > self.currentSize: | |
| return i*2 | |
| else: | |
| if self.heapArray[i*2][0] < self.heapArray[i*2+1][0]: | |
| return i*2 | |
| else: | |
| return i*2+1 | |
| def percUp(self,i): | |
| while i // 2 > 0: | |
| if self.heapArray[i][0] < self.heapArray[i//2][0]: | |
| tmp = self.heapArray[i//2] | |
| self.heapArray[i//2] = self.heapArray[i] | |
| self.heapArray[i] = tmp | |
| i = i//2 | |
| def add(self,k): | |
| self.heapArray.append(k) | |
| self.currentSize = self.currentSize + 1 | |
| self.percUp(self.currentSize) | |
| def delMin(self): | |
| retval = self.heapArray[1][1] | |
| self.heapArray[1] = self.heapArray[self.currentSize] | |
| self.currentSize = self.currentSize - 1 | |
| self.heapArray.pop() | |
| self.percDown(1) | |
| return retval | |
| def isEmpty(self): | |
| if self.currentSize == 0: | |
| return True | |
| else: | |
| return False | |
| def decreaseKey(self,val,amt): | |
| # this is a little wierd, but we need to find the heap thing to decrease by | |
| # looking at its value | |
| done = False | |
| i = 1 | |
| myKey = 0 | |
| while not done and i <= self.currentSize: | |
| if self.heapArray[i][1] == val: | |
| done = True | |
| myKey = i | |
| else: | |
| i = i + 1 | |
| if myKey > 0: | |
| self.heapArray[myKey] = (amt,self.heapArray[myKey][1]) | |
| self.percUp(myKey) | |
| def __contains__(self,vtx): | |
| for pair in self.heapArray: | |
| if pair[1] == vtx: | |
| return True | |
| return False | |
| u""" | |
| dijkstra算法, 类似于bfs, 只是使用优先级队列, 按权重最小排列 | |
| 最终算出其它顶点与开始顶点间最短距离 | |
| 只有权重为正才能正常运行,否则会死循环 | |
| """ | |
| def dijkstra(aGraph, start): # O((V + E)log^V ) | |
| pq = PriorityQueue() | |
| start.setDistance(0) | |
| pq.buildHeap([(v.getDistance(), v) for v in aGraph]) # 所有的都放进去了 | |
| while not pq.isEmpty(): | |
| currentVert = pq.delMin() | |
| for nextVert in currentVert.getConnections(): | |
| newDist = currentVert.getDistance() \ | |
| + currentVert.getWeight(nextVert) | |
| if newDist < nextVert.getDistance(): | |
| nextVert.setDistance(newDist) | |
| nextVert.setPred(currentVert) | |
| pq.decreaseKey(nextVert, newDist) # 移动到队列的前面 | |
| u""" | |
| 最小权重生成树 | |
| Prim生成树算法 | |
| 使用最小权重的边重写顶点的路径, 贪婪算法 | |
| """ | |
| def prim(G, start): | |
| pq = PriorityQueue() | |
| for v in G: | |
| v.setDistance(sys.maxint) | |
| v.setPred(None) | |
| start.setDistance(0) | |
| pq.buildHeap([(v.getDistance(), v) for v in G]) | |
| while not pq.isEmpty(): | |
| currentVert = pq.delMin() | |
| for nextVert in currentVert.getConnections(): | |
| newCost = currentVert.getWeight(nextVert) + currentVert.getDistance() | |
| if nextVert in pq and newCost < nextVert.getDistance(): | |
| nextVert.setPred(currentVert) | |
| nextVert.setDistance(newCost) | |
| pq.decreaseKey(nextVert, newCost) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment