1

我有一个数据结构，它看起来像一个相当孤立的无向“子图”图，并且希望获得那些具有少于 N 条边的子图，在这种情况下，只有那些具有一条或两条边的子图。我在这里有点迷路，不知道该怎么做。实际上，我存储数据的方式甚至可能不是解决这个问题的最佳方法。

例如，对于graph下面我想检索节点和A-B，但不是因为它有超过 2 条边。H-JK-MC-G

graph = {  # using sets
    # single (A-B)
    'A': {'B'},
    'B': {'A'},
    # complex (C-G)
    'C': {'D'},
    'D': {'C', 'E'},
    'E': {'D', 'F'},
    'F': {'G', 'E'},
    'G': {'F'},
    # digraph1 (H-J)
    'H': {'J', 'I'},
    'I': {'H'},
    'J': {'H'},
    # digraph2 (K-M)
    'K': {'L'},
    'L': {'K', 'M'},
    'M': {'L'},
}

关于如何在 Python 中解决这个问题的任何想法或建议？

4

3 回答 3

1

您可以对每个节点进行简单的广度优先搜索，以识别您的子组件。您还可以在执行此操作时计算边数并将其与子组件一起返回。例如，给定您的图形结构，您可以执行以下操作：

from collections import deque

def bfs(graph, start_node):
    searched = set([start_node])
    edge_count = 0
    queue = deque(start_node)
    while(len(queue)):
        current = queue.popleft()
        for node in graph[current]:
            edge_count += 1                
            if node not in searched:
                searched.add(node)
                queue.append(node)
    return (searched, edge_count/2)

def findSubGraphs(graph):
    subgraphs = []
    found = set()
    for node in graph:
        if node not in found:
            (subgraph, edge_count) = bfs(graph, node)
            found.update(subgraph)
            subgraphs.append((subgraph, edge_count))
    return subgraphs

findSubGraphs(graph)

这应该返回一个包含子图节点和边数的数据结构。例如：

[({'A', 'B'}, 1.0),
 ({'C', 'D', 'E', 'F', 'G'}, 4.0),
 ({'H', 'I', 'J'}, 2.0),
 ({'K', 'L', 'M'}, 2.0)]
于 2018-03-27T22:40:02.060 回答
1

我不确定您需要多少通用解决方案，所以这里有一个非常具体的解决方案，使用networkx package。

首先初始化你的图：

import networkx as nx
edges = [('a','b'),('c','d'),('d','e'),('e','f'),('f','g'),('h','j'),('i','h'),('k','l'),('l','m')]
gr = nx.Graph(edges)

然后找到所有连接的组件并遍历它们：

connected = nx.algorithms.connected_components(gr)
for comp in connected:
    if len(comp) <= 3:
        print(comp)

瞧！（显然你不必打印它们，你可以对它们做任何你想做的事情）。

于 2018-03-27T22:19:15.350 回答
1

您遵循关闭图形节点的标准算法：

构建您方便的新结构。 

Pick a starting node however you like; you'll eventually get to all of them.  Put it on the "not visited" list.

While the "not visited" list is not empty:
    Remove the top node from the list.
    Add it to the structure.
    Iterate through its edges.
        If the node on the other end isn't already in the structure,
            add the node and edge to the structure.

现在，只需检查结构中有多少边。如果它小于 3，则您有一个想要的图表。

从字典中删除这些节点。继续新的起点，直到您的字典为空。您现在已经识别了所有小图。

于 2018-03-27T21:43:43.150 回答