算法基础：图算法和广度优先搜索（Python版本）

本博客所呈现的所有内容均源自《算法图解》一书，欢迎大家进行探讨与交流~

提及图算法以及广度优先搜索时，首先需要理解这两类算法的实际用途。在此，我将引用《算法图解》中所列举的一个典型实例进行说明。

在许多场景下，我们常常希望确定两个对象之间的最短路径。这里的“距离”并非仅指物理上的长度，其含义可以多种多样。下面来看几个具体的问题：

• 设计国际跳棋的人工智能程序，以计算实现胜利所需的最少步数；
• 开发拼写检查工具，以计算将错误拼写的单词修正为正确形式所需的最少修改次数；
• 在人际关系网络中寻找与自己联系最为紧密的医生。

实际上，上述问题均可归类为最短路径问题。那么面对此类问题该如何解决呢？

让我们从一个最为基础的最短路径问题出发进行思考。假设你现在居住在北京，并计划外出旅行。在此过程中暂且不考虑旅费、交通等其他因素，仅关注唯一变量——距离。在可选的城市包括上海、南京、天津、合肥、成都、东京和纽约之中，哪一个城市所需旅行的距离最短？

显然，在这个问题上许多人凭借经验便可得出答案：天津是最近的选择；那么如果我们稍作调整，不再仅仅寻找前往一个城市的最优路径，而是要求必须依次访问上述所有城市，并最终返回北京的情况下，应选择怎样的路线才能使总距离最短呢？

显然这一问题变得较为复杂了。事实上这属于经典的旅行商问题，在这种情况下我们需要列举出所有可能的路线，并逐一比较