如何在NetworkX中判断一个图是否为另一个图的子图？

你需要实现的是有向图的子图匹配逻辑，分两种常见场景可以选择对应方案，不需要自己实现字符串匹配这类不稳定的逻辑，NetworkX本身提供了成熟的实现。

场景1：节点标签严格匹配（和示例场景一致） #

如果要求小图的节点名必须和大图完全对应（比如小图里的A节点只能匹配大图里的A节点），不需要做跨标签的结构匹配，直接用节点、边的存在性判断即可，性能极高，适合小规模图场景。
判断逻辑：

• 校验小图的所有节点都存在于大图中
• 校验小图的所有有向边（含方向）都存在于大图中

场景2：通用子图同构匹配（不要求节点标签一致） #

如果只需要结构匹配，小图节点可以重映射到大图的任意节点（比如小图里X->Y的结构可以匹配大图里A->B的边），可以直接使用NetworkX内置的DiGraphMatcher实现，支持自定义节点、边属性匹配规则，是官方实现的标准子图同构算法。

示例对应图示 #

待检测主图A #

符合要求的子图B #

图B是图A的子图，检测应返回True

不符合要求的非子图C #

图C不是图A的子图，检测应返回False

完整可运行代码 #

原示例代码的导入语句有小问题，import networkx后需要加别名nx才能直接调用nx.xxx接口，修正后的完整实现如下：

import networkx as nx
from networkx.algorithms.isomorphism import DiGraphMatcher

# 严格标签匹配：节点名必须完全对应
def is_subgraph_strict(big_g: nx.DiGraph, small_g: nx.DiGraph) -> bool:
    # 节点校验
    if not set(small_g.nodes).issubset(set(big_g.nodes)):
        return False
    # 有向边校验
    return all(big_g.has_edge(u, v) for u, v in small_g.edges)

# 通用子图同构：支持结构匹配，不要求节点名一致
def is_subgraph_isomorphic(big_g: nx.DiGraph, small_g: nx.DiGraph) -> bool:
    matcher = DiGraphMatcher(big_g, small_g)
    return matcher.subgraph_is_isomorphic()

# 构建测试图
A = nx.DiGraph()
A.add_edges_from([('A','B'),('B','C'),('C','A')])

B = nx.DiGraph()
B.add_edges_from([('A','B')])

C = nx.DiGraph()
C.add_edges_from([('A','B'),('A','C')])

# 测试输出
print(is_subgraph_strict(A, B))  # 输出 True
print(is_subgraph_strict(A, C))  # 输出 False
print(is_subgraph_isomorphic(A, B))  # 输出 True
print(is_subgraph_isomorphic(A, C))  # 输出 False

补充说明 #

字符串序列匹配方案仅能匹配简单路径类的子结构，遇到带环、多分支的图结构很容易出现误判、漏判，不建议使用。如果你的图规模较大（节点数过百），子图同构属于NP难问题，可以根据业务场景提前做节点度剪枝优化，减少不必要的匹配计算。

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