- iOS/Objective-C 元类和类别
- objective-c - -1001 错误,当 NSURLSession 通过 httpproxy 和/etc/hosts
- java - 使用网络类获取 url 地址
- ios - 推送通知中不播放声音
我一直在尝试为类解决一个问题。问题是:
Given an undirected graph G, find the minimum spanning tree within G.
为了通过这个问题,我的函数必须接受并返回一个邻接表。但是,我不确定如何将输入和输出表示为邻接表。
from collections import defaultdict
class Graph:
def __init__(self,vertices):
self.V= vertices
self.graph = []
def Edge(self,u,v,w):
self.graph.append([u,v,w])
# A utility function to find set of an element i
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
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
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 rank by one
else :
parent[yroot] = xroot
rank[xroot] += 1
# The main function to build the MST
def Question3(G):
MST =[] # This will store the MST
e = 0 # An index variable used for MST[]
i = 0 # An index variable for sorted edges
G.graph = sorted(G.graph,key=lambda item: item[2])
parent = [] ; rank = []
# Create V subsets with single elements
for node in range(G.V):
parent.append(node)
rank.append(0)
# Edges to be taken is equal to V-1
while e < G.V -1 :
# Take smallest edge and increment the index
u,v,w = G.graph[i]
i = i + 1
x = G.find(parent, u)
y = G.find(parent ,v)
# If including this edge does't cause cycle, include it
# in result and increment the index of result for next edge
if x != y:
e = e + 1
MST.append([u,v,w])
G.union(parent, rank, x, y)
# Else discard the edge
print "Minimum Spanning Tree"
for u,v,weight in MST:
print ("%d -- %d == %d" % (u,v,weight))
g = Graph(4)
g.Edge(0, 1, 9)
g.Edge(0, 2, 6)
g.Edge(0, 3, 5)
g.Edge(1, 3, 12)
g.Edge(2, 3, 4)
g.Question3()
print """---End Question 3---
"""
最佳答案
假设您将最小生成树计算为称为 MST 的边列表。现在,MST 包含三元组 (u, v, weight)
。您可以做的是迭代 MST 中的边,并为每个这样的边 (u, v, weight)
将元组 (v, weight)
附加到的邻接列表中u
,并且还在v
的邻接表中附加一个元组(u, weight)
。在伪代码中它可能看起来像这样:
adj = {} # your resulting adjacency lists, one for each vertex in the graph
for u, v, weight in MST:
if u not in adj:
adj[u] = []
adj[u].append((v, weight))
if v not in adj:
adj[v] = []
adj[v].append((u, weight))
关于python - 使用邻接表表示最小生成树,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/43145679/
我在 ma 应用程序中使用 Jqgrid 树 View 模型,我可以看到它显示错误,因为不支持对象或属性我已经包含了 grid.Treeview.js 和其他 Jqgrid 脚本文件。我不知道可能是什
我正在尝试使用图中所示的符号在 matlab 上实现 Freeman Chain Code [4 adjacency]: 我的代码为我测试过的多个小矩阵提供了正确的链码。但是,当我在我的实际图像文件上
我有一张表,其中包含世界上所有地理位置及其关系的位置。 这是一个显示层次结构的示例。你会看到数据实际上存储为所有三个 枚举路径 邻接表 嵌套集 数据显然也不会改变。下面是英格兰布莱顿位置的直系祖先示例
我正在尝试从邻接树模型(id、parent_id)中的 MySQL 数据库中计算/创建或生成 PHP 目录。到目前为止,这是我在回显输出时所取得的成就。 1. Category 1 1 Subc
我知道 std::vector在内部连续存储它的数据(除非它是 std::vector )都在旧的 C++03 中标准和新的C++11 . 处理此问题并引用标准的好 stackoverflow 问题:
Development language and DB: PHP/MySQL 我有一张 geo_places 表,其中包含大约 800 万个地理位置。 这些地方都是分层次的,我用 parent_id
过去几个小时我一直在尝试在网上找到这个问题的解决方案。我找到了很多关于如何从嵌套集合转换为邻接的例子......但很少有相反的例子。我发现的示例要么不起作用,要么使用 MySQL 过程。不幸的是,我不
我是一名优秀的程序员,十分优秀!