python-圖論最短路徑算法

python-圖論最短路徑算法

一、深度優先算法、廣度優先算法差別

'''

查找最短路徑

定義：

v = 頂點

t = 目标頂點

v1 = 子頂點

廣度優先算法：優先周遊 v 的所有鄰接頂點，在所有鄰接頂點中查找 t，直到所有頂點都通路過；

深度優先算法：優先周遊 v 的第一個 v1，如果 v1 存在子頂點則繼續深入查找，直到以 v 為頂點的所有子節點通路過；

'''

二、執行結果

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

廣度優先搜尋過程

a ['b', 'c']

b ['a', 'c']

c ['a', 'd']

d ['e']

e ['d']

搜尋 a -> e 最短路徑

結果=e    times=4    searched=['a', 'b', 'c', 'd', 'e']

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

深度優先搜尋過程

a ['b', 'c']

b ['a', 'c']

c ['a', 'd']

d ['e']

e ['d']

#!/usr/bin/env python3
# coding=utf-8

'''
查找最短路徑
    定義：
        v = 頂點
        t = 目标頂點
        v1 = 子頂點
    廣度優先算法：優先周遊 v 的所有鄰接頂點，在所有鄰接頂點中查找 t，直到所有頂點都通路過；
    深度優先算法：優先周遊 v 的第一個 v1，如果 v1 存在子頂點則繼續深入查找，直到以 v 為頂點的所有子節點通路過；
'''
from collections import deque

times = 0
tragetNode = None

def getGrahp():
    gp = {
        "a":["b","c"],
        "b":["a","c"],
        "c":["a","d"],
        "d":["e"],
        "e":["d"]
    }
    return gp

def search_widest(start,target):
    '''
    廣度優先搜尋：
    （1）頂點v入隊列。
    （2）當隊列非空時則繼續執行，否則算法結束。
    （3）出隊列取得隊頭頂點v；通路頂點v并标記頂點v已被通路。
    （4）查找頂點v的第一個鄰接頂點v1。
    （5）若v的鄰接頂點v1未被通路過的，則v1入隊列。
    （6）繼續查找頂點v的另一個新的鄰接頂點v1，轉到步驟（5）。直到頂點v的所有未被通路過的鄰接點處理完。轉到步驟（2）。
    '''
    global times
    global tragetNode
    gp = getGrahp() # 圖
    searched = [start] # 已經搜尋過的頂點
    search_queue = deque() # 搜尋隊列
    search_queue += gp[start]
    tragetNode = None
    print('\n%s\n廣度優先搜尋過程'%('~'*30))
    print(start,gp[start])
    while search_queue:
        v = search_queue.popleft() # 出隊一個待搜尋頂點
        if v in searched or v not in gp.keys():
            continue
        print(v,gp[v])
        times += 1
        searched.append(v)
        if v == target:
            tragetNode = v
            break
        else:
            search_queue += gp[v] # 待搜尋頂點搜尋隊列
    print('\n')
    print('搜尋 %s -> %s 最短路徑'%(start,target))
    print('結果=%s\ttimes=%s\tsearched=%s'%(tragetNode,times,searched))

def search_deep(start,target):
    '''
    深度優先搜尋：
    （1）通路初始頂點v并标記頂點v已通路。
    （2）查找頂點v的第一個鄰接頂點w。
    （3）若頂點v的鄰接頂點w存在，則繼續執行；否則回溯到v，再找v的另外一個未通路過的鄰接點。
    （4）若頂點w尚未被通路，則通路頂點w并标記頂點w為已通路。
    （5）繼續查找頂點w的下一個鄰接頂點wi，如果v取值wi轉到步驟（3）。直到連通圖中所有頂點全部通路過為止。
    '''
    global times
    global tragetNode
    times = 0
    tragetNode = None
    gp = getGrahp() # 圖
    print('\n%s\n深度優先搜尋過程'%('~'*30))
    searched = []
    def func(v):
        global times
        global tragetNode
        if v in searched or v not in gp.keys():
            return
        times += 1
        searched.append(v)
        print(v,gp[v])
        if v == target:
            tragetNode = v
            return
        for v1 in gp[v]:
            func(v1)
    func(start)
    print('\n')
    print('搜尋 %s -> %s 最短路徑'%(start,target))
    print('結果=%s\ttimes=%s\tsearched=%s'%(tragetNode,times,searched))



def main():
    start = 'a'
    target = 'e'
    search_widest(start,target)
    search_deep(start,target)

if __name__ == '__main__':
    main()