如何插入txt， txt文件里面有matrix, 如何在python用minimum spanning tree 的算法来运行matrix， 并得出结果
如何插入任意一个txt文件，txt文件里面有一个matrix，matrix可以是任意的， 例如， 55， 66.
如何用minimum spanning tree 的kruskal算法来算出结果
我的想法 要用到adj
= numpy.loadtxt("graph.txt", delimiter=',')
这个公式来插入txt
要用kruskal的方法计算minimum spanning tree， 但是那个matrix（或者说edge, wight)不是直接输在python code里面， 而是通过插入一个txt格式的文件，txt文件里面有matrix，例如：
0,30,26,50,40
30,0,24,40,50
26,24,0,24,26
50,40,24,0,30
40,50,26,30,0
这是55格式的
也有可能是66格式， 不同数字。
要求无论插入的txt文本里面有什么样的matrix，python code都可以运行
我希望最后的output像这样
Following are the edges in the constructed MST
2 -- 3 == 4
0 -- 3 == 5
0 -- 1 == 10
Minimum Cost Spanning Tree: 19
可以参考 这个链接 https://www.geeksforgeeks.org/kruskals-minimum-spanning-tree-algorithm-greedy-algo-2/
并且希望output的顶点不是从0开始计， 而是从1开始
像‘（0，2）’ 变成 “（1，3）”
求解完整的算法
已完成，需要在代码的文件夹下新建一个graph.txt，
内容如下
# Python program for Kruskal's algorithm to find
# Minimum Spanning Tree of a given connected,
# undirected and weighted graph
# Class to represent a graph
class Graph:
def __init__(self, vertices):
self.V = vertices # No. of vertices
self.graph = [] # default dictionary
# to store graph
# function to add an edge to graph
def addEdge(self, u, v, w):
self.graph.append([u, v, w])
# A utility function to find set of an element i
# (uses path compression technique)
def find(self, parent, i):
if parent[i] == i:
return i
return self.find(parent, parent[i])
# A function that does union of two sets of x and y
# (uses union by rank)
def union(self, parent, rank, x, y):
xroot = self.find(parent, x)
yroot = self.find(parent, y)
# Attach smaller rank tree under root of
# high rank tree (Union by Rank)
if rank[xroot] < rank[yroot]:
parent[xroot] = yroot
elif rank[xroot] > rank[yroot]:
parent[yroot] = xroot
# If ranks are same, then make one as root
# and increment its rank by one
else:
parent[yroot] = xroot
rank[xroot] += 1
# The main function to construct MST using Kruskal's
# algorithm
def KruskalMST(self):
result = [] # This will store the resultant MST
# An index variable, used for sorted edges
i = 0
# An index variable, used for result[]
e = 0
# Step 1: Sort all the edges in
# non-decreasing order of their
# weight. If we are not allowed to change the
# given graph, we can create a copy of graph
self.graph = sorted(self.graph,
key=lambda item: item[2])
parent = []
rank = []
# Create V subsets with single elements
for node in range(self.V):
parent.append(node)
rank.append(0)
# Number of edges to be taken is equal to V-1
while e < self.V - 1:
# Step 2: Pick the smallest edge and increment
# the index for next iteration
u, v, w = self.graph[i]
i = i + 1
x = self.find(parent, u)
y = self.find(parent, v)
# If including this edge does't
# cause cycle, include it in result
# and increment the indexof result
# for next edge
if x != y:
e = e + 1
result.append([u, v, w])
self.union(parent, rank, x, y)
# Else discard the edge
minimumCost = 0
print("Edges in the constructed MST")
for u, v, weight in result:
minimumCost += weight
print("%d -- %d == %d" % (u+1, v+1, weight))
print("Minimum Spanning Tree", minimumCost)
# Driver code
data = []
with open('graph.txt', mode='r', encoding='utf-8') as fp:
data = fp.readlines()
for i, item in enumerate(data):
data[i] = item.split(',')
n = len(data)
g = Graph(n)
for i in range(n):
for j in range(n):
g.addEdge(i, j, int(data[i][j]))
# Function call
g.KruskalMST()
# This code is contributed by Neelam Yadav
代码实现如下，最后输出边列表
import numpy as np
matrix= np.loadtxt("graph.txt", delimiter=',')
len = matrix.shape[0]
fathers = np.array(list(range(len)))
edgesv = np.where(matrix>0)
edgesv = list(zip(edgesv[0],edgesv[1]))
edges = list(zip(edgesv,matrix[matrix>0]))
edges.sort(key=lambda x: x[1])
selectE = []
for (u,v),w in edges:
if fathers[u]!=fathers[v]:
if fathers[u]>fathers[v]:
u, v = v,u
fathers[fathers==fathers[v]] = fathers[u]
selectE.append((u,v,w))
print ("Edges in the constructed MST")
minimumCost = 0
for u, v, weight in selectE:
minimumCost += weight
print("%d -- %d == %d" % (u+1, v+1, weight))
print("Minimum Spanning Tree" , minimumCost)
你再讲具体一些问题
参考：https://blog.csdn.net/qq_35175413/article/details/98110336
这个重点是你先得编一个读取txt文件的程序，txt里边文件数据读取出来了，这些数据读出来了，你想怎么插都可以，再用kruskal的方法计算minimum spanning tree就可以了，txt读取的程序可以参考https://blog.csdn.net/ggj0727/article/details/120605935
class Solution:
# @param {Connection[]} connections given a list of connections
# include two cities and cost
# @return {Connection[]} a list of connections from results
def lowestCost(self, connections):
# Write your code here
connections.sort(key=lambda c:(c.cost,c.city1,c.city2))
ans = []
group = {}
def find(city):
while group.get(city) != city:
city = group.get(city)
return city
cityset = set()
for con in connections:
cityset.add(con.city1)
cityset.add(con.city2)
for con in connections:
c1 = con.city1
c2 = con.city2
if c1 not in group.keys():
group[c1] = c1
if c2 not in group.keys():
group[c2] = c2
g1 = find(c1)
g2 = find(c2)
group[c1] = g1
group[c2] = g2
if g1 != g2:
ans.append(con)
group[g2] = g1
if len(cityset) - 1 == len(ans):
return ans
return []
创建一个test.txt格式的文件，txt文件里面有matrix，例如：
0,30,26,50,40
30,0,24,40,50
26,24,0,24,26
50,40,24,0,30
40,50,26,30,0
在python用minimum spanning tree 的算法来运行matrix， 并得出结果
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import minimum_spanning_tree
with open('test.txt', 'r') as f:
l = [[int(num) for num in line.split(',')] for line in f if line.strip() != "" ]
X = csr_matrix(l)
Tcsr = minimum_spanning_tree(X)
Tcsr.toarray().astype(int)
PS：问答VIP年卡 【限时加赠：IT技术图书免费领】，了解详情>>> https://vip.csdn.net/askvip?utm_source=1146287632