1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
# 使用散列表来表示图
class GraphItem:


class Graph:
    item = {}

    # 向图中加入顶点

    # 删除顶点
    def dl


广度优先算法

 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
# 在图 graph 中从 start 到 item 的广度优先算法
def breadth_first_search(start, item):
    import queue
    search_queue = queue.Queue()
    # 将 start 顶点的邻接点加入到队列中
    for element in start['neighbors']:
        if match(element, item):
            return True
        else:
            # 顶点标记为灰, 表示已经入队查找过
            element['mark'] = 'gray'
            search_queue.put(element)
    # 查找队列
    while not search_queue.empty():
        # 获得队列中顶点
        element = search_queue.get()
        element['mark'] = 'black'
        for node in element['neighbors']:
            # 白色表示还没搜索过的顶点
            if node['mark'] == 'white':
                if match(node, item):
                    return True
                else:
                    # 顶点标记为灰, 表示已经入队查找过
                    node['mark'] = 'gray'
                    search_queue.put(node)

加权图和狄克斯特拉算法(Dijkstra’s algorithm)

边带权重(weight)的图称为加权图

使用Dijkstra's algorithm算法计算加权图中顶点到顶点之间边之各权重为最大或最小

狄克斯特拉算法只能计算有向, 无循环, 权重为正的加权图

  1. 找出最便宜的节点,即可在最短时间内前往的节点
  1. 对于该节点的邻居,检查是否有前往它们的更短路径,如果有,就更新其开销
  1. 重复这个过程,直到对图中的每个节点都这样做了(先行标注终点, 不对终点的邻接点再做处理)
  1. 计算最终路径。
 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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
graph = {
    'compare': lambda x, y:  x < y,
    's': {'a': 24, 'b': 10},
    'a': {'d': 4},
    'b': {'c': 5, 'e': 8},
    'c': {'d': 5, 'a': 1},
    'd': {'f': 4},
    'e': {'d': 12},
    'f': {}
}




def dikjistra_algorithm(graph, start, end):
    if start not in graph or end not in graph:
        return None
    # 已处理过的顶点, 不再搜索其邻接点
    processed = [end]
    # 到某个顶点的最小权重需经过的上一顶点
    parents = {k: start for k in graph[start]}
    # 到某个顶点需要的最小权重
    costs = {key: value for key, value in graph[start].items()}
    # 每次从 costs 里找到最小权重的顶点来搜索其邻接点
    def find_lowest_cost_node(costs):
        lowest_cost = None
        lowest_cost_node = None
        for node in costs:
            if node not in processed:
                lowest_cost = lowest_cost if lowest_cost else costs[node]
                lowest_cost_node = lowest_cost_node if lowest_cost_node else node
                cost = costs[node]
                if graph.get('compare')(cost, lowest_cost):
                    lowest_cost = cost
                    lowest_cost_node = node
        return lowest_cost_node

    node = find_lowest_cost_node(costs)
    while node is not None:
        cost = costs[node]
        neighbors = graph[node]
        for n in neighbors.keys():
            new_cost = cost + neighbors[n]
            if n in costs and graph.get('compare')(costs[n], new_cost):
                continue
            costs[n] = new_cost
            parents[n] = node
        processed.append(node)
        node = find_lowest_cost_node(costs)
    route = []
    cost = costs[end]
    while end != start:
        route.append(end)
        end = parents[end]
    route.append(start)
    return {'route': route[-1::-1], 'cost': cost}

result = dikjistra_algorithm(graph, 's', 'f')
print('parents: ', end='')
print(result['route'])
print('costs: ', end='')
print(result['cost'])