用深度优先搜索计算极大独立集
无向图G=(V，E)的独立集是V的子集I使得I中没有两个顶点相邻。也就是说，如果u和v在I中，那么(u，v)不在E中。极大独立集M是一个独立集，这样，如果我们给M添加任何附加的顶点，那么它将不再是独立的。每个图都有一个极大独立集。（你能看到这个吗？这个问题不是练习的一部分，但值得思考。）给出了一个计算图G的最大独立集的有效算法。该方法的运行时间是多少？
我不确定对深度优先搜索的修改是否能解决上述问题，但这里是我的尝试（注意：我不是在寻找代码，只是对我应该做什么的高级描述）
使用DFS，我们将从某个起始顶点S1开始遍历图的所有顶点。从S1到一个相邻边S2，如果不存在相邻边，我们将S1加到最大独立集M中，因为这个顶点在G中的任何其他顶点之间没有边，如果是这样，那么我们选择另一个顶点S1'并从那个点（递归地）做DFS。
假设在S1和S2之间有一条边，那么我们可以将S1加到独立集合中，而不是S2，那么DFS继续，我们添加S3，因为S3与S1没有共享边，DFS继续，我们所做的就是继续将S[k]加到集合M中，只要它与M中已经存在的当前元素没有共享边。
这将占用我们O(V+E)的时间复杂度。原因：DFS是O(V+E)，每次我们移动到一个新节点时，我们必须对照M中的K个元素检查它，以确保它们不共享边。即O(k(V+E))=O(V+E)。
最坏的情况：空图，V调用DFS，给出O(V(V+E)
问题：
（1）这是正确的吗，我实际上是找到了极大独立集还是最大独立集？
（2）如果正确，这是否有效？
如果完全错了，我真的很感激一个解决方案，我已经考虑这个问题一段时间了。
共有1个答案
下面是我的解决方法：
输入：一组顶点v，邻接列表e[v]（每个顶点一个）：
- 准备一个数组
take[]大小v包含bool值。所有元素最初都设置为false。这个数组告诉我们哪些顶点被取为结果。 - 将
取[0]设置为为true。 - 对于每个顶点
v=1..v-1:如果e[v]不包含边(v,u)使得take[u]为true则将take[v]设置为true。 - 返回所有顶点
v，使take[v]为true。
-
主要内容：深度优先搜索（简称“深搜”或DFS）,广度优先搜索,总结前边介绍了有关图的 4 种存储方式，本节介绍如何对存储的图中的顶点进行遍历。常用的遍历方式有两种： 深度优先搜索和 广度优先搜索。 深度优先搜索（简称“深搜”或DFS） 图 1 无向图 深度优先搜索的过程类似于树的先序遍历，首先从例子中体会深度优先搜索。例如图 1 是一个无向图，采用深度优先算法遍历这个图的过程为： 首先任意找一个未被遍历过的顶点，例如从 V1 开始，由于 V1 率先访问过了，所以
-
本文向大家介绍深度优先搜索，包括了深度优先搜索的使用技巧和注意事项，需要的朋友参考一下 图遍历是按某种系统顺序访问图的所有顶点的问题。遍历图主要有两种方法。 广度优先搜索 深度优先搜索 深度优先搜索(DFS)算法从顶点v开始，然后遍历到之前未访问过的相邻顶点（例如x），并将其标记为“已访问”，然后继续处理x的相邻顶点，依此类推。 如果在任何一个顶点上遇到所有相邻顶点都被访问过，则它将回溯直到找到具
-
3. 深度优先搜索 现在我们用堆栈解决一个有意思的问题，定义一个二维数组： int maze[5][5] = { 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, }; 它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的路线
-
假设我有下面的迷宫:(格式不正确) S 表示迷宫的起点，E 表示迷宫的终点。我有两个给定的课程;和 .我必须构建以下递归助手方法来找到迷宫的解决方案： 此方法递归地找到一条从当前迷宫的开始到结束的路径，该路径通过当前Cell。该路径是从迷宫的开始到当前单元格的单元格序列的ArrayList（即到目前为止探索的路径）。为了避免超过所需的路径，算法应避免重新访问已在此路径中的单元格。如果没有从当前到结
-
骑士之旅是深度优先搜索的特殊情况，其目的是创建最深的第一棵树，没有任何分支。更一般的深度优先搜索实际上更容易。它的目标是尽可能深的搜索，在图中连接尽可能多的节点，并在必要时创建分支。 甚至可能的是，深度优先搜索将创建多于一个树。当深度优先搜索算法创建一组树时，我们称之为深度优先森林。与广度优先搜索一样，我们的深度优先搜索使用前导链接来构造树。此外，深度优先搜索将在顶点类中使用两个附加的实例变量。新
-
我在处理一个单词搜索问题。我正确地实现了dfs搜索，但在其他地方有一些琐碎的错误。