如何在Python中创建节点仅单向连接的随机DAG

核心思路 #

要彻底避免双向边，最可靠的方式是先给所有节点分配拓扑序，只允许从拓扑序靠前的节点指向靠后的节点。这样任何两个节点之间最多只有一条单向边，不可能出现A→B同时B→A的情况，且天然满足DAG的无环要求。

基础实现（Python） #

import random

def generate_dag(num_nodes, edge_probability):
    # 用0到num_nodes-1的序号直接作为拓扑序
    nodes = list(range(num_nodes))
    adjacency_list = {node: [] for node in nodes}
    
    # 仅遍历i<j的节点对，按概率添加i→j的边
    for i in range(num_nodes):
        for j in range(i + 1, num_nodes):
            if random.random() < edge_probability:
                adjacency_list[i].append(j)
    
    return adjacency_list

# 示例：生成10个节点，边出现概率0.2的DAG
dag = generate_dag(10, 0.2)
for node in dag:
    print(f"{node} -> {dag[node]}")

扩展：带自定义节点标识的DAG #

如果需要非序号的节点名称，可以调整为：

import random
import string

def generate_named_dag(num_nodes, edge_probability):
    # 生成随机大写字母组合作为节点名
    nodes = [''.join(random.choices(string.ascii_uppercase, k=2)) for _ in range(num_nodes)]
    node_order = {node: idx for idx, node in enumerate(nodes)}
    adjacency_list = {node: [] for node in nodes}
    
    # 严格遵循拓扑序添加边
    for i in range(num_nodes):
        for j in range(i + 1, num_nodes):
            if random.random() < edge_probability:
                adjacency_list[nodes[i]].append(nodes[j])
    
    return adjacency_list

# 示例调用
named_dag = generate_named_dag(8, 0.15)
for node in named_dag:
    print(f"{node} -> {named_dag[node]}")

可选：指定固定边数的生成方式 #

若不想用概率控制边数，可直接指定总边数：

import random
from itertools import combinations

def generate_dag_with_fixed_edges(num_nodes, num_edges):
    nodes = list(range(num_nodes))
    adjacency_list = {node: [] for node in nodes}
    # 生成所有合法的单向边候选（i<j）
    all_valid_edges = list(combinations(nodes, 2))
    # 随机选择指定数量的边（不超过候选总数）
    selected_edges = random.sample(all_valid_edges, min(num_edges, len(all_valid_edges)))
    
    for u, v in selected_edges:
        adjacency_list[u].append(v)
    
    return adjacency_list

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