有向图（Directed Graph）和有向无环图（Directed Acyclic Graph，DAG）代码实践

有向图（Directed Graph）和有向无环图（Directed Acyclic Graph，DAG）代码实践

flyfish

有向图（Directed Graph）是图论中一种重要的数据结构，它由顶点（Vertices）和有向边（Directed Edges）组成

基本组成元素

• 顶点（Vertices）：也称为节点（Nodes），是有向图的基本组成部分，可以用来表示各种对象。比如在一个表示城市交通的有向图中，顶点可以代表不同的城市；在一个任务调度的有向图里，顶点可以表示不同的任务。
• 有向边（Directed Edges）：有向边是连接两个顶点的线段，并且带有方向。它用有序对 (u, v) 来表示，其中 u 是边的起点（尾顶点），v 是边的终点（头顶点），意味着从顶点 u 到顶点 v 存在一个特定的关系。例如在表示网页链接的有向图中，有向边可以表示从一个网页到另一个网页的链接指向。

有向图的特点

• 方向性：这是有向图最显著的特点。从顶点 u 到顶点 v 的有向边 (u, v) 与从顶点 v 到顶点 u 的有向边 (v, u) 是不同的，它们代表不同的连接关系。比如在一个表示比赛胜负的有向图中，(A, B) 表示 A 战胜了 B，而 (B, A) 则表示 B 战胜了 A。
• 允许存在环和多重边：
  • 环（Loop）：有向图中允许存在从一个顶点出发又回到自身的边，即 (u, u) 这样的边，这被称为环。例如在一个表示程序中函数调用的有向图里，某个函数内部调用自身，就可以用一个环来表示。
  • 多重边（Multiple Edges）：在有向图中，可能存在从顶点 u 到顶点 v 的多条有向边，它们可能代表不同类型或者不同权重的关系。

概念

• 入度（In - degree）和出度（Out - degree）：
  • 入度：对于一个顶点 v，入度是指以 v 为终点的有向边的数量，它反映了有多少其他顶点指向该顶点。比如在一个社交网络的有向图中，一个人的入度可以表示有多少人关注他。
  • 出度：出度是指以 v 为起点的有向边的数量，它体现了该顶点可以指向多少其他顶点。在上述社交网络例子中，一个人的出度表示他关注了多少其他人。
• 路径（Path）：从一个顶点 u 到另一个顶点 v 的路径是一个顶点序列 u = v0, v1, v2,..., vk = v，其中 (vi, vi + 1) 是有向图中的一条有向边，i = 0, 1,..., k - 1。路径的长度是路径中边的数量。例如在一个导航应用的有向图里，从一个地点到另一个地点的行驶路线就可以看作是一条路径。
  

import networkx as nx
import matplotlib.pyplot as plt# 创建一个有向图
G = nx.DiGraph()# 添加节点
node_list = ["红富士苹果", "蛇果", "青苹果", "果园", "水果店"]
G.add_nodes_from(node_list)# 添加边，表示关系
G.add_edge("果园", "红富士苹果", relation="产出")
G.add_edge("果园", "蛇果", relation="产出")
G.add_edge("果园", "青苹果", relation="产出")
G.add_edge("红富士苹果", "水果店", relation="运输售卖")
G.add_edge("蛇果", "水果店", relation="运输售卖")
G.add_edge("青苹果", "水果店", relation="运输售卖")# 设置图片清晰度
plt.rcParams['figure.dpi'] = 300# 设置中文字体
plt.rcParams['font.sans-serif'] = ['SimHei']
plt.rcParams['axes.unicode_minus'] = False
plt.figure(figsize=(10, 10))
# 为不同类型的节点分配颜色
node_colors = []
for node in node_list:if "苹果" in node:node_colors.append('lightcoral')elif "果园" in node:node_colors.append('lightgreen')else:node_colors.append('lightskyblue')# 计算每个节点的入度和出度
in_degrees = dict(G.in_degree())
out_degrees = dict(G.out_degree())# 绘制图形，增加节点间距
pos = nx.spring_layout(G, k=0.8, iterations=100)
nx.draw_networkx_nodes(G, pos, node_size=2000, node_color=node_colors, edgecolors='black', linewidths=1)
nx.draw_networkx_edges(G, pos, arrowstyle='-|>', arrowsize=25, edge_color='black', connectionstyle="arc3,rad=0.1", node_size=2000)# 绘制节点标签，同时显示入度和出度
node_labels = {}
for node in node_list:node_labels[node] = f"{node}\n入度: {in_degrees[node]}\n出度: {out_degrees[node]}"
nx.draw_networkx_labels(G, pos, labels=node_labels, font_size=10)# 添加边的标签
edge_labels = nx.get_edge_attributes(G,'relation')
nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels)# 添加标题
plt.title('苹果相关关系有向图')
plt.axis('off')# 保存为 JPG 图像
plt.savefig('苹果相关关系有向图.jpg')
plt.close()

有向无环图（Directed Acyclic Graph，DAG）

有向无环图是一种有向图，并且图中不存在环。所谓环，指的是从某个节点出发，沿着有向边又能回到该节点的路径。

苹果例子的分析

在苹果例子的代码里：

# 创建一个有向图
G = nx.DiGraph()# 添加节点
node_list = ["红富士苹果", "蛇果", "青苹果", "果园", "水果店"]
G.add_nodes_from(node_list)# 添加边，表示关系
G.add_edge("果园", "红富士苹果", relation="产出")
G.add_edge("果园", "蛇果", relation="产出")
G.add_edge("果园", "青苹果", relation="产出")
G.add_edge("红富士苹果", "水果店", relation="运输售卖")
G.add_edge("蛇果", "水果店", relation="运输售卖")
G.add_edge("青苹果", "水果店", relation="运输售卖")

添加的边所代表的关系是明确的单向流程。果园产出不同种类的苹果，然后这些苹果被运输到水果店售卖。从任何一个节点出发，都不存在沿着有向边能回到自身的情况。比如从 “果园” 节点出发，只能沿着 “产出” 边到不同苹果节点，再从苹果节点沿着 “运输售卖” 边到 “水果店” 节点，无法再回到之前经过的节点，所以不存在环，是有向无环图。

解释

1. 导入库

import networkx as nx
import matplotlib.pyplot as plt

这里导入了两个关键的库。networkx（简写成nx）库用于创建、操作和分析图结构，比如构建有向图、添加节点和边等操作。matplotlib.pyplot（简写成plt）库是一个强大的绘图工具，用于将networkx创建的图进行可视化展示。

2. 创建有向图

# 创建一个有向图
G = nx.DiGraph()

使用nx.DiGraph()函数创建了一个空的有向图对象G。有向图与无向图不同，它的边是有方向的，从一个节点指向另一个节点，这在表示具有特定流向或关系的数据时非常有用。

3. 添加节点

# 添加节点
node_list = ["红富士苹果", "蛇果", "青苹果", "果园", "水果店"]
G.add_nodes_from(node_list)

首先定义了一个包含节点名称的列表node_list，这里面的元素代表了不同的实体，如不同种类的苹果、果园和水果店。然后通过add_nodes_from方法将这些节点添加到之前创建的有向图G中。

4. 添加边并指定关系

# 添加边，表示关系
G.add_edge("果园", "红富士苹果", relation="产出")
G.add_edge("果园", "蛇果", relation="产出")
G.add_edge("果园", "青苹果", relation="产出")
G.add_edge("红富士苹果", "水果店", relation="运输售卖")
G.add_edge("蛇果", "水果店", relation="运输售卖")
G.add_edge("青苹果", "水果店", relation="运输售卖")

使用add_edge方法为有向图添加边。每一条边连接两个节点，并且通过relation参数赋予了边一个描述性的关系属性。例如，从 “果园” 到 “红富士苹果” 的边，其关系被标记为 “产出”，意味着果园产出红富士苹果；从苹果节点到 “水果店” 的边，关系标记为 “运输售卖”，表示苹果被运输到水果店进行售卖。

5. 设置图片清晰度和中文字体

# 设置图片清晰度
plt.rcParams['figure.dpi'] = 300# 设置中文字体
plt.rcParams['font.sans-serif'] = ['SimHei']
plt.rcParams['axes.unicode_minus'] = False
plt.figure(figsize=(10, 10))

• plt.rcParams['figure.dpi'] = 300：rcParams是matplotlib的全局配置参数，figure.dpi设置生成图片的分辨率为每英寸 300 点，数值越高图片越清晰。
• plt.rcParams['font.sans-serif'] = ['SimHei']：设置用于显示中文的字体为黑体（SimHei），这样在绘制图形时涉及到的中文内容能够正确显示。
• plt.rcParams['axes.unicode_minus'] = False：用于修正负号显示的问题，防止在显示负号时出现异常。
• plt.figure(figsize=(10, 10))：创建一个图形窗口，设置其大小为宽和高均为 10 英寸，这决定了最终绘制的图在窗口中的尺寸大小。

6. 为不同类型的节点分配颜色

# 为不同类型的节点分配颜色
node_colors = []
for node in node_list:if "苹果" in node:node_colors.append('lightcoral')elif "果园" in node:node_colors.append('lightgreen')

7. 英寸与厘米的转换

在长度单位换算中，1 英寸等于 2.54 厘米。所以 plt.figure(figsize=(10, 10)) 中设置的宽和高 10 英寸，换算为厘米就是 10 × 2.54 = 25.4 厘米，即创建的图形窗口宽和高均为 25.4 厘米。

8. 代码中入度和出度的计算方式

在代码中，通过以下两行来计算每个节点的入度和出度：

in_degrees = dict(G.in_degree())
out_degrees = dict(G.out_degree())

networkx 库的 DiGraph 类（有向图类）提供了 in_degree 和 out_degree 方法来分别计算节点的入度和出度。

• G.in_degree()：该方法返回一个可迭代对象，其中每个元素是一个元组，元组的第一个元素是节点，第二个元素是该节点的入度。dict(G.in_degree()) 将这个可迭代对象转换为字典，节点作为键，入度作为值，方便后续通过节点名称来获取其入度。例如，若想获取某个节点 node_name 的入度，可以使用 in_degrees[node_name]。
• G.out_degree()：原理与 in_degree 方法类似，它返回节点及其对应的出度，通过 dict(G.out_degree()) 转换为字典后，就可以通过节点名称获取其出度，如 out_degrees[node_name]。

9. 布局相关参数

• k（弹簧布局参数）：在 nx.spring_layout(G, k=0.8, iterations=100) 中，k 控制节点间的理想距离。如果图形节点分布过于紧凑，可以适当增大 k 值，比如增加到 1.0 或更高，让节点间距变大；若节点分布过于松散，则可减小 k 值，如 0.6 等。一般需要根据节点数量和图的复杂程度多次尝试，找到合适的间距效果。例如，节点数量较多时，可能需要较小的 k 值来避免图形过大。
• iterations（迭代次数）：该参数影响布局的稳定性和美观度。增加 iterations 通常会使节点布局更合理，但也会增加计算时间。对于简单的图，迭代次数可以适当减少，如 50 次；对于复杂的图，可能需要增加到 150 次甚至更多，直到布局看起来稳定且美观。