时间戳

首页 > 解决方案 > 如何找到加权顶点的中心枢纽

python - 如何找到加权顶点的中心枢纽

问题描述

因此，我正在开发一个程序，该程序采用一组顶点并从中生成 Kruskal 生成树。我把它记下来了，但现在我需要获取顶点并找到一个中心集线器，通过它我需要找到所有其他顶点之间的总距离最短的顶点。我正在考虑制作一棵 BFS 树，但我不确定如何实现这些点以及实现它的距离。

from collections import defaultdict
 
# 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, v, weight))
        print("Minimum Spanning Tree" , minimumCost)
 
# Driver code
g = Graph(4)
# so point 0 goes to 1 with a distance of 10
g.addEdge(0, 1, 10)
g.addEdge(0, 2, 6)
g.addEdge(0, 3, 5)
g.addEdge(1, 3, 15)
g.addEdge(2, 3, 4)
 
# Function call
g.KruskalMST()

标签： pythontree

解决方案

如果我理解正确，您有一棵树（从初始图派生的最小生成树），并且需要找到节点，以使其与任何其他节点的最大距离最小化。

这可以分两步完成，两个步骤都与 中的节点数量成线性关系：

  1. 确定 中的最长路径。这可以通过两次遍历（深度或广度优先）来完成：

    选择一个节点并在 中找到离它最远的节点。然后从 in 开始执行第二次遍历，以在 中找到离它最远的节点。路径 (, ) 表示 中的最长路径。另请参见树中最长路径的线性算法

  2. 问题现在简化为在路径 (, ) 上找到“中间”节点。对从 和 开始的路径执行简化的广度优先搜索：因此您有沿 相互遍历的引用，始终将 dist(, ) 和 dist(, ) 保持在最小值。和将相遇的节点是中间节点。离节点 in 最远的节点是 或 。

推荐阅读