算法图解第6章笔记

标签： 笔记 基础算法 python

---

数据结构

队列是一种先进先出（First In First Out，FIFO）的数据结构，而栈是一种后进先出（Last In First Out，LIFO）的数据结构。

简单图的python表示

graph = {}
graph["you"] = ["alice", "bob", "claire"]
graph["bob"] = ["anuj", "peggy"]
graph["alice"] = ["peggy"]
graph["claire"] = ["thom", "jonny"]
graph["anuj"] = []
graph["peggy"] = []
graph["thom"] = []
graph["jonny"] = []

补充：散列表是无序的，因此添加键—值对的顺序无关紧要。

图分为有向图和无向图（等价）。

广度优先搜索算法示例

from collections import deque
def search(name):
#创建一个双端队列
  search_queue = deque()
#将你的邻居都加入到这个搜索队列中
  search_queue += graph["you"]
  searched = []
  while search_queue:
    person = search_queue.popleft()
  #当此人不被标记是才判断
    if not person in searched:
      if person_is_seller(person):
        print person + " is a mango seller!"
        return True
      else:
        search_queue += graph[person] s
        earched.append(person)
  return false

#简单的判断函数
def person_is_seller(name):     
  return name[-1] == 'm'


search("you")

广度优先搜索的运行时间为 O(人数 + 边数)，这通常写作O(V + E)，其中V为顶点（vertice）数，E为边数。