少于 n 条边的无向图

Question

我有一个数据结构，它看起来像一个相当孤立的无向图 "subgraphs" 并且想要获得那些少于 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

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

构建您方便的新结构。

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，你就有了想要的图表。

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

Answer 2

我不确定您需要多少通用解决方案，所以这是一个非常具体的解决方案，使用 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)

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

Answer 3

您可以对每个节点进行简单的 breadth-first 搜索，这将识别您的子组件。您还可以在执行此操作时计算边数，并 return 使用子组件计算边数。例如，给定您的图形结构，您可以执行以下操作：

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)

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

[({'A', 'B'}, 1.0),
 ({'C', 'D', 'E', 'F', 'G'}, 4.0),
 ({'H', 'I', 'J'}, 2.0),
 ({'K', 'L', 'M'}, 2.0)]

少于 n 条边的无向图

Undirected graphs with less than n edges

python

python-3.x

undirected-graph