如何使用Bron–Kerbosch算法迭代器？已构建图但不知代码用法

Hey there! Let me break down how to use this Bron–Kerbosch iterator with your NetworkX graph clearly, including a tiny fix for a bug in the original code.

First, let's clarify what each parameter in the bronk function does—this is key to using it correctly:

• graph: Your pre-built NetworkX graph object (like the nx.Graph() you've already constructed)
• P: The set of nodes that could still be added to the current clique. For your first call, this should be all nodes in your graph
• R: The clique we're currently building. You don't need to pass this initially—leave it as the default empty set
• X: Nodes we've already ruled out for the current clique. Again, leave this as the default empty set for the first call

Important Quick Fix #

The original code has a small issue: when using R.union(node), node is a single element (not a set), which will throw an error because union() expects an iterable. We need to wrap node in a set, so update that line to R.union({node}).

Full Example Walkthrough #

Here's how to put it all together with a sample graph (swap this out for your own existing graph):

import networkx as nx

# Fixed Bron–Kerbosch function
def bronk(graph, P, R=set(), X=set()):
    ''' Implementation of Bron–Kerbosch algorithm for finding all maximal cliques in graph '''
    if not any((P, X)):
        yield R
    for node in P.copy():
        # Fixed: wrap node in a set for valid set union
        for r in bronk(graph, P.intersection(graph.neighbors(node)), R=R.union({node}), X=X.intersection(graph.neighbors(node))):
            yield r
        P.remove(node)
        X.add(node)

# 1. Use your existing graph, or create a sample one like this
my_graph = nx.Graph()
my_graph.add_edges_from([(1,2), (1,3), (2,3), (2,4), (3,4), (4,5)])

# 2. Initialize P with all nodes from your graph
initial_potential_nodes = set(my_graph.nodes())

# 3. Iterate over the generator to get each maximal clique
for idx, clique in enumerate(bronk(my_graph, initial_potential_nodes), 1):
    print(f"Maximal clique #{idx}: {clique}")

What You'll Get #

For the sample graph above, the output will look like this:

Maximal clique #1: {1, 2, 3}
Maximal clique #2: {2, 3, 4}
Maximal clique #3: {4, 5}

Key Notes #

• This is a generator function (uses yield instead of return), so it returns cliques one at a time—perfect for large graphs where storing all cliques in memory would be inefficient
• Always pass a set of your graph's nodes as the initial P parameter; set(my_graph.nodes()) works seamlessly here since NetworkX's nodes() returns an iterable we can convert to a set

内容的提问来源于stack exchange，提问作者Geiv