图可以用G=(V,E)来表述,对于图G,V是顶点的集合,E是边的集合。每个边是一个元组(v,w),v和w属于顶点集合V。
顶点Vertex类:包含了顶点信息,以及顶点连接边的信息
class Vertex:
def __init__(self, key):
self.id = key
self.connectedTo = {}
def addNeighbor(self, nbr, weight = 0): #该方法被用来添加从一个顶点到另一个顶点的连接
self.connectedTo[nbr] = weight #nbr是顶点对象的key
def __str__(self):
return str(self.id) + 'connectedTo: ' + str([x.id for x in self.connectedTo])
def getConnections(self): #该方法被用来返回以connectionTo字典中的实例变量所表示的邻接表中的所有顶点
return self.connectedTo.keys()
def getId(self):
return self.id
def getWeight(self, nbr): #该方法通过一个参数返回顶点与顶点之间的边的权重
return self.connectedTo[nbr]
图Graph类:保存了包含所有顶点的主表
class Graph:
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] #通过key查找顶点
else:
return None
def __contains__(self, n):
return n in self.vertList
def addEdge(self, f, t, cost = 0):
if f not in self.vertList: #不存在的顶线先添加
nv = self.addVertex(f)
if t not in self.addVertex:
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())
ADT Grapgh实现代码测试:
class Vertex:
def __init__(self,key):
self.id = key
self.connectedTo = {}
def addNeighbor(self,nbr,weight=0):
self.connectedTo[nbr] = weight
def __str__(self):
return str(self.id) + ' connectedTo: ' + str([x.id for x in self.connectedTo])
def getConnections(self):
return self.connectedTo.keys()
def getId(self):
return self.id
def getWeight(self,nbr):
return self.connectedTo[nbr]
class Graph:
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 addEdge(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())
g = Graph()
for i in range(6):
g.addVertex(i)
print(g.vertList)
g.addEdge(0,1,5)
g.addEdge(0,5,2)
g.addEdge(1,2,4)
g.addEdge(2,3,9)
g.addEdge(3,4,7)
g.addEdge(3,5,3)
g.addEdge(4,0,1)
g.addEdge(5,4,8)
g.addEdge(5,2,1)
for v in g:
for w in v.getConnections():
print("( %s , %s )" % (v.getId(), w.getId()))
{0: <__main__.Vertex object at 0x000001F151227F08>, 1: <__main__.Vertex object at 0x000001F150ACA388>, 2: <__main__.Vertex object at 0x000001F151208BC8>, 3: <__main__.Vertex object at 0x000001F151208D08>, 4: <__main__.Vertex object at 0x000001F151208A48>, 5: <__main__.Vertex object at 0x000001F151208748>}
( 0 , 1 )
( 0 , 5 )
( 1 , 2 )
( 2 , 3 )
( 3 , 4 )
( 3 , 5 )
( 4 , 0 )
( 5 , 4 )
( 5 , 2 )
BFS采用队列来存储待访问节点;DFS则是通过递归调用隐式使用了栈
#使用扩展版的Vertex类
class Vertex:
def __init__(self,num):
self.id = num
self.connectedTo = {}
self.color = 'white'
self.dist = sys.maxsize
self.pred = None
self.disc = 0
self.fin = 0
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 __str__(self):
return str(self.id) + ":color " + self.color + ":disc " + str(self.disc) + ":fin " + str(self.fin) + ":dist " + str(self.dist) + ":pred \n\t[" + str(self.pred)+ "]\n"
def getId(self):
return self.id
广度优先搜索Breadth First Search:最简单算法之一
def bfs(g, start):
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') #当前顶点设为黑色
算法分析:算法主体是两个循环的嵌套
深度优先搜索Depth First Search:逐层建立搜索树
骑士周游问题是一种特殊的对图进行深度优先搜索,其目的是建立一个没有分支的最深的深度优先树,表现为一条线性的包含所有节点的退化树
def knightTour(n, path, u, limit): #n:层次;path:路径;u:当前顶点;limit:搜索总深度
u.setColor('gray')
path.append(u) #当前顶点加入路径
if n < limit:
nbrList = list(u.getConnections()) #对所有合法移动逐一深入
i = 0
done = False
while i < len(nbrList) and not done:
if nbrList[i].getColor() == 'white': #选择白色未经过的顶点深入
done = knightTour(n+1, path, nbrList[i], limit) #层次加1,递归深入
i = i + 1
#prepare to backtrack
if not done:
path.pop() #都无法完成总深度,回溯,试本层下一个顶点
u.setColor('white')
else:
done = True
return done
一般的深度优先搜索目标是在图上进行尽量深的搜索,连接尽可能多的顶点,必要时可以进行分支(创建树)。有时候,深度优先搜索会创建多棵树,称为‘深度优先森林’
class DFSGraph(Graph):
def __init__(self):
super().__init__()
self.time = 0
def dfs(self):
for aVertex in self: #颜色初始化
aVertex.setColor('white')
aVertex.setPred(-1)
for aVertex in self: #self是DFSGraph类的一个实例
if aVertex.getColor() == 'white': #如果还有未包括的顶点,则建森林
self.dfsvisit(aVertex)
def dfsvisit(self, startVertex):
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)
DFS构建的树,其顶点的发现时间和结束时间属性,具有类似括号的性质,即一个顶点的发现时间总小于所有子顶点的发现时间,而结束时间则大于所有子顶点的结束时间。
Word Ladder:从一个单词演变到另一个单词,并且不允许转变成一个不存在的单词,其中的过程可以经过多个中间单词
#采用单词建立桶
def buildGraph(wordFile):
d ={}
g = Graph()
wfile = open(wordFile, 'r')
#create buckets of words that differ by one letter
for line in wfile:
word = line[:-1]
for i in range(len(word)):
bucket = word[:i] + '_' + word[i+1:]
if bucket in d: #4字母单词可属于4个桶
d[bucket].append(word)
else:
d[bucket] = [word]
#add vertices and edges for words in the same bucket
for bucket in d.keys():
for word1 in d[bucket]:
for word2 in d[bucket]:
if word1 != word2: #同一个桶单词之间建立边
g.addEdge(word1, word2)
return g
在以FOOL为起始顶点,遍历了所有顶点,并为每个顶点着色、赋距离和前驱之后,既可以通过一个回途追溯函数来确定任何单词顶点到FOOL的最短词梯
def traverse(y):
x = y
while(x.getPred()):
print(x.getId())
x = x.getPred()
print(x.getId())
wordgraph = buildGraph("fourletterwords.txt")
bfs(wordgraph, wordgraph.getVertex('FOOL'))
traverse(wordgraph.getVertex('SAGE'))
算法分析:
全部代码如下:
def buildGraph(wordFile):
d = {}
g = Graph()
wfile = open(wordFile,'r')
# create buckets of words that differ by one letter
for line in wfile:
word = line[:-1]
for i in range(len(word)):
bucket = word[:i] + '_' + word[i+1:]
if bucket in d:
d[bucket].append(word)
else:
d[bucket] = [word]
# add vertices and edges for words in the same bucket
for bucket in d.keys():
for word1 in d[bucket]:
for word2 in d[bucket]:
if word1 != word2:
g.addEdge(word1,word2)
return g
def bfs(g,start):
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()
print(x.getId())
wordgraph = buildGraph("fourletterwords.txt")
bfs(wordgraph, wordgraph.getVertex('FOOL'))
traverse(wordgraph.getVertex('SAGE'))
骑士周游:在一个国际象棋棋盘(8*8)上,一个棋子‘马’(骑士),按照马走日的规则,从一个格子出发,要走遍所有棋盘格恰好一次。把一个这样的走棋序列称为一次‘周游’。
def knightGraph(bdSize):
ktGraph = Graph()
for row in range(bdSize): #遍历每个格子
for col in range(bdSize):
nodeId = posToNodeId(row, col, bdSize)
newPisitions = genLegalMoves(row, col, bdSize) #单步合法走棋
for e in newPisitions:
nid = posToNodeId(e[0], e[1], bdSize)
ktGraph.addEdge(nodeId, nid) #添加边及顶点
return ktGraph
def genLegalMoves(x, y, bdSize):
newMoves = []
moveOffsets = [(-1, -2), (-1, 2), (-2, -1), (-2, 1), (1, -2), (1, 2), (2, -1), (2, -2)] #马走日的8个格子
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
else:
return False
def posToNodeId(row, col, bdSize):
return row * bdSize + col
初始算法中nbrList,直接以原始顺序来确定深度优先搜索的分支次序
def knightTour(n, path, u, limit): #n:层次;path:路径;u:当前顶点;limit:搜索总深度
u.setColor('gray')
path.append(u) #当前顶点加入路径
if n < limit:
nbrList = list(u.getConnections()) #对所有合法移动逐一深入
i = 0
done = False
while i < len(nbrList) and not done:
if nbrList[i].getColor() == 'white': #选择白色未经过的顶点深入
done = knightTour(n+1, path, nbrList[i], limit) #层次加1,递归深入
i = i + 1
#prepare to backtrack
if not done:
path.pop() #都无法完成总深度,回溯,试本层下一个顶点
u.setColor('white')
else:
done = True
return done
DFS算法是指数时间复杂度算法,可以在实际性能上加以大幅度改进
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))
#格式:key=lambda 元素: 元素[字段索引]
resList.sort(key=lambda x: x[0]) #按照列表中第一个元素排序;lambda 用于匿名函数,可以免去命名函数的麻烦
return [y[1] for y in resList]
def knightTourBetter(n,path,u,limit): #use order by available function
u.setColor('gray')
path.append(u)
if n < limit:
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
拓扑排序:将一个有向无圈图(DAG)转换为一个只包含它所有顶点的线性排列。例如,如果有一个图G包含一个边界(v,w)然后我们就可以按顺序将顶点v放在顶点w之前。
强连通分支:在一张图G中定义一个强连通分支C,作为最大的顶点子集C包含于V,因此对其中每一对顶点,均要使其相互联通。即顶点v,w之间都有路径来回,且(v,w)和(w,v)都是C的路径
#优先队列类
class PriorityQueue:
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
import PriorityQueue, Graph, Vertex
def dijkstra(aGraph, start):
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(): #修改出队顶点所邻接顶点的dist属性,并逐个重排队列
nextVert.setDistance(newDist)
nextVert.setPred(currentVert)
pq.decreaseKey(nextVert, newDist)
算法分析:时间复杂度为:O((|V|+|E|)log|V|)
信息广播问题一般解法:
import PriorityQueue, Graph, Vertex
import sys
def prim(G, start):
pq = PriorityQueue()
for v in G:
v.setDistance(sys.maxsize)
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)
if nextVert in pq and newCost < nextVert.getDistance():
nextVert.setPred(currentVert)
nextVert.setDistance(newCost)
pq.decreaseKey(nextVert, newCost)