仅给定邻接矩阵在线性时间内检查图的性质
我遇到了一个关于图形的问题。让我们定义一个rake图。
当满足某些条件时，n顶点图是耙子:
- 图中有一个度为1的顶点。
- 此顶点连接到2度的顶点。
- 该第二顶点连接到阶数为n-2的另一顶点。其他顶点可以相互连接，也可以不相互连接
有人给了我一个n顶点图的邻接矩阵。我的任务是检查由给定矩阵表示的图是否是“rake”。问题是这必须在线性时间内完成。
我什么都试过了。当你有一个邻接列表时，这很容易做到，但是在给定矩阵的情况下，我如何使它花费O（n）时间呢？
共有1个答案
好吧，我似乎找到了答案！确实有一种线性时间算法可以解决这个问题，因为我提出的问题在科学界被称为检查图是否是蝎子图！
在这里你可以找到我一直在寻找的算法。http://www.cs.cornell.edu/courses/cs681/2007fa/Handouts/scorpion.pdf
谢谢帮忙！
-
问题内容： 我正在尝试编写一种算法，用于在给定的子矩阵中查找子矩阵。为了解决这个问题，我编写了以下代码： 这段代码可以正常工作，但是我不确定这是问题的确切解决方案还是可以解决。请提供您的专家意见。提前致谢。 问题答案： 该算法对4×4矩阵和2×2子矩阵进行了硬编码。否则，它看起来像蛮力算法。 我会这样表示： 如果您想要更有效的方法，建议您将它们压扁，如下所示： 并在此序列中搜索以下模式： 使用标准
-
实现图的最简单的方法之一是使用二维矩阵。在该矩阵实现中，每个行和列表示图中的顶点。存储在行 v 和列 w 的交叉点处的单元中的值表示是否存在从顶点 v 到顶点 w 的边。 当两个顶点通过边连接时，我们说它们是相邻的。 Figure 3 展示了 Figure 2 中的图的邻接矩阵。单元格中的值表示从顶点 v 到顶点 w 的边的权重。 Figure 3 邻接矩阵的优点是简单，对于小图，很容易看到哪些节
-
作为一项练习，我必须建立一个卫星导航系统，规划从一个位置到另一个位置的最短和最快路线。它必须尽可能快，而不需要使用太多内存。 我很难决定使用哪种结构来表示图形。我知道矩阵更适合密集图，列表更适合稀疏图。我更倾向于使用列表，因为我认为添加顶点将是这个程序中最累人的部分。 我只是想听听你们的意见。如果我把一个典型的路线图看作一个图形，其中不同的位置是节点，道路是边缘。你认为它是稀疏的还是密集的？在这种
-
B）设是带有向图（无环多边）的一个邻接矩阵，其中是边到的一个权重。如果没有这样的边并且对于evrey我们有。矩阵。槽表示什么？最小权重？还是...？ 知道吗？ 编辑：我的意思是这些算法在图中找到哪一个？找到最大重量？最小重量？什么也没找到？
-
问题内容： 我对图和邻接矩阵感到困惑。我正在为 一个班级做作业，我有一个节点的文本文件和一个边的文本文件，我必须 阅读它们的每一个并将它们制成一个图，然后可以在该图上执行 操作，例如确定图是否为连接，找到最小的 生成树，遍历并找到路径。但是我之前从未使用过图形 ，并且整个过程让我很困惑，我想知道 是否有人可以帮助我解释其中的一些内容。 首先，我是否要自己建立一个图（也许有节点和边类？） ，然后从中
-
我试图实现一个无向未加权图的邻接矩阵上的BFS，它返回访问的节点数。到目前为止，我已经提出了这个，但我认为这是不对的，因为当我打印出top/vised节点时，我得到了一些节点的多次出现，而且它没有排序。我在某个地方读到过，BFS是一个拓扑排序，我得到的顺序不是排序的。