g = [
    ['A0', [('B1', 3), ('D3', 5)]],
    ['B1', [('C2', 4)]],
    ['C2', [('D3', 6), ('E4', 1)]],
    ['D3', [('E4', 2)]],
    ['E4', [('B1', 7)]],
]

for node in g:
    print(node[0],end=' ') 

for node in g:
    print('-------------------')
    print(node[0], ":", end='')
    edges = node[1]
    for e in edges:
        v, w = e
        print(v, w, end=';')
    print()

g = {
    'A0':{'B1': 3, 'D3': 5},
    'B1': {'C2': 4},
    'C2': {'D3': 6, 'E4': 1},
    'D3': {'E4':2},
    'E4': {'B1': 7}
}

for node in g.keys():
    print(node,end=" ")

print("查詢與 A0 項(xiàng)點(diǎn)有連接的其它頂點(diǎn)")
for k, v in g.get('A0').items():
    print((k, v), end=";")

class Vertex:
    def __init__(self, name, v_id=0):
        # 頂點(diǎn)的編號(hào)
        self.v_id = v_id
        # 頂點(diǎn)的名稱
        self.v_name = name
        # 是否被訪問過:False 沒有 True:有
        self.visited = False
        # 與此頂點(diǎn)相連接的其它頂點(diǎn)
        self.connected_to = {}

class Graph:

    def __init__(self):
        # 一維列表，保存節(jié)點(diǎn)
        self.vert_list = {}
        # 頂點(diǎn)個(gè)數(shù)
        self.v_nums = 0
        # 使用隊(duì)列模擬隊(duì)列或棧，用于路徑搜索算法
        self.queue_stack = []
        # 保存搜索到的路徑
        self.searchPath = []

class Vertex:
    def __init__(self, v_name, v_id=0):
        # 頂點(diǎn)的編號(hào)
        self.v_id = v_id
        # 頂點(diǎn)的名稱
        self.v_name = v_name
        # 是否被訪問過:False 沒有 True:有
        self.visited = False
        # 與此頂點(diǎn)相連接的其它頂點(diǎn)
        self.connected_to = {}

    '''
    添加鄰接頂點(diǎn)
    nbr_ver:相鄰頂點(diǎn)
    weight:無向無權(quán)重圖，權(quán)重默認(rèn)設(shè)置為 1
    '''
    def add_neighbor(self, nbr_ver, weight=1):
        # 以相鄰頂點(diǎn)為鍵，權(quán)重為值
        self.connected_to[nbr_ver] = weight

    '''
    顯示與當(dāng)前頂點(diǎn)相鄰的頂點(diǎn)
    '''
    def __str__(self):
        return '與 {0} 頂點(diǎn)相鄰的頂點(diǎn)有:{1}'.format(self.v_name,
                                           str([(key.v_name, val) for key, val in self.connected_to.items()]))

    '''
    得到相鄰頂點(diǎn)的權(quán)重
    '''
    def get_weight(self, nbr_v):
        return self.connected_to[nbr_v]

    '''
    判斷給定的頂點(diǎn)是否和當(dāng)前頂點(diǎn)相鄰
    '''
    def is_neighbor(self, nbr_v):
        return nbr_v in self.connected_to     

class Graph:
    def __init__(self):
        # 一維列表，保存節(jié)點(diǎn)
        self.vert_list = {}
        # 頂點(diǎn)個(gè)數(shù)
        self.v_nums = 0
        # 使用隊(duì)列模擬隊(duì)列或棧，用于路徑搜索算法
        self.queue_stack = []
        # 保存搜索到的路徑
        self.searchPath = []

   def add_vertex(self, vert):
        if vert.v_name in self.vert_list:
            # 已經(jīng)存在
            return
        # 頂點(diǎn)的編號(hào)內(nèi)部生成
        vert.v_id = self.v_nums
        # 所有頂點(diǎn)保存在圖所維護(hù)的字典中，以頂點(diǎn)名為鍵，頂點(diǎn)對(duì)象為值
        self.vert_list[vert.v_name] = vert
        # 數(shù)量增一
        self.v_nums += 1

 	'''
    根據(jù)頂點(diǎn)名找到頂點(diǎn)對(duì)象
    '''
    def find_vertex(self, v_name):
        if v_name in self.vert_list:
            return self.vert_list.get(v_name)
    # 查詢所有頂點(diǎn)
    def find_vertexes(self):
        return [str(ver) for ver in self.vert_list.values()]

    '''
    添加節(jié)點(diǎn)與節(jié)點(diǎn)之間的關(guān)系（邊），
    如果是無權(quán)重圖，統(tǒng)一設(shè)定為 1 
    '''
    def add_edge(self, from_v, to_v, weight=1):
        # 如果節(jié)點(diǎn)不存在
        if from_v not in self.vert_list:
            self.add_vertex(from_v)
        if to_v not in self.vert_list:
            self.add_vertex(to_v)
        from_v.add_neighbor(to_v, weight)

    '''
    廣度優(yōu)先搜索
    '''
    def bfs_nearest_path(self, from_v, to_v):
        tmp_path = []
        tmp_path.append(from_v)
        # 起始頂點(diǎn)不用壓入隊(duì)列
        from_v.visited = True
        # from_v 頂點(diǎn)的相鄰頂點(diǎn)壓入隊(duì)列
        self.push_queue(from_v)
        while len(self.queue_stack) != 0:
            # 從隊(duì)列中獲取頂點(diǎn)
            v_ = self.queue_stack.pop(0)
            if from_v.is_neighbor(v_):
                # 如果 v_ 是 from_v 的后序相鄰頂點(diǎn)，則連接成一條中路徑信息 
                tmp_path.append(v_)
                # 添加路徑信息
                self.searchPath.append(tmp_path)
                tmp_path = tmp_path.copy()
                tmp_path.pop()
            else:
                for path_ in self.searchPath:
                    tmp_path = path_.copy()
                    tmp = tmp_path[len(tmp_path) - 1]
                    if tmp.is_neighbor(v_):
                        tmp_path.append(v_)
                        self.searchPath.append(tmp_path)
            if v_.v_id == to_v.v_id:
                break
            else:
                self.push_queue(v_)

    '''
     把某一頂點(diǎn)的相鄰頂點(diǎn)壓入隊(duì)列
     '''
    def push_queue(self, vertex):
        # 獲取 vertex 頂點(diǎn)的相鄰頂點(diǎn)
        for v_ in vertex.connected_to.keys():
            # 檢查此頂點(diǎn)是否壓入過
            if v_.visited:
                continue
            vertex.visited = True
            self.queue_stack.append(v_)

'''
測(cè)試無向圖最短路徑
'''

if __name__ == '__main__':
    # 初始化圖
    graph = Graph()
    # 添加節(jié)點(diǎn)
    for v_name in ['A', 'B', 'C', 'D', 'E', 'F']:
        v = Vertex(v_name)
        graph.add_vertex(v)

    # 添加頂點(diǎn)之間關(guān)系
    v_to_v = [('A', 'B'), ('A', 'D'), ('B', 'C'), ('C', 'E'), ('D', 'E'), ('E', 'F')]
    # 無向圖中每 2 個(gè)相鄰頂點(diǎn)之間互為關(guān)系
    for v in v_to_v:
        f_v = graph.find_vertex(v[0])
        t_v = graph.find_vertex(v[1])
        graph.add_edge(f_v, t_v)
        graph.add_edge(t_v, f_v)

    # 輸出所有頂點(diǎn)
    print('-----------頂點(diǎn)及頂點(diǎn)之間的關(guān)系-------------')
    for v in graph.find_vertexes():
        print(v)

    # 查找路徑
    print('-------------廣度優(yōu)先搜索--------------------')
    # 起始點(diǎn)
    f_v = graph.find_vertex('A')
    # 目標(biāo)點(diǎn)
    t_v = graph.find_vertex('F')
    # 廣度優(yōu)先搜索
    graph.bfs_nearest_path(f_v, t_v)
    for path in graph.searchPath:
        weight = 0
        for idx in range(len(path)):
            if idx != len(path) - 1:
                weight += path[idx].get_weight(path[idx + 1])
            print(path[idx].v_name, end='-')
        print("的最短路徑長度，", weight)

    '''
    遞歸實(shí)現(xiàn)
    '''

    def bfs_nearest_path_dg(self, from_v, to_v):

        # 相鄰頂點(diǎn)
        self.push_queue(from_v)
        tmp_v = self.queue_stack.pop(0)
        if not tmp_v.visited:
            self.searchPath.append(tmp_v)
        if tmp_v.v_id == to_v.v_id:
            return

        self.bfs_nearest_path_dg(tmp_v, to_v)