邻接表的python实现与深度优先搜索

Vertex类

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]

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]
        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())

基于邻接表的深度优先搜索(python实现)

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