学习目标：
1.了解图是什么，如何构建
2.使用图来解决问题
一 、常用术语
顶点：顶点是图的基本部分，我们也可称为键。
边：边可以连接两个顶点，以表明他们之间的关系。可以是双向也可以是单向。如果都是单向的，我们称图为有向图。
权重：边可被加权，表示从一个顶点到另一个顶点的成本。
路径：图中的路径是由边连接的顶点序列。
循环：有向图中的循环是在同一顶点开始和结束的路径。
二、实现方式
实现图的最简单的方法：一是二维矩阵。每个行和列表示图中的顶点。优点：实现方式简单。二、邻接表。在邻接表实现中，我们保存Graph对象中的所有顶点的主列表，然后图中的每个顶点对象维护连接到的其他顶点的列表。
#创建一个顶点类
class Vertex(object):
def __init__(self,key):
self.id=key
self.connectedTo={} #利用字典来追踪它连接的顶点和每个边的权重。
#添加顶点
def addNeighbor(self,nbr,weight=0):
self.connectedTo[nbr]=weight
#返回邻接表中的所有顶点
def getConnections(self):
return self.connectedTo.keys()
def getId(self):
return self.id
#返回从这个顶点到参数传递的顶点的权重
def getWeight(self,nbr):
return self.connectedTo[nbr]
def __str__(self):
return str(self.id)+'connectedTo'+str([x.id for x in self.connectedTo])
#创建Graph类,将顶点名称映射到顶点对象的字典
class Graph(object):
def __init__(self):
self.vertList={}
self.numVertices=0
#
def addVertex(self,key):
self.numVertices=self.numVertices+1
newVertex=Vertex(key)#顶点
self.vertList[key]=newVertex
return newVertex
def getVertex(self,n):
if n in self.vertList:
return self.vertList[n]
else:
return None
def __contains__(self, n):
return n in self.vertList
#添加边
def addEdage(self,f,t,cost=0):
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)
def getVertices(self):
return self.vertList.keys()
def __iter__(self):
return iter(self.vertList.values())
if __name__=="__main__":
g=Graph()
#添加顶点
for i in range(6):
g.addVertex(i)
#添加边
g.addEdage(0,1,5)
g.addEdage(0,5,2)
g.addEdage(1, 2, 4)
g.addEdage(2,3,9)
g.addEdage(3,4, 7)
g.addEdage(3,5,2)
g.addEdage(4,0,1)
g.addEdage(5,4,8)
g.addEdage(5,2,1)
for v in g:
for w in v.getConnections():
print("(%s,%s)" %(v.getId(),w.getId()))
具体问题---字梯的问题
字梯的问题：是指将单词“FOOL”转换成单词”SAGE”。在字梯中你通过改变一个字母逐渐发生变化。每一步，你必须将一个将一个字换成另一个字。
FOOL
POOL
POLL
POLE
PALE
SALE
SAGE
怎样利用图来解决这个问题。主要步骤：
（1）将字之间的关系表示为图
（2）使用广度优先搜索的图算法来找到从起始到结束字的游侠路径
先看广度优先：
（1）顶点v入队列。
（2）当队列非空时则继续执行，否则算法结束。
（3）出队列取得队头顶点v；访问顶点v并标记顶点v已被访问。
（4）查找顶点v的第一个邻接顶点col。
（5）若v的邻接顶点col未被访问过的，则col入队列。
（6）继续查找顶点v的另一个新的邻接顶点col，转到步骤（5）。直到顶点v的所有未被访问过的邻接点处理完。转到步骤（2）。
def bfs(self,start):
queue = [start] #创建队列
result = []
visited = [False for i in range(self.v)] #标记是否被访问
while queue: #队列不为空
now = queue.pop(0) #当前节点
if not visited[now]:#没有被访问时
visited[now] = True
result.append(now)
for i in range(self.v):
if self.graph[now][i]!= 0 and visited[i] is False:
queue.append(i)
return result
具体问题---骑士之旅（深度优先算法）
（1）访问初始顶点v并标记顶点v已访问。
（2）查找顶点v的第一个邻接顶点w。
（3）若顶点v的邻接顶点w存在，则继续执行；否则回溯到v，再找v的另外一个未访问过的邻接点。
（4）若顶点w尚未被访问，则访问顶点w并标记顶点w为已访问。
（5）继续查找顶点w的下一个邻接顶点wi，如果v取值wi转到步骤（3）。直到连通图中所有顶点全部访问过为止。
网友评论