问Prim算法回溯Python

EN

def lowest_cost(conduits_info_str):
    graph = conduits_info_str.splitlines()
    num_vertices = int(graph[0].split()[1])
    graph = graph[1:]
    adj_list = adjacency_list(conduits_info_str)
    num_edges = len(adj_list)
    visited = []
    cost = 0
    if num_edges > 0:
        visited.append(int(graph[0].split()[0]))
    print(adj_list)
    while len(visited) < len(adj_list):
        print("Next Node: ",visited[-1])
        minimum = adj_list[visited[-1]][0][1]
        min_vertex = adj_list[visited[-1]][0][0]  
        for each in adj_list[visited[-1]]:
            if each[1] < minimum and each[0] not in visited:
                min_vertex = each[0]
                minimum = each[1]
            visited.append(min_vertex)

    return adj_list





def adjacency_list(graph_str):
    is_weighted = False
    is_directed = False
    graph_list = graph_str.splitlines()
    num_verticies = int(graph_list[0].split()[1])
    graph_list.pop(0)
    adj_list = [[] for _ in range(num_verticies)]

    if 'D' in graph_str:
        is_directed = True
    if 'W' in graph_str:
        is_weighted = True


    if is_weighted == True:
        for line in graph_list:
            line_list = line.split()
            a = int(line_list[0])
            b = int(line_list[1])
            c = int(line_list[2])
            adj_list[int(a)].append((b,c))
    else:
        for line in graph_list:
            line_list = line.split()
            i = int(line_list[0])
            j = int(line_list[1])
            if not is_directed:
                adj_list[j].append((i, None))            
            adj_list[int(i)].append((j, None))
    return adj_list


conduits_info = """\
U 7 W
0 1 5
0 2 7
0 3 12
1 2 9
2 3 4
1 4 7
2 4 4
2 5 3
3 5 7
4 5 2
4 6 5
5 6 2
"""

print(lowest_cost(conduits_info))

[[(1, 5), (2, 7), (3, 12)], [(2, 9), (4, 7)], [(3, 4), (4, 4), (5, 3)],[(5, 7)], [(5, 2), (6, 5)], [(6, 2)], []]

visited_list = [0, 1, 4, 5]

minimum = adj_list[visited[-1]][0][1]
    min_vertex = adj_list[visited[-1]][0][0]