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