Python图算法

图，那些由节点和线组成的纠结的东西，在数学中非常有用。它们有助于解决计算机网络或研究化学形状等棘手问题。它们也是解决城市交通、寻找最佳路线甚至破译人类语言怪癖的秘诀。现在，真正的难题是我们如何使用这些线来访问每个节点，在这些图中移动。有两种众所周知的技巧可以解决这个挑战，我们将在下面揭示它们。

好的，我理解您对具有“困惑度”和“突发度”的文本的要求。在讨论深度优先搜索 (DFS) 和广度优先搜索 (BFS) 图搜索算法时，我将保持这些特征。让我们深入了解这些算法的细节及其底层机制。

深度优先搜索 (DFS) 和广度优先搜索 (BFS) 是基本的图搜索算法，在理解和导航图结构方面发挥着至关重要的作用。

DFS 是我们讨论的第一个算法，它通过一个接一个地遍历图的顶点，沿着其连接的顶点移动，如附带的 GIF 精美地所示。这就像在茂密的森林中循着一条小径，只要分支存在就深入其中。当 DFS 遇到死胡同（例如 GIF 中的顶点 #4）时，它会回溯以检查从起点（顶点 #1）发出的任何其他未探索的分支。DFS 擅长探索类似于线性路径的图结构，没有众多分支选项。

另一方面，BFS 是我们正在探索的第二个算法，它更适用于类似于密集互连网络的图结构，类似于具有众多分支的树。BFS 采用一种策略，在继续前进之前全面检查所有连接的顶点。BFS 不像 DFS 那样沿着单个分支（1 -> 2 -> 3 -> 4）前进，而是并行地查看连接到顶点 #1 的所有相邻顶点，启动类似于您深呼吸时产生的涟漪（因此得名）。

那么，是什么让这些算法起作用呢？魔力在于它们的机制和逻辑。DFS 依赖递归，在回溯之前尽可能深入，而 BFS 则采用队列数据结构同时探索所有相邻顶点。理解各种物理原理对于开发这些算法至关重要。

在这篇文章中，我们将更深入地探讨 DFS 和 BFS 的内部运作，解释它们的原理，并提供代码示例，以确保您完全理解这些概念。在我们探索完这些数学概念之后，您必须对它们的工作原理以及如何在实际情况中使用它们有一个很好的了解。所以让我们从 DFS 开始，深入探讨图搜索算法的领域。

深度优先遍历

在进行深度优先搜索 (DFS) 时，我们使用地址列表来记录我们的位置，并使用堆栈来方便我们在探索完一个分支后想要返回时回溯。假设我们正在检查图上的一条路线，从 1 移动到 2，然后到 4，然后到 9，最后到 7。稍后，当我们到达顶点 7 时，我们可能会问我们是否已经探索了所有数据，或者我们是否只是到达了当前分支的末端。我们如何解决这个问题？话虽如此，我们可以信任我们正在使用的堆栈。我们的想法是确保我们尽可能长时间地留在它上面，转移到新的位置。但是，当我们无法从当前位置移动到任何新顶点时，我们开始一个接一个地从堆栈中取出顶点。所以，我们首先移除 7。现在，我们在 9，同样，没有其他地方可去，所以我们取出 9。4 也发生同样的情况。但是当我们在顶点 2 时，我们注意到我们仍然可以移动到顶点 8。所以，我们探索 8，再次，我们到达一个无法再前进的点。我们重复这个过程，回到 2，然后到 1。

当我们的堆栈用尽时，我们认为整个图的遍历已完成。在探索图的不同部分时，堆栈可以保持进度，它还可以让我们跟踪我们去过的地方。

在使用图时，有时我们必须沿着特定路径才能找到所需数据。这类似于在迷宫般的路径中工作。实现这一点的一种方法是使用深度优先搜索，简称 DFS。

DFS 的功能类似于侦探寻找线索。它不是立即检查整个区域，而是深入可视化中的某个部分，并沿着该路线前进，直到达到其极限。之后，它会转身尝试不同的路线。

DFS 采用一种称为“堆栈”的设备，其操作类似于数字便签纸，以跟踪已经去过的地方和仍然需要去的地方。

DFS 在开始时会查看线形图中的一个区域。如果它遇到死胡同，就像迷宫中未完成的街道一样，它会返回到上次有选择的先前位置。通过这种方式，它不会忽略任何潜在的路线。

在 Python 中，我们可以通过使用称为“集合”的数据类型来实现 DFS 来探索图。集合使我们能够维护我们之前探索过的图区域以及我们继续返回的区域的历史记录。这类似于在我们访问过的位置旁边做一个小标记。

简而言之，DFS 是一种聪明的方法，可以导航相互连接的点或数据的迷宫。它就像一个侦探，跟踪线索，必要时回溯，并使用笔记记住他们去过的地方。在 Python 中，我们使用集合来保持侦探的踪迹清晰和有条理。

代码

输出

a
c
d
e

代码解释

这段代码是关于创建一个 Python 类来处理图并执行称为深度优先搜索 (DFS) 的操作。让我们剖析它并理解每个阶段正在发生的事情。

1. 图类解释： 以下代码使用名为“graph”的 Python 类。它有一个称为构造函数的独特方法，用字母“init”表示。表示图的条目列表是此构造函数可以接受的额外输入。即使您不提供，它也会为您生成一个空词汇表。一个类包含保存其中的此字典。
2. DFS 函数定义： 代码还定义了一个名为“dfs”的函数，代表深度优先搜索。此函数以递归方式实现，这意味着它会调用自身来解决问题。它接受三个输入
   1. 图：这是一个字典，表示您要使用 DFS 探索的图。
   2. 开始：它是 DFS 开始的节点。
   3. 已访问（可选）：这充当一种日志簿，记录在查找过程中查看的节点。如果它不存在，该函数将生成一个额外的。
3. “dfs”函数内部： 如果您没有提供“visited”记录，该函数会创建一个空的。它将“start”节点标记为已访问，就像在其上插一面旗帜。它还会让您在屏幕上知道它正在访问“start”节点。然后，它会遍历“start”节点的每个尚未访问的邻居（基本上是与当前节点连接但尚未探索的节点）。对于每个未访问的邻居，它会再次运行“dfs”函数，从该邻居开始。
4. 从图创建字典： 此代码提供了一个表示基本定向图的字典示例。此图中有标签为“a”、“b”、“c”、“d”和“e”的节点。字典中包含的标签是节点，冒号后面的数字（标签后面的对象）是彼此相邻的节点集合。
   使用 DFS 功能： 最后，有一行代码类似于此。
5. dfs(dict, 'a')
6. 继续使用先前建立的图中的“a”节点，此行调用“dfs”程序执行深度优先搜索。已访问节点的列表以及访问节点的时间顺序将作为此查询的输出返回。

广度优先搜索

一种称为广度优先搜索（简称 BFS）的技术对您来说并不陌生。这种结构探索方法类似于逐层遍历图并以这种方式了解它。我们利用一个队列——基本上是一群等待轮到他们的人——来跟踪我们的去向。这有助于我们记住下一步需要访问哪个顶点。

研究和理解结构中连接不同节点的关系的一种方法是使用广度优先搜索技术，简称 BFS。用通俗的话说，让我解释它是如何运作的。假设在一张纸上，有许多相互连接的点，例如定居点。在 BFS 中，您从一个城市开始，我们称之为城市 #1。BFS 不会立即跳到相邻的城市，例如城市 #2，而是采用更彻底的方法。此外，它还前往与城市 #1 关联的城市 #3。因此，我们将城市 #1、城市 #2 和城市 #3 添加到我们将称为“队列”的城市集合中。

目前，我们查看城市 #1，看它是否与任何其他区域有连接。如果它已经到达了它能够访问的每个相邻城市，我们就将其从队列中取出。在城市 #1 从队伍中移除后，我们继续前往城市 #2。作为回应，城市 #2 扫描该区域以寻找附近的城市并将它们添加到队列中。由于它与城市 #2 的连接，因此它可能包括城市 #4、#7 和 #8。

当我们去过每个城市并且您的等待为空时，我们继续执行相同的过程。

要记住的关键区别是，BFS 在移动到下一个点之前会彻底探索一个点的所有连接。相比之下，另一种称为深度优先搜索 (DFS) 的方法一旦访问新点就会继续前进，而不会首先完全探索所有连接。

想象一下您在一个迷宫中，偶尔会遇到死胡同。这就是我们在狩猎过程中发生的事情。当没有更多路径可循时，我们利用队列将我们引导到我们随后的搜索区域。一旦没有更多位置可检查，我们的任务就结束了。

您可以查看我们网页上的详细信息，以了解有关 BFS 如何使用图的更多信息。为了完成这项工作，我们使用了一个名为队列的数据结构与 Python 结合使用。我们不断移动到尚未访问的相邻位置并将它们添加到我们的队列中。然后，我们取出队列中的第一个位置并访问它。我们重复此过程，直到没有更多未访问的位置。

换句话说，BFS 可以被认为是一种系统的方法，用于仔细检查图，确保不会遗漏任何潜在的路径。

代码

输出

a
c
d
e

代码解释

这段代码介绍了一种处理图的简单方法，以及一种称为广度优先搜索 (BFS) 的方法来探索这些图。让我们以更易懂的方式逐步讲解这段代码

1. 导入集合模块： 在代码的第一部分，我们导入了一个名为“collections”的模块。这个模块帮助我们创建一种特殊类型的列表，称为“deque”（双端队列的缩写），它对于执行 BFS 很有用。
2. 定义图类： 接下来，我们定义一个名为“graph”的类。这个类代表一个图。把它想象成一个绘制图的说明手册。上面的类包含一个名为“init”的独特方法，并在创建新图时调用。您可以在创建图时提供一个字典来定义其结构。但是有一个小错误：它应该使用“dict”而不是“gdict”作为参数名。
3. 创建一个空图： “gdict = {}”这一行创建一个空字典，我们在这里存储图的结构。
4. 连接图： “self.gdict = gdict”这一行将您提供的字典（如果您没有提供，则为空字典）连接到图实例。
5. 广度优先搜索函数： 代码定义了一个名为“bfs”的函数，用于在图上执行 BFS。它需要两样东西：您要搜索的图和搜索的起始点（节点）。
6. 跟踪已访问节点： 在“bfs”函数内部，有一个名为“seen”的集合，用于跟踪我们已访问的节点。还有一个名为“queue”的双端队列，用于跟踪我们需要探索的节点。
7. 主 BFS 循环： 代码使用“while”循环执行 BFS。只要队列中有节点要探索，它就会一直循环。
8. 处理当前节点： 在下一个循环中，我们选择队列中离最后一个节点最远的节点。我们目前正在检查这个节点。因此，这个节点被一个名为“marked”的算法用来执行一个动作（打印它的值）。此后，以下代码定义了“marked”操作。
9. 检查邻居： 接下来，源代码检查网络中作为当前节点邻居的每个节点，如果它们尚未被查看，则将它们放入队列中。
10. 标记已访问节点： 方法“marked(n)”只输出以“n”开头的节点中包含的值。这用于在 BFS 期间将节点标记为已访问。
11. 示例图： 最后是一个线形图的插图，表示为一个字典，其中每个元素都是一个条目，并且每个相邻的节点组都是链接结果。
12. 启动 BFS： 代码启动 BFS 搜索，从字典表示的图中的节点“a”开始。

Python 图算法的优点

Python 是一种流行且灵活的计算机语言，人们使用它来处理图算法。它在处理与图相关的数据结构和算法时提供了许多好处。以下是 Python 在图算法方面表现出色的原因

1. Python 的语法易于学习和理解，几乎不需要阅读。处理图等复杂对象对于新手和经验丰富的程序员都非常有帮助。
   Python 语言有许多有用的库可供选择，如果您想处理图和图算法，它是一个不错的选择。您拥有 NetworkX 和 igraph 等工具，它们可以帮助您完成各种与图相关的事情。
2. 免费和开源：Python 中许多与图相关的工具都是开源的。这意味着它们是免费的，可以适应不同的用途。这一切都关乎共享和团队合作。
3. 随处可用：Python 就像一种通用语言；它可以在各种计算机上运行，无需更改。这对于需要在不同系统上工作的项目很方便。
4. 与他人良好协作：Python 很容易与 NumPy、SciPy 和 scikit-learn 等其他数据科学和机器学习工具连接。这使其成为将图算法与其他数据分析技术结合起来的强大工具。
5. 易于测试和实验：Python 的交互式开发环境非常适合尝试图算法。Jupyter notebook 非常适合创建包含代码和解释的交互式文档。
6. 可以创建精美图片：Python 有许多工具可以美化图。这很重要，因为它有助于我们有效地理解和共享图数据。
7. 大型社区：Python 用户有一个庞大而活跃的社区，包括开发人员、数据科学家和研究人员。他们为正确执行图算法提供支持、文档和资源。
8. 适用于大数据：您可以将 Python 与其他技术结合使用来处理海量数据集。Dask 和 PySpark 等工具有助于加速和分散处理图的工作。
9. 数据清理和分析：Python 有大量库用于在使用图算法之前整理数据。这使您的数据更好，您的算法更智能。
10. 与机器学习良好协作：Python 非常适合将基于图的机器学习模型添加到更大的机器学习项目中。这使得使用图数据进行预测变得更容易。
11. 适用于许多领域：Python 的灵活性和图库的范围使其适用于各种事物。您可以将其用于分析社交网络、研究生物学、构建推荐系统和改进网络等。

简而言之，Python 易于理解的语言、灵活性、广泛的图相关工具和强大的社区支持使其成为在许多不同领域处理和试验图算法的绝佳选择。

Python 图算法的缺点

Python 是一种广泛用于图算法的编程语言。它因其简单性和可用 NetworkX 和 igraph 等有用库而受到青睐。然而，使用 Python 处理图算法仍然存在一些缺点

性能：由于 Python 是一种解释性语言，它可能不如 Java 或 C++ 等语言快。在处理涉及大型图的密集计算的图算法时，这种性能差异会变得更加明显。

1. 内存使用：与用 C 或 C++ 等语言编写的对象相比，Python 中的对象通常使用更大的内存量。在处理大型图时，这可能会出现问题，因为它会占用大量内存。
   全局解释器锁 (GIL)：全局解释器锁是 Python 的一个特性，它阻止多个线程同时运行 Python 代码。这限制了对某些图算法使用多线程的有效性，而这些算法原本可以针对并行执行进行优化。
2. 有限的并行性：尽管 Python 提供了像多进程这样的库用于并行处理，但由于 GIL 和管理并发任务的复杂性，实现高效的并行性可能具有挑战性。
3. 对外部库的依赖：Python 依赖于 NetworkX 和 igraph 等外部库来实现图算法。这意味着您必须确保正确维护和部署软件包，这在使用多个平台时可能很困难。
   不适用于实时应用程序：由于其速度低于低级方言，因此 Pi 可能不是即时或低延迟应用程序的理想选择。
   缺少静态类型：Python 使用变量类型，这可能导致在运行时出现错误，并且可能直到软件运行时才变得明显。这对于更大更复杂的图算法可能是一个问题。
4. 有限的编译器优化：Python 缺少静态类型编译语言中发现的某些编译器优化，导致在某些情况下性能不佳。
5. 对超大型图的支持有限：Python 可能不是处理需要专门内存和存储优化的超大型图的最佳选择。在这种情况下，专门的图数据库和 C/C++ 等语言可能更合适。
6. 对内存管理的控制较少：Python 抽象了大部分内存管理，这有利于易用性，但在图算法需要对内存分配和解除分配进行细粒度控制时，这可能是一个缺点。

尽管存在这些缺点，Python 仍然是原型设计和处理中小型图算法的首选，尤其是在性能不是首要任务时。对于需要高性能和高效率的应用程序，开发人员通常会寻找其他语言或考虑将 Python 与低级语言集成以满足这些需求。

结论

Python 是一种流行的编程语言，以其多功能性和简洁性而闻名。它广泛用于解决涉及图（具有相互连接的点或节点的结构）的复杂问题。图算法在网络分析和推荐系统等领域至关重要。

当我们深入 Python 中的图算法世界时，我们会发现大量的工具和资源。其中一个突出的是 NetworkX 库。它就像一个强大的工具箱，用于创建、研究和可视化复杂的网络和图。其直观的布局和全面的文档使其易于理解，即使对于那些没有经验的程序员也是如此。稍有更多经验，它仍然是一个有用的工具。

Python 工具包中的另一个宝藏是 SciPy 库。它提供了先进的方法来有效解决复杂的图问题。科学家和工程师尤其受益于 SciPy，因为它帮助他们解决了各自领域中的复杂问题。

Python 的超能力之一是其丰富的社区。许多开发人员和用户积极为该语言做出贡献。这意味着您总能找到与图算法相关的帮助、教程和开源项目。这是一个推动创新和创建尖端解决方案的社区。

Python 的吸引力不仅限于其库。它是一种易于阅读和使用的语言，这在处理图算法时是一个很大的优势。其语法允许简洁的代码，使其清晰易懂。

总之，Python 因其出色的库支持、SciPy 和 NetworkX 等出色工具以及活跃的社区而成为图算法的绝佳选择。无论您是研究人员、设计人员还是数据分析师，Python 都能为您提供快速有效地解决复杂网络问题所需的工具。它是各个领域不可或缺的资产。