有效的算法在有向图的另一子集中最连接到节点的子集中的节点
我需要一种有效的方法来在最连接到另一个节点子集的节点子集中找到节点。
当前，我在第一个子集S1中的每个节点上迭代，如果在S2中的每个节点上完成了子集S2中的节点，则会增加计数器。因此，时间复杂性是S1XS2X（是时候找到候选者之间的路径了）。我当前的算法是使用NetworkX实现的，该图是有向图。
有人知道可以解决我的问题的算法吗？
I need an efficient way to find the node in a subset of nodes that is the most connected to another subset of nodes.
Currently, I iterate over each node in the first subset S1 and increment a counter if there is a path to a node in subset S2, done over each node in S2. So time complexity is S1xS2x(time to find a path between candidates). My current algorithm is implemented using networkx and the graph is a directed graph.
Does anyone know of an algorithm that can solve my problem?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
如果您的第一个子集已连接（子集中的每个节点之间都有一条路径），则没有答案，所有节点均匀地连接到第二个子集。因为每个节点都均等连接。
如果您的子集未连接，则第一个子集中的“最连接”节点是连接到第二个子集的最大组件的第一个子集中的节点之一。 （一个组件是一组节点，都可以彼此接触）
因此：
If your first subset is connected ( there is a path between every pair of nodes in the subset ) then there is no answer, all nodes are equally connected to the second subset.. If your second subset is connected, then again there is no answer because every node is equally connected, or not.
If your subsets are not connected, then the "most connected" node in the first subset is one of the nodes in the first subset connected to the largest component of the second subset. ( A component is a set of nodes, all reachable from each other )
So: