树算法笔记（三）：Prim最小生成树

data=‘‘‘2 4 11
3 5 13
4 6 3
5 6 4
2 3 6
4 5 7
1 2 1
3 4 9
1 3 2‘‘‘

lines=data.split("\n")
for i,line in enumerate(lines):
    lines[i]=list(map(int,line.split(" ")))

adj=[[-1]*7 for i in range(7)]
for line in lines:
    adj[line[0]][line[1]]=line[2]
    adj[line[1]][line[0]]=line[2]

# for x in range(7):
#     for y in range(7):
#         if adj[x][y]==-1:
#             adj[x][y]=float("inf")

dis=[float("inf") for i in range(7)]
dis[1]=0
vertex=[i for i in range(1,7)]
path=[1]
path_value=[0]

def dfs(v):
    if len(path)==6:
        return
    for y,e in enumerate(adj[v]):
        if e!=-1 and e<dis[y]:
            dis[y]=e
    
    minx=float("inf")
    mini=0
    for i in range(7):
        if dis[i]!=0 and dis[i]!=float("inf") and i not in path and dis[i]<minx:
            minx=dis[i]
            mini=i
    path.append(mini)
    path_value.append(minx)
    dfs(mini)
    
        
dfs(1)
print(path,path_value)