leetcode 链接所有可能的路径1 图的基本概念1.1 有向图和无向图左边是有向图右边是无向图。对于无向图来说图中的边没有方向两个节点之间只可能存在一条边比如 0 和 1 之间的边因为是无向图这条边可以表示从 0 到 1 的边也可以表示从 1 到 0 的边。对于有向图来说图中的边有方向 0 和 1 之间可以存在两条边一条表示从 0 到 1 的边一条表示从 1 到 0 的边。用邻接矩阵来表示上边两个图如下所示。// 有向图 [ [1], // 有从 0 到 1 的边 [0 2], // 从 1 到 0 的边和从 1 到 2 的边 [0] // 从 2 到 0 的边 ] // 无向图 [ [1, 2], // 从 0 到 1 和从 0 到 2 的边 [0, 2], // 从 1 到 0 和从 1 到 2 的边 [0, 1] // 从 2 到 0 和从 2 到 1 的边 ]1.2 有环图和无环图讨论有环图还是无环图一般说的是有向图。因为对于无向图来说从 0 到 1 有边那么从 1 到 0 就有边本身就是一个环。有环图说的是从一个节点开始遍历在遍历过程中还能遍历到这个节点的图除了开始节点和结束节点是相同的其它节点不能重复出现并且路径长度大于 2。在图的遍历算法中为了防止一个节点被重复遍历往往需要一个 visited[n] 数组来标记一个节点是不是被遍历过。visited 数组下标是节点的值元素值均被初始化为 0当一个节点被遍历时则将值改为 1。对于有向有环图来说需要 visited 数组来标记因为有环一个节点可能被多次访问对于有向无环图来说一个节点不会被重复遍历所以不需要 visited 数组来标记。1.3 连通图和非连通图下边两个图上边的是非连通图下边的是连通图。连通图指的是从一个节点出发沿着边进行遍历能把图中的节点都遍历到的图。 这个很像那种益智小游戏看怎么样能一笔把图中的所有点连起来。当对图做遍历时如果图是连通的那么从一个节点开始遍历一次就能将图中所有的节点遍历一遍所以遍历一次就可以了。如果图不是连通的那么遍历一次无法将所有的点都遍历一遍这个时候要从每个点都开始每个节点都要开始一次遍历一遍。2 深度优先搜索和广度优先搜索图是一种二维的数据结构可以使用邻接表或者邻接矩阵来表示更多的使用邻接表来表示有行和列。1.3 节中连通图的邻接矩阵表示如下深度优先从遍历过程来看优先在纵向遍历纵深深度。广度优先从遍历过程来看优先在横向遍历横向是广度。纵向是深度横向是广度。上边这个图从节点 0 开始遍历第一步遍历到节点 1下一步遍历的选择就是深度优先和广度优先的区别。下一步遍历 1 节点开始的链表也就是跳到第二行开始遍历遍历到节点 1 的邻接点 2这就是深度优先遍历下一步还是在 0 这一行遍历节点 2这就是广度优先遍历。深度优先遍历和广度优先遍历不仅仅适用于图这种数据结构。二叉树的遍历包括前序遍历中序遍历后序遍历以及层序遍历。前 3 种遍历方式属于深度优先遍历层序遍历属于广度优先遍历。二叉树也属于二维的数据结构。二叉树遍历算法和应用广度优先遍历层序遍历借助queue来实现一层入队出队的时候再遍历深度优先遍历针对每一个新的节点都进行dfs。2.1 时间复杂度深度优先和广度优先遍历图都是沿着边进行遍历的。如果节点个数是 n那么对于无向图来说边的个数最大是 n(n - 1)/2对有向图来说边的个数最大是 n(n - 1)。所以最差的情况下两种算法的时间复杂度均是 O(n * n)。3 所有可能的路径如下是 leetcode 中的题目说明。题意中的图是有向无环图有向并且没有环所以在遍历的时候不需要使用 visited 数据来标记一个节点是不是被访问过因为没有环一个节点不会被重复访问。3.1 深度优先这个题目适合使用深度优先遍历算法。深度优先遍历是递归算法递归算法需要注意两点递归退出条件一定要有退出条件否则会一直递归下去递归体也就是递归算法的主要逻辑。递归算法的这两点与循环类似循环算法也包括循环退出条件和循环主要逻辑。找路径的题目使用递归算法的题目不管是图和是二叉树最核心的就是如下代码注释中的三段式。1将节点加入到路径2递归3将节点移出路径为什么加入的节点要移出呢因为这个节点加入之后进行了递归运算。也就是说以这个节点为基础的路径都已经全部遍历。下一次要遍历的节点与这个节点是并列的节点并不是路径的前后关系它们属于这一行的邻接点。要进行下一步遍历这个节点需要移出因为后边遍历的节点跟这个节点不在一个路径只不过都是当前这一行的得邻接点而已。class Solution { public: vectorvectorint allPathsSourceTarget(vectorvectorint graph) { const int n graph.size(); // 没有数据直接返回 if (n 0) { return ret; } // 要找的路径是从 o 到 n - 1 // 所以从 0 开始遍历 // 在遍历之前要把这个点加入到路径中 one_path.push_back(0); // 深度优先遍历 DfsScan(graph, 0, n); return ret; } // 深度优先遍历时一种递归算法 void DfsScan(vectorvectorint graph, int index, const int n) { // 递归退出条件当前这个点是 n - 1 的时候说明找到了这样一个路径 // 将这条路径加入到结果中 if (index n - 1) { ret.push_back(one_path); return; } // 递归体深度优先搜索 // 对于遍历的这个节点找到这个节点锁代表的这一行遍历这一行 // 这种方式取出数据的一行会发生拷贝直接使用引用来获取数据可以避免数据拷贝 // vectorint line graph[index]; // int line_size line.size(); // for (int i 0; i line_size; i) { for (int data : graph[index]) { // 三段式 // 1、push_back 将节点加入到路径中 // 2、递归运算 // 3、将节点从路径中移走 one_path.push_back(data); DfsScan(graph, data, n); one_path.pop_back(); } } private: vectorvectorint ret; vectorint one_path; };3.2 广度优先广度优先需要使用一个队列和循环算法。在循环之前将一个元素加入到队列中循环的条件是队列不为空循环中的逻辑是把新遍历到的节点加入到队列中。找路径这样的题目广度优先没有深度优先好理解。深度优先在遍历的过程中前后相邻的两个被遍历的点一定是一条路径上的前后的两个点这样遍历到一个点直接追加到路径上就可以。而广度优先遍历不是这样的相邻两次遍历的点不是属于路径上的前后点而是只属于当前这一行首节点的邻接点。这样就需要给每个节点维护一个路径当这个节点是首节点的时候那么这个节点的所有邻接点的路径都要更新都要在这个首节点的路径的基础上加上当前这个节点。class Solution { public: struct Node { int data; vectorint path; }; vectorvectorint allPathsSourceTarget(vectorvectorint graph) { int size graph.size(); if (size 0) { return ret; } Node node; node.data 0; // 将节点加入到队列中 // 节点保存着到当前这个节点的路径 node.path.push_back(0); // 循环的出发条件只要队列不是空循环就继续进行 q.push(node); while (!q.empty()) { // 从队列中获取一个元素 // 开始遍历以这个元素为行首的节点即广度优先遍历 Node tmp q.front(); q.pop(); for (int d : graph[tmp.data]) { Node linenode; linenode.data d; linenode.path tmp.path; linenode.path.push_back(d); // 当前这个节点是 size - 1 了找到了满足条件的一个路径 // 那么这个节点就不需要加入队列了 // 加入队列之后下次遍历的时候路径后边还要加入其它节点 // 继续追加没有意义因为当前已经是要找的路径了 if (d size - 1) { ret.push_back(linenode.path); } else { q.push(linenode); } } } return ret; } private: std::queueNode q; vectorvectorint ret; };4被围绕的区域、岛屿数量现在的思维能力你是已经很差了思考一步都思考不了工具放在这里一步都思考不了。下边这两个题都是使用图的遍历算法加上一个题目特定的步骤就可以了就是一小步自己就想不起来。这两个题目其实都很典型都是图的遍历算法的经典功能图的遍历过程一次遍历其实就是一个相互连通的区域。这两个题目才是图的最经典的题目。深度优先搜索dfs是递归算法。130. 被围绕的区域 - 力扣LeetCode200. 岛屿数量 - 力扣LeetCode确定一个连续的区域深度优先是可以理解的广度优先能实现这样的功能吗要优先选用深度优先遍历。