数据结构编程实践20讲(Python版)—16有向图

往期链接

16 有向图（Directed Graph）

S1 说明

有向图也称为有向网络，是一种由节点（顶点）和有向边（弧）组成的图。每条边有一个方向，从一个节点指向另一个节点。与无向图不同，有向图的边是有方向的，表示一种从一个节点到另一个节点的关系。

特征

• 节点和边： 有向图由一组节点和一组有向边组成。每条边连接两个节点，并具有一个起始节点和一个终止节点。
• 出度和入度：
  • 出度：某个节点的出度是指从该节点出发的边的数量。
  • 入度：某个节点的入度是指指向该节点的边的数量。
• 路径： 在有向图中，路径是指从一个节点到另一个节点的一系列边，遵循边的方向。
• 连通性： 有向图可以是强连通的（每对节点都有路径相连）或弱连通的（忽略边的方向后，图是连通的）。

应用领域

有向图在许多领域都有广泛应用，包括：

• 社交网络：表示用户之间的关注关系。
• 网页链接：表示网页之间的超链接关系。
• 任务调度：表示任务之间的依赖关系。
• 路由问题：表示网络中的路由关系。

S2 示例

import networkx as nx
import matplotlib.pyplot as plt

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

# 添加节点
G.add_nodes_from([1, 2, 3, 4])

# 添加有向边
G.add_edges_from([(1, 2), (1, 3), (2, 4), (3, 4)])

# 绘制图形
pos = nx.spring_layout(G)  # 使用弹簧布局
nx.draw(G, pos, with_labels=True, arrows=True)
plt.title("Directed Graph Example")
plt.show()

# 计算入度和出度
for node in G.nodes():
    print(f"Node {
     node}: In-degree = {
     G.in_degree(node)}, Out-degree = {
     G.out_degree(node)}")

# 查找路径
path = nx.shortest_path(G, source=1, target=4)
print(f"The shortest path from 1 to 4 is: {
     path}")

结果

Node 1: In-degree = 0, Out-degree = 2
Node 2: In-degree = 1, Out-degree = 1
Node 3: In-degree = 1, Out-degree = 1
Node 4: In-degree = 2, Out-degree = 0
The shortest path from 1 to 4 is: [1, 2, 4]

S3 问题：利用有向图构建贝叶斯网络

Python代码

# 导入必要的库
from pgmpy.models import BayesianNetwork  # 贝叶斯网络模型
from pgmpy.factors.discrete import TabularCPD  # 条件概率分布（CPD）
from pgmpy.inference import VariableElimination  # 变量消除推理算法
import matplotlib.pyplot as plt  # 绘图库
import networkx as nx  # 网络图处理库

# macos系统显示中文
plt.rcParams['font.sans-serif'] = ['Arial Unicode MS']

# 定义贝叶斯网络的结构
# 有向边列表，表示节点之间的依赖关系
edges = [
    ('Cloudy', 'Sprinkler'),     # 多云影响洒水器的开启
    ('Cloudy', 'Rain'),          # 多云影响是否下雨
    ('Sprinkler', 'WetGrass'),   # 洒水器影响草坪是否湿润
    ('Rain', 'WetGrass'