我有一个基本上可以被视为图表的问题.我正在考虑使用JGraphT来实现它,而不是自己动手.使用JGraphT从图形中获取最小生成树的最佳方法是什么？
我正在编写一个程序,我需要对作业进行分组,以最大限度地减少CNC打孔的工具更改.我刚开始的时候问了一个关于它的问题,但是当我编写程序时,方法已经改变了.
我有一份工作清单:
jobs = ['5618', '5612', '5613', '5897', '5589', '5474',
'5472', '5470', '5471', '9040']
我的程序已经将这些分类为可以一起完成的有效"组"工作:
['5471', '9040']
['5618', '5612', '5613', '5472']
['5471', '5589', '5897']
['5618', '5612', '5471', '5613']
['5471', '5474']
['5471', '5470', '5589']
现在我需要选择意味着完成所有工作的最小组数.猜测它会是这个组合:
['5618', '5612', '5613', '5472']
['5471', '5589', '5897']
['5470', '5589'] #this is the last group in the above lists but with 5471
#removed because it's already been done
[9040] #same as above except the first group with 5471 already been done.
我在逻辑上考虑这样做的方法是找到最长的有效组,假设是第一组,从剩余的作业中删除该组中的作业.重复.但是,当有两个具有相同长度的组时,这不起作用.也许根据工作在其他群体或其他事物中的次数加权函数？我不知道.想法？蛮力吗？哈哈
有没有办法打印MST给出的输出的预先遍历(使用Kruskal或Prim的算法).我有一个混乱,因为输出可能总是或不是二叉树.那么,这里的预订遍历是如何实现的呢？普通的DFS可以完成任务吗？
假设我们找到了一棵最小的生成树.现在,我们只需要在MST中从A到Z的路径.我们怎样才能在O(n ^ 2)时间内做到这一点？
我们从根A开始.然后我们查看Ax(其中x是任何顶点)形式的树中的所有边.
然后,我们发现:AB,AC,AD等......然后对于每一个,我们寻找形式的边缘:Bx,Cx,Dx ......这显然不是O(n ^ 2).
那么在给定MST的情况下找到路径A - > Z的更好/更有效的方法是什么？
谢谢
我能够运行此代码进行一些输入.但在某些情况下,我得到了错误的生成树.例如:如果我在执行程序时给出如下输入:
输入no.of vertices:5输入no.of edges:8
Enter the vertices and the weight of edge 1:
1
3
10
Enter the vertices and the weight of edge 2:
1
4
100
Enter the vertices and the weight of edge 3:
3
5
64
Enter the vertices and the weight of edge 4:
1
2
13
Enter the vertices and the weight of edge 5:
3
2
20
Enter the vertices and the weight of edge 6:
2
5
5
Enter the vertices and …最小乘积生成树与最小和生成树不同吗？请解释一下（如果可能的话，举例说明）。我的意思是，添加到最小值的边应该（？）也具有最小乘积。
你们中有人知道使用生成树数据结构的任何实际应用程序吗？
给定一个像这样的简单无向网格网络：
import networkx as nx
from pylab import *
import matplotlib.pyplot as plt
%pylab inline
ncols=3
N=3
G=nx.grid_2d_graph(N,N)
labels = dict( ((i,j), i + (N-1-j) * N ) for i, j in G.nodes() )
nx.relabel_nodes(G,labels,False)
inds=labels.keys()
vals=labels.values()
inds=[(N-j-1,N-i-1) for i,j in inds]
pos2=dict(zip(vals,inds))
nx.draw_networkx(G, pos=pos2, with_labels=True, node_size = 200, node_color='orange',font_size=10)
plt.axis('off')
plt.title('grid')
plt.show()
考虑到每条边都有与其长度相对应的权重：
#Weights
from math import sqrt
weights = dict()
for source, target in G.edges():
x1, y1 = pos2[source]
x2, y2 = pos2[target]
weights[(source, target)] = round((math.sqrt((x2-x1)**2 + …python minimum-spanning-tree spanning-tree networkx weighted-graph
以下是我的图论与算法课程中的一个例子：
让A为带权无向图（不同权重）的边的最小子集G，这样，如果我们A从中删除G，G则变得断开连接。中最亮的边A必须位于任何 MST 中。
为什么这是一个正确的事实？我无法理解。
algorithm graph shortest-path minimum-spanning-tree data-structures
我在C(www.bubblellicious.es/prim.tar.gz)中实现了Prim的算法,但我只是想知道如何将其转换为Kruskal的算法.
看起来它们非常相似,但我无法想象如何将旧代码修改为新代码.如果你给出一些建议或东西,这将是美味的.我知道这很简单,但我仍然是C编程中的n00b ...
c algorithm minimum-spanning-tree prims-algorithm kruskals-algorithm
假设我们给出了给定图G的最小生成树T(具有n个顶点和m个边)以及我们将添加到G的权重w的新边e =(u,v).
I)检查T是否仍然是MST.II)如果没有,给出一个有效的算法来找到图G + e的最小生成树.