如何在Python中生成多种类型的连通无向图（含大尺度图）？

Got it, let's tackle this problem step by step. You want to generate a variety of connected undirected graphs for algorithm benchmarking, and the adjacency matrix approach isn't scaling for large graphs—totally makes sense, since adjacency matrices take O(n²) space which gets unwieldy fast.

NetworkX has a suite of efficient built-in generators that use adjacency lists (O(n+m) space, way better for large/sparse graphs) instead of matrices. Below are implementations for all the graph types you need, plus tips for scaling and benchmarking:

1. Complete Graph (Extreme Dense) #

Every node connects to every other node—perfect for testing algorithms on worst-case dense scenarios. NetworkX’s complete_graph handles large nodes efficiently as long as you have enough memory.

import networkx as nx

# Generate a complete graph with 1000 nodes
complete_graph = nx.complete_graph(1000)
# Verify connectivity
assert nx.is_connected(complete_graph)

2. Acyclic Graph (Tree, Extreme Sparse) #

Connected acyclic graphs are trees, with exactly n-1 edges. You can generate random trees or structured ones like path/star trees:

# Random tree with 10,000 nodes (scales easily)
random_tree = nx.random_tree(n=10000, seed=42)
# Linear path tree
path_tree = nx.path_graph(5000)
# Star-shaped tree (one central node connected to all others)
star_tree = nx.star_graph(2000)

# Confirm it's a tree (acyclic + connected)
assert nx.is_tree(random_tree)

3. Sparse Graph #

Sparse graphs have far fewer edges than complete graphs. Use the Erdős–Rényi model (gnp_random_graph) with a low edge probability, or generate small-world sparse graphs:

# 10,000-node sparse graph (average 2 edges per node)
sparse_graph = nx.gnp_random_graph(n=10000, p=0.0004, seed=42)
# Ensure connectivity (grab the largest connected component if needed)
if not nx.is_connected(sparse_graph):
    largest_cc = max(nx.connected_components(sparse_graph), key=len)
    sparse_graph = sparse_graph.subgraph(largest_cc).copy()

# Small-world sparse graph (balances local clustering and short paths)
small_world_sparse = nx.connected_watts_strogatz_graph(n=5000, k=4, p=0.1, seed=42)

4. Dense Graph #

Dense graphs have edges close to the complete graph count. Again use gnp_random_graph with a high edge probability:

# 500-node dense graph (60% edge existence chance)
dense_graph = nx.gnp_random_graph(n=500, p=0.6, seed=42)
# Ensure connectivity
if not nx.is_connected(dense_graph):
    largest_cc = max(nx.connected_components(dense_graph), key=len)
    dense_graph = dense_graph.subgraph(largest_cc).copy()

5. Hamiltonian Graph #

A Hamiltonian graph has a path that visits every node exactly once and returns to the start. We can construct one by first making a Hamiltonian cycle, then adding extra edges:

def generate_hamiltonian_graph(n, extra_edges=0, seed=42):
    # Start with a path graph, then connect ends to form a Hamiltonian cycle
    g = nx.path_graph(n)
    g.add_edge(0, n-1)
    # Add random extra edges if needed
    if extra_edges > 0:
        import random
        random.seed(seed)
        possible_edges = [(u, v) for u in range(n) for v in range(u+1, n) if not g.has_edge(u, v)]
        edges_to_add = random.sample(possible_edges, min(extra_edges, len(possible_edges)))
        g.add_edges_from(edges_to_add)
    return g

# 1000-node Hamiltonian graph with 500 extra edges
hamiltonian_graph = generate_hamiltonian_graph(n=1000, extra_edges=500, seed=42)
assert nx.is_connected(hamiltonian_graph)

• Fixed seeds: Use the seed parameter in generators to ensure reproducible graphs—critical for fair algorithm comparisons.
• Batch generation: Automate graph creation with a helper function to avoid repetitive code:

  def generate_test_graphs():
      graphs = []
      graphs.append(("complete_100", nx.complete_graph(100)))
      graphs.append(("random_tree_1000", nx.random_tree(1000)))
      graphs.append(("sparse_10000", nx.gnp_random_graph(10000, 0.0004)))
      graphs.append(("dense_500", nx.gnp_random_graph(500, 0.6)))
      graphs.append(("hamiltonian_1000", generate_hamiltonian_graph(1000, 500)))
      
      # Ensure all graphs are connected
      for idx, (name, g) in enumerate(graphs):
          if not nx.is_connected(g):
              largest_cc = max(nx.connected_components(g), key=len)
              graphs[idx] = (name, g.subgraph(largest_cc).copy())
      return graphs
  

• Super-large graphs: For 100k+ nodes, consider saving graphs as edge lists with nx.write_edgelist() to avoid loading everything into memory at once.

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