今天要开启新的一章学习啦，近期学习目标：
- 图及算法，慢慢来
- py实现逻辑回归（easy）、cart回归树（median）、SVM（hard）
- 经典机器学习算法还差rf和boosting，学完之后可以了解下强化学习的概念
- 做完这些就需要对数据结构进行复习啦，暂定为看b站视频&leetcode简单题目
图的概念
- 顶点Vertex
具有名称标识Key，也可以携带数据项payload - 边Edge/弧Arc
表示两个顶点之间的关系，可以有方向也可以没有 - 权重Weight
给边赋权重，可以理解为从一个顶点到另一个顶点的“代价” - 图Graph 一个图G可以定义为G = (V,E)，即点和边的集合
- E中的每一条e = (v,w) v,w是两个顶点
- 如果有权重，e中还要增加权重分量
- 路径Path 依次链接的顶点序列：
- 有权重：路径的长度=边的数量
- 无权重：路径的长度=边权重的和
- 圈Cycle 首尾相连/顶点相同的路径，有些有向图不存在任何圈（称为DAG）
实现ADT Graph
- 添加：顶点、边/有权重的边addVertex、addEgde
- 查找：按key查找顶点
实现形式：
-
邻接矩阵
- 行列代表顶点，如果i和j有连接，矩阵ij处保存权重
- 问题在于效率，大多数时候都是系数的
-
邻接表
- 一个masterlist，包括所有顶点
- 每个顶点都关联一个list，保存所有和自己有边连接的顶点
## 将代码块运行结果全部输出，而不是只输出最后的，适用于全文
from IPython.core.interactiveshell import InteractiveShell
InteractiveShell.ast_node_interactivity = "all"
#### 1.首先定义顶点类（不带payload的、有方向的图）
class Vertex:
def __init__(self, key):
self.id = key # 用id保存key
self.connectedTo = {} # 字典保存，非常类似昨天10.14写的ID3里对于多叉数的节点定义！
def addNeighbor(self, nbr, weight = 0): # nbr——链接的对象的key
self.connectedTo[nbr]=weight # 加入connection里，并赋边的权重
def __str__(self):
return str(self.id) +' connectedTo: ' +str([x.id for x in self.connectedTo])
def getId(self): # 获得id
return self.id
def getConnections(self): # 该顶点链接的所有顶点的key
return self.connectedTo.keys()
def getWeight(self,nbr): # 查看两个顶点的边权重
return self.connectedTo[nbr] # 字典按照key索引
# 测试
v1 = Vertex(1);v2 = Vertex(2);v3 = Vertex(3)
v1.addNeighbor(1, 12);v1.addNeighbor(2, 13);v2.addNeighbor(3, 23)
v1.getConnections()
v2.getWeight(3)
1
2
23
##### 2.接着实现Graph类（邻接表的形式）
class Graph: # 维护一个masterlist
def __init__(self):
self.vertList = {} # 存储所有顶点，是一个字典key:vertex
self.numVertices = 0 # 顶点数量
def addVertex(self,key): # 添加顶点
newVertex = Vertex(key) # 变成顶点形式
self.vertList[key] = newVertex # 加入masterlist字典
self.numVertices +=1
#print(newVertex)
def getVertex(self,item): # 按照key从master里查找一个顶点
if item in self.vertList:
return self.vertList[item]
else:
return None
def __contain__(self,item): # 是否包含某个key
return item in self.vertList
def addEdge(self, f, t, cost=0): # 添加边 f 到 t（key），cost是边的权重
# 如果给出的f和t在masterlist里面找不到
if f not in self.vertList:
nv = self.addVertex(f)
if t not in self.vertList:
nv = self.addVertex(t)
self.vertList[f].addNeighbor(self.vertList[t], cost) # 调用vertex类里定义联系的方法
#print(self.vertList[f])
def getVertices(self): # 输出所有顶点key
return self.vertList.keys()
def __iter__(self):
return iter(self.vertList.values()) # 可迭代 所有vertex
# 测试
g = Graph()
# 添加顶点
for i in range(6): g.addVertex(i)
# 查看所有顶点
g.getVertices()
# 添加新边
g.addEdge(1, 2, cost=12)
g.addEdge(1, 3, cost=13)
g.addEdge(1, 7, cost=17)
# 顶点数目
g.numVertices
# 查看某个顶点
print(g.getVertex(1))
dict_keys([0, 1, 2, 3, 4, 5])
7
1 connectedTo: [2, 3, 7]
图的应用
单词游戏——词梯问题
-
相邻两个单词之间的差异只能是一个字母
-
我们的目标是找到最短的单词变换序列
-
如何用图来解释——把可能的单词之间的演变关系表达为图
- 把所有固定长度的单词作为顶点key
- 对每个顶点，如果单词之间之只差一个字母，就设一条边（比较次数多）
- 无向图、无权重
避免逐个比较建边的改进方法
- 桶，每个桶可以存放若干单词——只有一个字母不一样
- 桶的key是用_占替代一个字母
- 然后在同一个桶的相互之间建边
-
广度优先搜索BFS：搜索从开始单词到结束单词之间的所有有效路径
-
选出最短路径
建立单词关系图
### 前置处理——采用字典建立“桶”
import os # 加载标准库
os.chdir('/Users/mac/Desktop/快乐研一/python/data') # 相当于setwd()
def buildGraph(wordFile):
d = {}
g = Graph()
wfile = open(wordFile,'r')
# 构造桶
for line in wfile: # 对于每一个单词
word = line[:-1]
for i in range(len(word)): # 有a个字母的单词会属于a个桶!!
bucket = word[:i] + "_" + word[i+1:] # 对于单词的每一个字母
if bucket in d: # 如果已经有了这个桶，直接加入，没有的话新建桶用bucket当做key
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) # 默认权重0，相当于无权重
return g # 就是各个单词的图
wordslink = buildGraph('fourletterwords.txt')
print(wordslink.getVertex('SAIL'))
#wordslink.getVertices()
length = 0
for key in wordslink.getVertices():
length += len(wordslink.getVertex(key).connectedTo)
print("\n 单词数量={}，邻接表的边数目={}，如果用邻接矩阵单元数目将会是={} ".format(wordslink.numVertices ,length, wordslink.numVertices *wordslink.numVertices))
SAIL connectedTo: ['BAIL', 'FAIL', 'HAIL', 'JAIL', 'KAIL', 'MAIL', 'NAIL', 'PAIL', 'RAIL', 'TAIL', 'VAIL', 'WAIL', 'SAID', 'SAIN', 'SOIL', 'SALL', 'SAUL']
单词数量=3838，邻接表的边数目=42004，如果用邻接矩阵单元数目将会是=14730244
广度优先搜索BFS
初步理解
- 给定一个图G和搜索的起始顶点S，搜索所有从s可到顶点的边
- 可以想象为s作为根节点，构建一颗多叉树的过程
- **“广度优先”**意味着在增加搜索距离到k+1/加深层次之前，把所有兄弟节点/距离为k的顶点都找到
- 产生的问题：有一些节点到S有不同路径，导致距离不同——如何解决？
跟踪顶点加入过程——给顶点增加属性
- 距离distance：起始S到当前顶点的路径
- 前驱顶点 predecessor：反向追溯
- 标识color：白色：尚未发现；灰色：已经发现；完成探索：黑色
- 队列：对已经发现的顶点进行排序
## 首先扩展一下vertex类，加入三个属性
class Vertex:
def __init__(self, key):
self.id = key # 用id保存key
self.connectedTo = {} # 字典保存，非常类似昨天10.14写的ID3里对于多叉数的节点定义
self.distance = None
self.pred = None
self.color = "white"
def addNeighbor(self, nbr, weight = 0): # nbr——链接的对象的key
self.connectedTo[nbr]=weight # 加入connection里，并赋边的权重
def __str__(self):
return str(self.id) +' connectedTo: ' +str([x.id for x in self.connectedTo])
def getId(self): # 获得id
return self.id
def getConnections(self): # 该顶点链接的所有顶点的key
return self.connectedTo.keys()
def getWeight(self,nbr): # 查看两个顶点的边权重
return self.connectedTo[nbr] # 字典按照key索引
##### 增加部分 ######
def setDistance(self, x): # 设置距离
self.distance = x
def setPred(self, x): # 设置前驱顶点
self.pred = x
def setColor(self, x): # 设置颜色标识
self.color = x
算法过程
-
第一步、从起始顶点S开始（颜色灰色，距离0，前驱none，加入队列）
-
第二步、迭代：
- 从队首pop出一个顶点，作为current顶点
- 遍历current顶点的connected顶点，如果是白色，则：改为灰色、距离+1、前驱设为current顶点、加入队列）
- 遍历结束后，把current顶点设为黑色
-
最终的结果：所有的顶点都有颜色黑色、距离X、前驱X，可以根据前驱一步步找回起始顶点S——一条路径
def bfs(g,start): # 按照上述写成函数
# 第一步
queue = []
start.setDistance(0)
start.setColor("grey")
queue.append(start)
# 第二步
while len(queue)>0:
current = queue.pop(0)
for node in current.connectedTo:
if node.color == "white":
node.setColor("grey")
node.setDistance(current.distance+1)
node.setPred(current)
queue.append(node)
current.setColor("black")
# 第三步
def traverse(y): # 根据pred来回溯
x = y
path = []
while x.pred: # 顶点有predecessor时
path.append(x.id)
x = x.pred # 继续向上
path.append(x.id)
path.reverse()
return path
# 测试
wordslink = buildGraph('fourletterwords.txt')
bfs(wordslink, wordslink.getVertex('FOOL')) # 给出图和起始顶点
res = traverse(wordslink.getVertex('SAGE'))
print("词梯问题的一个解：\n"+ ' -> '.join(res))
词梯问题的一个解：
FOOL -> MOOL -> MOLL -> MALL -> SALL -> SALE -> SAGE