图是一种善于处理关系型数据的数据结构,使用它可以很轻松地表示数据之间是如何关联的

图的实现形式有很多,最简单的方法之一就是用散列表

背景

图有两种经典的遍历方式:广度优先搜索和深度优先搜索。两者是相似的。

实现

1广度优先搜索算法需要用队列来记录后续要处理哪些顶点。

2该队列最初只含有起步的顶点

3处理顶点。我们将其移出队列,标为“已访问”,并记为当前顶点

1
2
3
4
5
6
7
8
9
class Bfs:
    def __init__(self,from_v,json):
        # 最初的顶点
        self.from_v = from_v
        # 已访问
        self.visitList = [self.from_v]
        # 需要一个队列来记录后续需要处理哪些顶点
        self.vertexQ = queue.Queue()
        self.json = json

 核心步骤

(1) 找出当前顶点的所有邻接点。如果有哪个是没访问过的,就把它标为“已访问”,并且将它入队。(尽管该顶点并未作为“当前顶点”被访问过。)

(2) 如果当前顶点没有未访问的邻接点,且队列不为空,那就再从队列中移出一个顶点作为当前顶点。

(3) 如果当前顶点没有未访问的邻接点,且队列里也没有其他顶点,那么算法完成。

图解

 

1首先A会作为顶点,A被访问

2再去寻找A领接点B、D,依次加入队列

3A所有领接点都访问完成,开始访问B的领接点

4知道队列为空,算法结束

代码展示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Bfs:
    def __init__(self,from_v,json):
        # 最初的顶点
        self.from_v = from_v
        # 已访问
        self.visitList = [self.from_v]
        # 需要一个队列来记录后续需要处理哪些顶点
        self.vertexQ = queue.Queue()
        self.json = json
 
    def find_neighbor(self,currentVertex):
        #寻找领接点
        for neighbor in self.json[currentVertex]:
            if neighbor not in self.visitList:
                self.visitList.append(neighbor)
                self.vertexQ.put(neighbor)
 
    def checkTOV(self,currentVertex,to_v):
        #检测要寻找的值(to_v)是否已经在当前currentVertex中
        return to_v in self.json[currentVertex]
 
    def searchV(self,to_v):
        reverseList = [self.from_v]
        self.find_neighbor(self.from_v)
        while not self.vertexQ.empty():
            currentVertex = self.vertexQ.get()
            reverseList.append(currentVertex)
            tmp_path = Reverse(currentVertex,self.json).reverseOrder(reverseList,currentVertex)
            if currentVertex == to_v:
                print(tmp_path)
            else:
                self.find_neighbor(currentVertex)
                if self.checkTOV(currentVertex,to_v):
                    tmp_path.append(to_v)
                    print(tmp_path)

 此外我们额外写了一个向上反向找寻路径的工具类(主要代码写好,不想动原来的结构了)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Reverse:
    def __init__(self,from_v,json):
        self.from_v = from_v
        self.json = json
    def reverseOrder(self,reverseList:list,current_v):
        indexReverseList = self.indexReverseList(reverseList)
        res = [self.from_v]
        tmp = current_v
        while len(reverseList) > 0 :
            # for _key in self.value2Key(current_v):
            _key = self.value2Key(reverseList,tmp)
            res.append(_key)
            reverseList = reverseList[:indexReverseList[_key]]
            tmp = _key
        return res[::-1]
 
    def value2Key(self,reverseList:list,current_v):
        #根据值找json中的key
        #这里我们每次都只取离我们最近的一个key
        indexReverseList = self.indexReverseList(reverseList)
        tmp = -1
        for _key, _value in self.json.items():
            if current_v in _value and _key in reverseList and (index := indexReverseList[_key]) > tmp:
                tmp = index
        return reverseList[tmp]
 
    def indexReverseList(self,reverseList:list):
        return {value: index for index, value in enumerate(reverseList)}

 运行结果

1
2
3
json = {"A":["B","D"],"B":["C"],"C":["E","D"],"D":["E"],"E":["B"]}<br>#从A出发找B
b=Bfs("A",json)
b.searchV("B")