一、讨论题

略

二、编程练习

1.修改深度优先搜索函数，以进行拓扑排序。

&

2.修改深度优先搜索函数，以计算强连通分量。

&

3.修改深度优先搜索函数，以计算强连通分量。

Graph.py:

class Vertex:
    def __init__(self, key):
        self.id = key
        self.connectedTo = {}

        self.distance = 0
        self.color = 'white'
        self.pred = None

        self.discovery = 0
        self.finish = 0


    def addNeighbor(self, nbr, weight=0):
        self.connectedTo[nbr] = weight

    def __str__(self):
        return f'<Vertex id:{self.id} time:({self.discovery}/{self.finish}) ' \
               f'color:{self.color} predecessor:{self.pred.id if self.pred else None} ' \
               f'connect_to:{[v.id for v in self.connectedTo]}>'
        # return str(self.id) + ' connectedTo: ' + str([x.id for x in self.connectedTo])

    def __lt__(self, other):
        return self.id < other.id

    def __eq__(self, other):
        return self.id == other.id

    def __hash__(self):
        return super().__hash__()

    def getConnections(self):
        return self.connectedTo.keys()

    def getId(self):
        return self.id

    def getWeight(self, nbr):
        return self.connectedTo[nbr]

    def getDistance(self):
        return self.distance

    def setDistance(self, distance):
        if distance > 0:
            self.distance = distance

    def getColor(self):
        return self.color

    def setColor(self, color):
        self.color = color

    def getPred(self):
        if self.pred:
            return self.pred
        else:
            return None

    def setPred(self, pred):
        self.pred = pred

    def setDiscovery(self, value):
        self.discovery = value

    def setFinish(self, value):
        self.finish = value


class Graph:
    def __init__(self):
        self.vertList = {}
        self.numVertices = 0

    def addVertex(self, key):
        self.numVertices += 1
        newVertex = Vertex(key)
        self.vertList[key] = newVertex
        return newVertex

    def getVertex1(self, n):
        if n in self.vertList:
            return self.vertList[n]
        else:
            return None

    def getVertex(self, key):
        vertex = None
        if key in self.vertList:
            vertex = self.vertList[key]
        return vertex

    def get_vertex(self, key) -> Vertex:
        vertex = None
        if key in self.vertList:
            vertex = self.vertList[key]

        return vertex

    def __contains__(self, item):
        return item in self.vertList

    def addEdge(self, f, t, cost=0):
        if f not in self.vertList:
            nv = self.addVertex(f)
        if t not in self.vertList:
            nv = self.addVertex(t)
        self.vertList[f].addNeighbor(self.vertList[t], cost)

    def getVertices(self):
        return self.vertList.keys()

    def __iter__(self):
        return iter(self.vertList.values())

    def get_all_vertex(self):
        return list(self.vertList.keys())



if __name__ == '__main__':
    g = Graph()
    for i in range(6):
        g.addVertex(i)

    print(g.vertList)
    g.addEdge(0, 1, 5)
    g.addEdge(0, 5, 2)
    g.addEdge(1, 2, 4)
    g.addEdge(2, 3, 9)
    g.addEdge(3, 4, 7)
    g.addEdge(3, 5, 3)
    g.addEdge(4, 0, 1)
    g.addEdge(5, 4, 8)
    g.addEdge(5, 2, 1)

    for v in g:
        for w in v.getConnections():
            print('( %s, %s)' % (v.getId(), w.getId()))

from chapter7.Graph import Graph

class DFSGraph(Graph):
    def __init__(self):
        super(DFSGraph, self).__init__()
        self.time = 0

        self.__sort_list = []
        self.__scc_list = []

    def _initial_visit(self):
        self.time = 0
        self.__sort_list = []
        self.__scc_list = []
        for vertex in self:
            vertex.setColor('white')
            vertex.setPred(None)

    def _dfs(self, vertex):
        self.time += 1
        vertex.setColor('gray')
        vertex.setDiscovery(self.time)

        for neighbor in vertex.getConnections():
            if neighbor.getColor() == 'white':
                neighbor.setPred(vertex)
                self._dfs(neighbor)


        self.time += 1
        vertex.setColor('black')
        vertex.setFinish(self.time)
        self.__sort_list.append(vertex)
        self.__scc_list[-1].append(vertex)

    def _transpose(self):
        gt = DFSGraph()
        for vertex in self:
            for neighbor in vertex.getConnections():
                gt.addEdge(neighbor.id, vertex.id)
        return gt

    def dfs(self, vertex_list=None):
        self._initial_visit()
        if vertex_list is None:
            vertex_list = self
        for vertex in vertex_list:
            if vertex.getColor() == 'white':
                self.__scc_list.append(list())
                self._dfs(vertex)

    def topo_sort(self):
        self.dfs()
        self.__sort_list.reverse()
        return self.__sort_list


    def scc(self):
        topo = self.topo_sort()
        gt = self._transpose()
        for vid, vertex in enumerate(topo):
            topo[vid] = gt.getVertex(vertex.id)
        gt.dfs(topo)
        scc_mp = {}
        for scc in gt.__scc_list:
            value = scc[::-1]
            key = ''.join(str(v.id) for v in value)
            scc_mp[key] = value
        return scc_mp

def topo_sort(g):
    g.dfs()
    ans = []
    for vertex in g:
        ans.append(vertex)
    ans.sort(key=lambda v: v.finish, reverse=True)
    return ans

def show_scc(g):
    scc_mp = g.scc()
    for key, scc in scc_mp.items():
        print(f'scc_id: {key}')
        print(f'scc: [{" -> ".join(str(v.id) for v in scc)}]')
        print('*' * 30)

if __name__ == '__main__':

    g = DFSGraph()
    # tasks = ['3/4杯牛奶', '一个鸡蛋', '一勺油', '一杯松饼粉', '加热平底锅',
    #          '倒入1/4杯', '出现气泡时翻面', '加热枫糖浆', '开始享用']
    # g.addEdge(tasks[0], tasks[3])
    # g.addEdge(tasks[4], tasks[5])
    # g.addEdge(tasks[1], tasks[3])
    # g.addEdge(tasks[2], tasks[3])
    # g.addEdge(tasks[3], tasks[5])
    # g.addEdge(tasks[3], tasks[7])
    # g.addEdge(tasks[5], tasks[6])
    # g.addEdge(tasks[6], tasks[8])
    # g.addEdge(tasks[7], tasks[8])
    # task_list = topo_sort(g)
    # print(' -> '.join(str(t.id) for t in task_list))
    #
    # # DFSGraph内置拓扑排序[O(n)]
    # print(' -> '.join(str(v.id) for v in g.topo_sort()))
    g.addEdge('A', 'B')
    g.addEdge('B', 'C')
    g.addEdge('B', 'E')
    g.addEdge('C', 'C')
    g.addEdge('C', 'F')
    g.addEdge('D', 'B')
    g.addEdge('D', 'G')
    g.addEdge('E', 'A')
    g.addEdge('E', 'D')
    g.addEdge('F', 'H')
    g.addEdge('G', 'E')
    g.addEdge('H', 'I')
    g.addEdge('I', 'F')
    show_scc(g)

4.使用广度优先搜索实现一个算法，用以计算从每一个顶点到其余所有顶点的最短路径。这被称为所有对最短路径。

from chapter7.Graph import Vertex, Graph
from chapter3.queue import Queue


def bfs(g, start, end):
    start = g.getVertex(start)
    end = g.getVertex(end)
    if start is None or end is None:
        raise ValueError(f'{start}或{end}不在单词表中')
    start.setDistance(0)
    start.setPred(None)
    vertQueue = Queue()
    vertQueue.enqueue(start)
    while (vertQueue.size() > 0):

        currentVert = vertQueue.dequeue()
        for nbr in currentVert.getConnections():
            if (nbr.getColor() == 'white'):
                nbr.setColor('gray')
                nbr.setDistance(currentVert.getDistance() + 1)
                nbr.setPred(currentVert)
                vertQueue.enqueue(nbr)
        currentVert.setColor('black')
    return currentVert.distance

def traverse(g, y):
    x = g.getVertex(y)
    # x = y
    while (x.getPred()):
        print(x.getId())
        x = x.getPred()
    print(x.getId())

def traversal(g: Graph, end) -> list:
    res = []
    vertex = g.getVertex(end)
    while vertex:
        res.append(vertex.id)
        vertex = vertex.pred

    return res

if __name__ == '__main__':
    g = Graph()
    g.addEdge('A', 'B')
    g.addEdge('A', 'D')
    g.addEdge('B', 'C')
    g.addEdge('B', 'D')
    g.addEdge('D', 'E')
    g.addEdge('E', 'B')
    g.addEdge('E', 'F')
    for start_vertex in g:
        for end_vertex in g:
            if start_vertex.id != end_vertex.id:
                distance = bfs(g, start_vertex.id, end_vertex.id)
                print(f'the distance from {start_vertex.id} to {end_vertex.id} is: ')
                trace = traversal(g, end_vertex.id)
                if trace[-1] == start_vertex.id:
                    print(' -> '.join(trace[::-1]))
                else:
                    print('None')


    # start, end = 'C', 'E'
    # distance = bfs(g, start, end)
    # print(f'the distance from {start} to {end} is: {distance}')
    # trace = traversal(g, end)
    # if len(trace) > 1:
    #     print(' -> '.join(trace[::-1]))
    # else:
    #     print('None')
    # traverse(g, end)
    # print('->'.join(trace[::-1]))

5.使用广度优先搜索修改第4章中的迷宫程序，从而找到走出迷宫的最短路径。

BFS迷宫（不会改……直接在网上找的，嗯感觉结果不太对……）

# -*- coding: utf-8 -*-
"""
Created on Tue Apr 27 13:48:14 2021

@author: Administrator
"""

###无递归、类求迷宫最短路径算法
# import random
pre_route = list()  # 宽度搜索得到的节点
q = list()  # 队列结构控制循环次数
xx = [0, 1, 0, -1]  # 右移、下移、左移、上移
yy = [1, 0, -1, 0]
visited = list()  # 记录节点是否已遍历
father = list()  # 每一个pre_route节点的父节点
route = list()


def bfs(l, x, y, m, n):
    visited = [[0 for i in range(len(l[0]))] for j in range(len(l))]
    visited[x][y] = 1  # 入口节点设置为已遍历
    q.append([x, y])
    while q:  # 队列为空则结束循环
        now = q[0]
        q.pop(0)  # 移除队列头结点
        for i in range(4):
            point = [now[0] + xx[i], now[1] + yy[i]]  # 当前节点
            if point[0] < 0 or point[1] < 0 or point[0] >= len(l) or point[1] >= len(l[0]) or visited[point[0]][
                point[1]] == 1 or l[point[0]][point[1]] == '1':
                continue
            father.append(now)
            visited[point[0]][point[1]] = 1
            q.append(point)
            pre_route.append(point)
            if point[0] == m and point[1] == n:
                print("success")
                return 1
    print("false")
    return 0


def get_route(father, pre_route):  # 输出最短迷宫路径
    route = [pre_route[-1], father[-1]]
    for i in range(len(pre_route) - 1, -1, -1):
        if pre_route[i] == route[-1]:
            route.append(father[i])
    route.reverse()
    print("迷宫最短路径为：\n", route)
    print("步长：", len(route) - 1)
    return route


def prn_map(route, l, m, n):  # 打印包含路径的迷宫图
    for i in range(len(l)):
        l[i] = list(l[i])
    for i in range(len(route)):
        l[route[i][0]][route[i][1]] = '2'
    for i in range(len(l)):
        for j in range(len(l[0])):
            if l[i][j] == '1':
                print('  ', end='')
            elif l[i][j] == '0':
                print('██', end='')
            else:
                print('░░', end='')
            if i == m and j == n:
                print('☀', end='')
        print()


l = ['01010101001011001001010110010110100100001000101010',
     '00001000100000101010010000100000001001100110100101',
     '01111011010010001000001101001011100011000000010000',
     '01000000001010100011010000101000001010101011001011',
     '00011111000000101000010010100010100000101100000000',
     '11001000110101000010101100011010011010101011110111',
     '00011011010101001001001010000001000101001110000000',
     '10100000101000100110101010111110011000010000111010',
     '00111000001010100001100010000001000101001100001001',
     '11000110100001110010001001010101010101010001101000',
     '00010000100100000101001010101110100010101010000101',
     '11100100101001001000010000010101010100100100010100',
     '00000010000000101011001111010001100000101010100011',
     '10101010011100001000011000010110011110110100001000',
     '10101010100001101010100101000010100000111011101001',
     '10000000101100010000101100101101001011100000000100',
     '10101001000000010100100001000100000100011110101001',
     '00101001010101101001010100011010101101110000110101',
     '11001010000100001100000010100101000001000111000010',
     '00001000110000110101101000000100101001001000011101',
     '10100101000101000000001110110010110101101010100001',
     '00101000010000110101010000100010001001000100010101',
     '10100001000110010001000010101001010101011111010010',
     '00000100101000000110010100101001000001000000000010',
     '11010000001001110111001001000011101001011011101000',
     '00000110100010001000100000001000011101000000110011',
     '10101000101000100010001111100010101001010000001000',
     '10000010100101001010110000000100101010001011101000',
     '00111100001000010000000110111000000001000000001011',
     '10000001100111010111010001000110111010101101111000']

if __name__ == '__main__':
    x = 0;
    y = 0
    m = 25;
    n = 40
    if bfs(l, x, y, m, n) == 1:
        route = get_route(father, pre_route)
        prn_map(route, l, m, n)

6.写一个程序来解决这样一个问题：有2个坛子，其中一个的容量是4加仑，另一个的是3加仑。坛子上都没有刻度线。可以用水泵将它们装满水。如何使4加仑的坛子最后装满2加仑的水？

&

7.扩展练习6中的程序，将坛子的容量和较大的坛子中最后的水量作为参数。

水壶问题：源代码有注释

import queue
import numpy as np

class Kettle:
    def __init__(self, w1, w2, result):
        self.w1 = w1
        self.w2 = w2
        self.result = result
        self.x = 0
        self.y = 0
        self.state_space = np.zeros((self.w1 + 1, self.w2 + 1))
        self.q_temp = queue.Queue()
        self.final = []
        self.final_only_data = [[0, 0]]

    def BFS(self):
        self.q_temp.put([0, 0])
        self.final.append([[0, 0], 'none', [0]])
        self.state_space[0][0] = 1
        while len(self.q_temp.queue) != 0:
            a, b = self.q_temp.get()
            if a == self.result or b == self.result:
                continue
            pre = [a, b]
            self.x, self.y = a, b
            self.Pour_X()
            self.update(pre, a, b, 'Pour_X')

            self.Pour_Y()
            self.update(pre, a, b, 'Pour_Y')

            self.Empty_X()
            self.update(pre, a, b, 'Empty_X')

            self.Empty_Y()
            self.update(pre, a, b, 'Empty_Y')

            self.Pour_X_To_Y()
            self.update(pre, a, b, 'Pour_X_To_Y')

            self.Pour_Y_To_X()
            self.update(pre, a, b, 'Pour_Y_To_X')

        return self.final, self.final_only_data


    def update(self, pre, a, b, name):
        if self.state_space[self.x][self.y] == 0:
            self.state_space[self.x][self.y] = 1
            self.q_temp.put([self.x, self.y])
            self.final_only_data.append([self.x, self.y])
            self.final.append([[self.x, self.y], name, pre])
        self.x, self.y = a, b

    def Pour_X(self):
        self.x = self.w1
        return True

    def Pour_Y(self):
        self.y = self.w2
        return True

    def Empty_X(self):
        self.x = 0
        return True

    def Empty_Y(self):
        self.y = 0
        return True

    def Pour_X_To_Y(self):
        if (self.x + self.y) <= self.w2:
            self.y += self.x
            self.x = 0
        else:
            self.x = self.x - (self.w2 - self.y)
            self.y = self.w2
        return True

    def Pour_Y_To_X(self):
        if (self.x + self.y) <= self.w1:
            self.x += self.y
            self.y = 0
        else:
            self.y = self.y - (self.w1 - self.x)
            self.x = self.w1
        return True

if __name__ == '__main__':
    kettle = Kettle(3, 4, 2)
    final_list, tmp_list = kettle.BFS()
    result = []
    for i in range(len(final_list)):
        if i == 0:
            continue
        data = final_list[i]
        print('每行的数据为:', data)
        pre = data[2]
        print('当前的父节点为:', pre)
        pre_index = tmp_list.index(pre)
        print('当前父节点在列表中的位置为:', pre_index)
        result = final_list[pre_index][-1]
        print('当前父节点的路径为:', result)
        a = result.copy()
        a.append(i)
        final_list[i][-1] = a
        print('*********************************************')


        def output(order):
            print('x' + '\t' + 'y' + '\t' + 'method')
            for i in order:
                print(*final_list[i][0], sep='\t', end='\t')
                print(final_list[i][1])


        con = 0
        for i in range(len(tmp_list)):
            if 2 in tmp_list[i]:
                print(f'-------------方法{con}--------------')
                order = final_list[i][-1]
                output(order)
                con += 1

8.写一个程序来解决这样一个问题：3只羚羊和3只狮子准备乘船过河，河边有一艘能容纳2只动物的小船。但是，如果两侧河岸上的狮子数量大于领养数量，羚羊就会被吃掉。找到运送办法，使得所有动物都能安全渡河。

用图解决过河问题

from chapter7.Graph import Graph
from chapter3.queue import Queue

def solution():
    '''
    3只羚羊和3只狮子过河问题:
        1艘船只能容纳2只动物
        当河岸上狮子数大于羚羊数，羚羊就会被吃掉
        找到运输方法，让所有动物都过河
    '''

    # 定义合法的运输操作(i, j) , 例如(1, 0)表示运送羚羊1只，狮子0只
    opt = [(1, 0), (0, 1), (1, 1), (2, 0), (0, 2)]

    # 定义状态state(m, n, k), m表示羚羊数，n表示狮子数，k表示船在此岸还是彼岸
    # stateA 表示A岸（此岸）的状态；stateB 表示B岸（彼岸）的状态；

    # 初始状态
    stateA = (3, 3, 1)
    stateB = (0, 0, 0)

    # BFS搜索
    mygraph = Graph()
    myqueue = Queue()
    myqueue.enqueue((stateA, stateB))
    sequence = []  # 剪枝记录（最后发现，有效状态只有15种）
    sequence.append((stateA))
    while True:
        stateA, stateB = myqueue.dequeue()

        if stateA == (0, 0, 0):
            break
        for o in opt:
            # 一次从某岸到另一岸的运输
            if stateA[2] == 1:
                stateA_ = (stateA[0] - o[0], stateA[1] - o[1], stateA[2] - 1)
                stateB_ = (stateB[0] + o[0], stateB[1] + o[1], stateB[2] + 1)
            else:
                stateB_ = (stateB[0] - o[0], stateB[1] - o[1], stateB[2] - 1)
                stateA_ = (stateA[0] + o[0], stateA[1] + o[1], stateA[2] + 1)

            # 运输后
            if stateA_[0] and stateA_[0] < stateA_[1]:  # 此岸在有羊的情况下，如果狼大于羊，则吃掉
                continue
            elif stateB_[0] and stateB_[0] < stateB_[1]:  # 彼岸在有羊的情况下，如果狼大于羊，则吃掉
                continue
            elif stateA_[0] < 0 or stateA_[0] > 3 or stateA_[1] < 0 or stateA_[1] > 3:  # 边界
                continue
            else:
                # 剪枝
                if stateA_ in sequence:
                    continue
                else:
                    sequence.append(stateA_)
                    myqueue.enqueue((stateA_, stateB_))
                    mygraph.addEdge(stateA, stateA_, o)

    return mygraph, sequence
if __name__ == '__main__':
    g, sq = solution()

    # 建立父子关系
    for v_n in sq:
        v = g.getVertex(v_n)

        for nbr in v.getConnections():
            if nbr.getColor() == 'white':
                nbr.setPred(v)
                nbr.setColor('gray')
        v.setColor('black')
    target = g.getVertex(sq[-1])

    # 回溯，显示决策路径
    i = 0
    while target.getPred():
        predv = target.getPred()
        print(target.id, '<--', predv.getWeight(target), '--', predv.id)

        target = predv
        i += 1

三、总结

主要学习了

1.用python表示图这种抽象数据类型，
2.BFS找到无权重的最短路径：词梯问题，
3.Dijkstra算法求解带权重的最短路径，
4.使用强连通分量来简化图，
5.拓扑排序：任务有先后，
6.利用Prim最小生成树广播消息。