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,const = 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],const) def getVertices(self): return self.vertList.keys() def __iter__(self): return iter(self.vertList.values())
visited = [] start = 0 #假设以0为起点 stack = [] stack.append(start) while len(stack)>0: n = stack[-1] stack.pop() if n in visited: continue print(n," is visited") v = g.getVertex(n) for neighbor in list(v.getConnections()): stack.append(neighbor.getId()) visited.append(n)
g = Graph() for i in range(6): g.addVertex(i) 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) visited = [] start = 0 stack = [] stack.append(start) while len(stack)>0: n = stack[-1] stack.pop() if n in visited: continue print(n," is visited") v = g.getVertex(n) for neighbor in list(v.getConnections()): stack.append(neighbor.getId()) visited.append(n)
输出:
0 is visited
5 is visited
2 is visited
3 is visited
4 is visited
1 is visited