输入形如"a-b,b-c,b-d"的字符串,计算最远路径

一道算法题,输入形如"a-b,b-c,b-d"的字符串,表示a点到b点(b到c、b到d)相邻且有路,假定没有形成环状,要求输出最远路径的数值,
比如:输入"a-b,b-c,b-d"时,输出应该为2,因为最远路径为"a-b-c"或"a-b-d"或其他,最远经过2段路。还比如:
输入(邻近点的路径):"b-e,b-c,c-d,a-b,e-f"
输出(最远的距离数):4
代码思路:
1、先处理输入数据,得到全部邻近路径和全部点;
2、构造函数,可搜寻出某点的全部一阶路径;
3、构造函数,可搜寻出某点的全部二阶路径;
4、根据二阶路径函数,得到思路,构造出“给定某点的n阶路径,搜寻全部n+1阶路径”的函数;
5、设置死循环,得到某点的最高阶路径;
6、选出所有点中的最远的路径,输出。
代码如下:
def FarthestNodes(strPath: str):
    path_list = strPath.replace('-', '').split(',')  # ['ab', 'bc', 'bd']
    # print('path_list:',path_list)
    # 全部的点
    node_list = list(set(''.join(path_list)))  # ['c', 'a', 'd', 'b']
    node_list.sort()  # ['a', 'b', 'c', 'd']

    # print('node_list:',node_list)

    # 搜寻某点的全部一阶路径
    def search_degree1_path(node: str):
        node_degree1_list = []
        for path in path_list:
            if node in path:
                if node == path[1]:
                    path = path[1] + path[0]
                node_degree1_list.append(path)
        return node_degree1_list

    # node0_degree1_list = search_degree1_path(node_list[3])
    # print('node_degree1_list',node0_degree1_list)

    # 搜寻某点的全部二阶路径
    def search_degree2_path(node: str):
        degree1_path_list = search_degree1_path(node)
        degree2_path_list = []
        for path in degree1_path_list:
            # 以一阶路径为基础,搜索延续点(第二个点)的全部一阶路径,也就是原点(第一个点)的二阶路径
            second_degree1_list = search_degree1_path(path[-1])
            # 删除包含原点的路径,即只保留去往第三点的路径
            second_degree1_list_simple = [p for p in second_degree1_list if path[-2] not in p]
            # 原点到本延续点的全部二阶路径
            degree2_path_part_list = [path[:-1] + p for p in second_degree1_list_simple]
            # 全部延续点的路径加到一起,形成原点的全部二阶路径
            degree2_path_list.extend(degree2_path_part_list)
        return degree2_path_list

    # node0_degree2_list = search_degree2_path(node_list[3])
    # print('node_degree2_list',node0_degree2_list)

    # 给定某点的n阶路径,搜寻全部n+1阶路径;举例:已知2阶路径,求3阶路径;根据二阶路径函数修改而得
    def search_degree_higher_path(node_degree_list: list):
        degree_higher_path_list = []
        for path in node_degree_list:
            # 以n阶路径为基础,搜索第n+1个点的全部一阶路径,举例:以2阶路径为基础,搜索第3个点的一阶路径
            second_degree1_list = search_degree1_path(path[-1])
            # 删除包含上一阶节点(第n个点)的路径,举例:以2阶路径为基础,删除返回第2个点的路径
            second_degree1_list_simple = [p for p in second_degree1_list if path[-2] not in p]
            # 原有n阶路径+本节点下全部一阶路径,得到本节点下全部n+1阶路径
            degree_higher_path_part_list = [path[:-1] + p for p in second_degree1_list_simple]
            # 全部节点的路径加到一起,形成原点的全部n+1阶路径
            degree_higher_path_list.extend(degree_higher_path_part_list)
        return degree_higher_path_list

    for node in node_list:
        node_degree_list = search_degree1_path(node)
        node_highest_degree_list = node_degree_list
        length = 1
        farthest_length = 1
        farthest_path = node_highest_degree_list
        while True:
            node_degree_higher_list = search_degree_higher_path(node_degree_list)
            if node_degree_higher_list:
                node_highest_degree_list = node_degree_higher_list
                length += 1
            else:
                break
            node_degree_list = node_degree_higher_list
        # print(f'node {node} highest_degree_path_list:',node_highest_degree_list)
        # print(f'node {node} length:',length)
        if length > farthest_length:
            farthest_length = length
            farthest_path = node_highest_degree_list
    # print('farthest_length:', farthest_length)
    # print('one of farthest_path:', farthest_path)
    return farthest_length,farthest_path


if __name__ == '__main__':
    # 输入相邻路径,得到最远路径
    input_path = "b-e,b-c,c-d,a-b,e-f"
    farthest_length,farthest_path = FarthestNodes(input_path)
    print('farthest_length:', farthest_length)
    print('one of farthest_path:', farthest_path)

 

上一篇:Codeforces Round #646 (Div. 2) C. Game On Leaves(树上博弈)


下一篇:潭州课堂25班:Ph201805201 WEB 之 HTML 第一课 (课堂笔记)