python - 边数少于 n 的无向图

Question

我有一个数据结构，看起来像一个由相当孤立的无向“子图”组成的图，并且希望获得那些具有少于 N 个边的子图，在本例中只有那些具有一个或两个边的子图。我在这里有点迷失，不知道如何应对。实际上，我存储数据的方式可能不是解决这个问题的最佳方法。

举个例子，对于下面的graph，我想检索节点A-B、H-J和K-M ，但不是 C-G 因为它有超过 2 条边。

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 中解决这个问题有什么想法或建议吗？

Answer 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)]