在Networkx中以无向图画出一棵树

摘要: 在 Networkx 中以无向图形式画出一棵树

【对数据分析、人工智能、金融科技、风控服务感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：潮汐朝夕
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

在解决图算法的问题时，我们经常希望把图画出来直观地分析。本文我们通过之前解决过的一道题来看一下画图对调试图算法的好处，并给出代码模板。

场景：图算法调试

例如在文章 力扣1766-互质树 中我们在一个无向图形式给出的树上，用树形前缀的方法解决了与质因数有关的问题。题目与算法的细节可以参考那篇文章，这里我们只把题目大意和输入输出简要介绍一下。

给定一个 n 节点的树，树根为 0，每个节点有一个权值。对每个节点 $u$，问距离 $u$ 最近且权值与 $u$ 的权值互质的祖先节点。输入是一个数组表示各个节点的权值，以及用边表形式记录的树。输出为一个数组 result[u] 表示节点 u 的祖先中距离最近且权值互质的节点。接口如下：

class Solution:
    def getCoprimes(self, nums: List[int], edges: List[List[int]]) -> List[int]:

对于 n 比较小的情况，比较好分析。当我们设计算法，并实现完成时，在几个 n 比较小的例子上都没问题。但是提交后，发现有不通过的 Case，如下：

nums = [9,16,30,23,33,35,9,47,39,46,16,38,5,49,21,44,17,1,6,37,49,15,23,46,38,9,27,3,24,1,14,17,12,23,43,38,12,4,8,17,11,18,26,22,49,14,9]
edges = [[17,0],[30,17],[41,30],[10,30],[13,10],[7,13],[6,7],[45,10],[2,10],[14,2],[40,14],[28,40],[29,40],[8,29],[15,29],[26,15],[23,40]
        ,[19,23],[34,19],[18,23],[42,18],[5,42],[32,5],[16,32],[35,14],[25,35],[43,25],[3,43],[36,25],[38,36],[27,38],[24,36],[31,24]
        ,[11,31],[39,24],[12,39],[20,12],[22,12],[21,39],[1,21],[33,1],[37,1],[44,37],[9,44],[46,2],[4,46]
        ]

在这个 Case 上，预期结果和我的代码的输出差异如下：

预期结果：[-1,21,17,43,10,42,7,13,29,44,17,31,39,10,10,29,32,-1,40,23,12,39,12,40,25,35,15,38,40,-1,17,24,5,1,19,14,35,21,25,24,14,17,40,25,37,17,10]
我的输出：[-1,21,17,43,10,42,7,13,29,44,17,31,39,10,10,29,32,0,40,23,12,39,12,40,25,35,15,38,40,40,17,24,5,1,19,14,17,21,25,24,14,17,40,25,37,17,10]

可以看到差异点在于节点 17、节点 29、节点 36 这三个。其中节点 17 的答案应该为 0、节点 29 的答案应该为 40，我的代码输出均为 -1；节点 36 的答案应该为 17、而我的代码输出为 35。其它的节点答案都对。

从代码调试来讲我们要做的是根据这个错误 Case 发现代码中的逻辑漏洞，漏洞原因有很多，对着代码干想的话很难，而对着 Case 来分析就会快速找到可能出错的位置。比如从上面的信息可以猜测，代码中的算法大框架没错，但是中间有一两个细节没有正确处理，使得当图的规模较大时，有少量节点出错。

但问题在于这个 Case 的输入还是不小的，如果一个个手画太费时了，但是输入也不算很多，如果能用可视化的方法画出来，在一个屏幕上呈现还是非常清晰的，此时就体现出 Networkx 画图的好处了。

---

Networkx 画图

在 Python 中，图的可视化最常用的方法是 Networkx 和 Matplotlib 结合。NetworkX 是一个用于创建、操作和研究复杂网络结构的 Python 库。在使用的时候大致可以按以下几步来：

step1, 安装

pip install networkx matplotlib

step2, 创建图

使用NetworkX的DiGraph类来创建一个有向图实例。

import networkx as nx
G = nx.DiGraph()  # 创建有向图

step3, 添加节点和边

G.add_node(1, desc='v1')  # 添加节点，并设置属性
G.add_edge(1, 2, weight=3)  # 添加有向边，并设置权重

step4, 设置节点位置

可以为每个节点设置一个位置。这可以通过多种布局算法来实现，例如 spring_layout：

pos = nx.spring_layout(G)  # 使用弹簧布局算法

step5, 绘制

绘制节点、边和标签。

import matplotlib.pyplot as plt

nx.draw_networkx_nodes(G, pos, node_size=700, node_color='lightblue')  # 绘制节点
nx.draw_networkx_edges(G, pos, edgelist=G.edges(), edge_color='gray')  # 绘制边
nx.draw_networkx_labels(G, pos, font_size=16, font_family='sans-serif')  # 绘制标签
plt.axis('off')  # 关闭坐标轴
plt.show()  # 显示图形

step6, 自定义样式

通过调整参数来自定义节点的样式、边的样式以及整体的布局。例如，可以改变节点大小、颜色，边的宽度、颜色和样式等。

以上代码画出图后如下：

---

代码模板：无向图形式的树

以上步骤只是展示了如何使用 NetworkX 和 Matplotlib 库来创建和可视化一个简单的有向图。通过调整不同的参数和样式，可以实现更加丰富和个性化的可视化效果。

此外，NetworkX 还提供了其他布局算法，如 kamada_kawai_layout、shell_layout 等，以及更多的绘图选项，以满足不同的可视化需求。

这里结合我们的图算法调试的问题，提供一个无向图形式的树比较适用的代码模板，使用 graphviz_layout 布局，这个布局需要额外安装 pydot，按照提示安装即可。

import matplotlib.pyplot as plt
import networkx as nx
from networkx.drawing.nx_pydot import graphviz_layout

G = nx.Graph()

nums = [9,16,30,23,33,35,9,47,39,46,16,38,5,49,21,44,17,1,6,37,49,15,23,46,38,9,27,3,24,1,14,17,12,23,43,38,12,4,8,17,11,18,26,22,49,14,9]
n = len(nums)
for u in range(n):
    G.add_node(u, weight=nums[u])

# 键为顶点编号，值为格式化字符串，包含编号和权重
labels = {node: "{} ({})".format(node, G.nodes[node].get("weight", "N/A")) for node in G.nodes()}

edges = [[17,0],[30,17],[41,30],[10,30],[13,10],[7,13],[6,7],[45,10],[2,10],[14,2],[40,14],[28,40],[29,40],[8,29],[15,29],[26,15],[23,40] \
        ,[19,23],[34,19],[18,23],[42,18],[5,42],[32,5],[16,32],[35,14],[25,35],[43,25],[3,43],[36,25],[38,36],[27,38],[24,36],[31,24]\
        ,[11,31],[39,24],[12,39],[20,12],[22,12],[21,39],[1,21],[33,1],[37,1],[44,37],[9,44],[46,2],[4,46]
        ]
for u, v in edges:
    G.add_edge(u, v)

# 树的布局，需要 pydot
pos = graphviz_layout(G)

nx.draw_networkx_nodes(G, pos, node_size=700, node_color='lightblue')  # 绘制节点
nx.draw_networkx_edges(G, pos, edgelist=G.edges(), edge_color='gray')  # 绘制边
nx.draw_networkx_labels(G, pos, labels=labels, font_size=16, font_family='sans-serif')  # 绘制标签
plt.axis('off')  # 关闭坐标轴
plt.show()  # 显示图形

在代码中，将错误 Case 的输入写进去，也就是代码中的 nums 和 edges，画出图后如下：

这下就可以看得很清晰了，出错误的其中两个顶点 17 和 29 的权值均为 1，很可能是 1 这个顶点需要特殊处理，但是代码中没有正确处理。

另外一个答案不对的顶点 36，问题比较难猜，但是通过可视化图，其祖先链上的各个顶点及其权重显示的非常清晰，对着算法一步一步去推就可以慢慢找出问题。

总结

当调试图算法时，如果 Case 的输入节点数较多，很难手画，同时输入节点数又不是特别大，使得一屏都放不下，一般就是 10 ~ 60 的节点数，可以通过 Networkx 和 Matplotlib 的方式画出图，借助直观来猜测代码中的问题可能在哪里。

---