图以及深度优先和广度优先

深度优先算法和广度优先算法的时间复杂度深度优先算法和广度优先算法是在图论中常见的两种搜索算法，它们在解决各种问题时都有很重要的作用。

本文将以深入浅出的方式从时间复杂度的角度对这两种算法进行全面评估，并探讨它们在实际应用中的优劣势。

1. 深度优先算法的时间复杂度深度优先算法是一种用于遍历或搜索树或图的算法。

它从图中的某个顶点出发，沿着一条路径一直走到底，直到不能再前进为止，然后回溯到上一个节点，尝试走其他的路径，直到所有路径都被走过为止。

深度优先算法的时间复杂度与图的深度有关。

在最坏情况下，深度优先算法的时间复杂度为O(V+E)，其中V表示顶点的数量，E表示边的数量。

2. 广度优先算法的时间复杂度广度优先算法也是一种用于遍历或搜索树或图的算法。

与深度优先算法不同的是，广度优先算法是从图的某个顶点出发，首先访问这个顶点的所有邻接节点，然后再依次访问这些节点的邻接节点，依次类推。

广度优先算法的时间复杂度与图中边的数量有关。

在最坏情况下，广度优先算法的时间复杂度为O(V+E)。

3. 深度优先算法与广度优先算法的比较从时间复杂度的角度来看，深度优先算法和广度优先算法在最坏情况下都是O(V+E)，并没有明显的差异。

但从实际运行情况来看，深度优先算法和广度优先算法的性能差异是显而易见的。

在一般情况下，广度优先算法要比深度优先算法快，因为广度优先算法的搜索速度更快，且能够更快地找到最短路径。

4. 个人观点和理解在实际应用中，选择深度优先算法还是广度优先算法取决于具体的问题。

如果要找到两个节点之间的最短路径，那么广度优先算法是更好的选择；而如果要搜索整个图，那么深度优先算法可能是更好的选择。

要根据具体的问题来选择合适的算法。

5. 总结和回顾本文从时间复杂度的角度对深度优先算法和广度优先算法进行了全面评估，探讨了它们的优劣势和实际应用中的选择。

通过对两种算法的时间复杂度进行比较，可以更全面、深刻和灵活地理解深度优先算法和广度优先算法的特点和适用场景。

二、 重排九宫问题游戏
在一个 3 乘 3 的九宫中有 1-8 的 8 个数及一个空格随机摆放在其中的格子里。如下面 左图所示。现在要求实现这样的问题：将该九宫调整为如下图右图所示的形式。调整规则是： 每次只能将与空格（上，下或左，右）相临的一个数字平移到空格中。试编程实现。
|2|8 |3|
|1|2|3|
from = f; to = t; distance = d; skip = false; } } class Depth { final int MAX = 100; // This array holds the flight information. FlightInfo flights[] = new FlightInfo[MAX]; int numFlights = 0; // number of entries in flight array Stack btStack = new Stack(); // backtrack stack public static void main(String args[]) {
下面是用深度优先搜索求解的程序:
// Find connections using a depth-first search. import java.util.*; import java.io.*; // Flight information. class FlightInfo {
String from; String to; int distance; boolean skip; // used in backtracking FlightInfo(String f, String t, int d) {
int dist; FlightInfo f; // See if at destination. dist = match(from, to); if(dist != 0) {

附录：图结构、深度优先搜索和广度优先搜索
1.图结构时一种比线性结构和树形结构更为复杂的线性结构。

线性结构中每个节点最多只有一个前驱节点和一个后继节点；树形结构中每个节点最多只有一个前驱节点，可以有多个后继节点；而图结构每个节点的前驱节点和后驱节点的个数都不是唯一的。

2.图结构根据节点之间的关系可以分为有向图、无向图、连通图和非连通图。

3.图结构处理——深度优先搜索和广度优先搜索
例题：公司安排小张到H市出差，从小张所在的A市到H市没有直达公交，需要中转若干个城市，但中转方式不唯一。

如图所示，从A市到H市有多种方案，请编写代码找出中转次数最少的方案。

用二维数组来存储城市之间的中转方案图，城市A-H分别编号为0-7。

用数值1来表示表格
①广度优先搜索（BFS）—找到最短路径
首先将起点入队，然后取出队首元素X，将X市可达的所有城市依次入队，不断重复次操
经过的节点都存放在同一个队列中，需要输出最短路径经过的节点时，需要在节点入队时就存储前向指针，构建节点间的逻辑关系。

②深度优先搜索(DFS)——找出全部路径
首先将起点入栈，然后取出栈顶元素X市，将X市可达的城市中的一个入栈，不断重复操
故在到达目的地时，栈空间中存储的就是换乘路线。

广度优先和深度优先的例子广度优先搜索(BFS)和深度优先搜索(DFS)是图遍历中常用的两种算法。

它们在解决许多问题时都能提供有效的解决方案。

本文将分别介绍广度优先搜索和深度优先搜索，并给出各自的应用例子。

一、广度优先搜索(BFS)广度优先搜索是一种遍历或搜索图的算法，它从起始节点开始，逐层扩展，先访问起始节点的所有邻居节点，再依次访问其邻居节点的邻居节点，直到遍历完所有节点或找到目标节点。

例子1：迷宫问题假设有一个迷宫，迷宫中有多个房间，每个房间有四个相邻的房间：上、下、左、右。

现在我们需要找到从起始房间到目标房间的最短路径。

可以使用广度优先搜索算法来解决这个问题。

例子2：社交网络中的好友推荐在社交网络中，我们希望给用户推荐可能认识的新朋友。

可以使用广度优先搜索算法从用户的好友列表开始，逐层扩展，找到可能认识的新朋友。

例子3：网页爬虫网页爬虫是搜索引擎抓取网页的重要工具。

爬虫可以使用广度优先搜索算法从一个网页开始，逐层扩展，找到所有相关的网页并进行抓取。

例子4：图的最短路径在图中，我们希望找到两个节点之间的最短路径。

可以使用广度优先搜索算法从起始节点开始，逐层扩展，直到找到目标节点。

例子5：推荐系统在推荐系统中，我们希望给用户推荐可能感兴趣的物品。

可以使用广度优先搜索算法从用户喜欢的物品开始，逐层扩展，找到可能感兴趣的其他物品。

二、深度优先搜索(DFS)深度优先搜索是一种遍历或搜索图的算法，它从起始节点开始，沿着一条路径一直走到底，直到不能再继续下去为止，然后回溯到上一个节点，继续探索其他路径。

例子1：二叉树的遍历在二叉树中，深度优先搜索算法可以用来实现前序遍历、中序遍历和后序遍历。

通过深度优先搜索算法，我们可以按照不同的遍历顺序找到二叉树中所有节点。

例子2：回溯算法回溯算法是一种通过深度优先搜索的方式，在问题的解空间中搜索所有可能的解的算法。

回溯算法常用于解决组合问题、排列问题和子集问题。

例子3：拓扑排序拓扑排序是一种对有向无环图(DAG)进行排序的算法。