Python中实现图论算法

简介: Python中实现图论算法 “【5月更文挑战第20天】”

在Python中实现图论算法,我们通常会用到networkx这个库,它是一个强大的图论库,提供了丰富的数据结构和算法。以下是一个使用networkx库实现的图的深度优先搜索(DFS)算法的例子:

首先,确保你已经安装了networkx库。如果没有安装,可以通过以下命令安装:

pip install networkx

然后,我们可以编写一个简单的程序来实现DFS:

import networkx as nx

# 创建一个无向图
G = nx.Graph()

# 添加节点和边
G.add_edge(1, 2)
G.add_edge(1, 3)
G.add_edge(2, 4)
G.add_edge(3, 4)
G.add_edge(4, 5)

# 打印图的边
print("Edges in graph:", G.edges())

# 定义DFS函数
def dfs(graph, start):
    visited, stack = set(), [start]
    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            visited.add(vertex)
            stack.extend(graph.successors(vertex))
            print(vertex, end=' ')
    return visited

# 调用DFS函数并打印结果
print("\nDFS starting from node 1:")
dfs(G, 1)

在这个例子中,我们首先创建了一个无向图G,然后添加了一些边。接着,我们定义了一个dfs函数,它接受图和一个起始节点作为参数,执行深度优先搜索,并打印出遍历的节点顺序。

请注意,networkx本身也提供了DFS的实现,可以通过networkx.dfs_preorder_nodesnetworkx.dfs_postorder_nodes等函数直接使用。

此外,如果你想要实现自己的数据结构和算法而不是依赖networkx,下面是一个不使用networkx的DFS实现示例:

# 使用字典来表示图
graph = {
   
    1: [2, 3],
    2: [1, 4],
    3: [1, 4],
    4: [2, 3, 5],
    5: [4]
}

# 辅助函数:DFS的递归实现
def dfs_recursive(graph, node, visited):
    if node in visited:
        return
    print(node, end=' ')
    visited.add(node)
    for neighbour in graph[node]:
        dfs_recursive(graph, neighbour, visited)

# 调用DFS递归函数并传入起始节点1
visited = set()
dfs_recursive(graph, 1, visited)

在这个例子中,我们使用字典来表示图,其中键是节点,值是与该节点相连的节点列表。dfs_recursive函数是一个递归实现的DFS,它接受图、当前节点和已访问节点集合作为参数。

目录
相关文章
|
4天前
|
SQL 数据采集 算法
LeetCode 题目 66:加一【python5种算法实现】
LeetCode 题目 66:加一【python5种算法实现】
|
2天前
|
存储 算法 数据可视化
算法金 | D3blocks,一个超酷的 Python 库
D3Blocks是一个基于d3.js的Python图形库,用于创建吸引人的数据可视化图表,如D3graph、Elasticgraph和Sankey图。拥有超过470个Star,其特点包括简易性、功能丰富、易用性、可定制性和及时更新。通过pip安装后,用户能轻松创建粒子图和其他图表。文中展示了实战应用,如能源数据集的网络图,通过调整节点和边的属性实现个性化展示。关注作者,享受智能乐趣。
35 8
算法金 | D3blocks,一个超酷的 Python 库
|
3天前
|
存储 算法 数据可视化
python多种算法对比图解实现 验证二叉树搜索树【力扣98】
python多种算法对比图解实现 验证二叉树搜索树【力扣98】
|
3天前
|
机器学习/深度学习 算法 TensorFlow
算法金 | 只需十四步:从零开始掌握Python机器学习(附资源)
```markdown ## 摘要 全网同名「算法金」的作者分享了一篇针对Python机器学习入门的教程。教程旨在帮助零基础学习者掌握Python和机器学习,利用免费资源成为实践者。内容分为基础篇和进阶篇,覆盖Python基础、机器学习概念、数据预处理、科学计算库(如NumPy、Pandas和Matplotlib)以及深度学习(TensorFlow、Keras)。此外,还包括进阶算法如SVM、随机森林和神经网络。教程还强调了实践和理解最新趋势的重要性。
7 0
算法金 | 只需十四步:从零开始掌握Python机器学习(附资源)
|
4天前
|
存储 算法 Unix
掌握Unix路径简化:五种有效算法比较【python力扣71题】
掌握Unix路径简化:五种有效算法比较【python力扣71题】
|
4天前
|
存储 算法 机器人
路径规划的艺术:不同路径 II 的算法深掘【python力扣63题】
路径规划的艺术:不同路径 II 的算法深掘【python力扣63题】
|
4天前
|
存储 算法 数据挖掘
python5种算法模拟螺旋、分层填充、递归、迭代、分治实现螺旋矩阵ll【力扣题59】
python5种算法模拟螺旋、分层填充、递归、迭代、分治实现螺旋矩阵ll【力扣题59】
|
4天前
|
存储 SQL 算法
LeetCode题58: 5种算法实现最后一个单词的长度【python】
LeetCode题58: 5种算法实现最后一个单词的长度【python】
|
4天前
|
存储 算法 搜索推荐
掌握区间合并:解决实际问题的算法策略和应用案例【python LeetCode题目56】
掌握区间合并:解决实际问题的算法策略和应用案例【python LeetCode题目56】
|
4天前
|
算法 数据挖掘 开发者
LeetCode题目55:跳跃游戏【python5种算法贪心/回溯/动态规划/优化贪心/索引哈希映射 详解】
LeetCode题目55:跳跃游戏【python5种算法贪心/回溯/动态规划/优化贪心/索引哈希映射 详解】