标签: graph-algorithm

嗨，我需要帮助寻找图形算法

我正在研究与距离函数相关的以下方程

d (g1, g2)   = 1-       ?mcs(g1,g2) ?  /
             ?g1?+?g2?-?mcs (g1, g2) ?

在哪里

• d (g1,g2) : 是基于最大公共子图的距离函数。
• g1, g2 是两张图。
• mcs (g1,g2): 是两个图 g1,g2 的最大公共子图，其中 mcs 是两个主题图中包含的最大图（通过某种涉及节点和边数的度量）。
• ?g1?：共同诱导子图g1的基数
• ?g2?：共同诱导子图g2的基数

我的问题：如何计算 MCS？
我在互联网上搜索过，但大多数算法都很复杂，任何人都知道从哪里可以得到一个简单的算法来在 matlab 中编程这个方程。

我正在尝试生成一个无向图,其中每个节点都有一个与之关联的最大程度.也就是说,如果节点的最大度数为2,则它最多可以连接两个节点(允许连接节点,但不允许为0).我的问题是我正在尝试生成一个可以从一个节点到另一个节点的图形.目前,我可以让节点"随机"连接到另一个,但问题是它可以创建分割图,即如果你有10个节点,那么有时无意中有两个图形,每个节点形成5个节点.如果有人知道有效的解决方案,我很乐意听到它!

编辑:假设我有一个包含十个节点的图形,并且我指定了最大度数为2.在这种情况下,这是可取的:

虽然这是我想要避免的:

两个图的每个节点的最大度数为2,但在第二个图像中,不可能选择任意节点并且能够到达任何其他任意节点.

我很困惑，这两者之间有什么区别？

循环和电路，所以请尽可能通过图表确定。

我想到的是循环总是在无向图中电路总是有向图。如果我错了，请纠正我？

哪种算法可用于生成具有多个成功路径的迷宫，如果算法是某些知名算法的修改版本，则解释或添加链接。

我正在使用二维数组 A 来存储 maze 的配置。

假设如果迷宫的大小是 n * n 那么从 A[0][0] 到 A[n-1][n-1] 应该有不止一条路径。

在最坏的情况下,我们可以通过使用Kruskal算法找到O(E log*V)中的最小瓶颈生成树.这是因为每个最小生成树都是生成树的最小瓶颈.

但是我在这个课程中遇到了这个面试问题.

即使在最坏的情况下,我们如何才能在线性时间内找到最小的瓶颈生成树.请注意,我们可以假设在最坏的情况下我们可以计算线性时间内n个键的中位数.

我有一个带有彩色加权边的有向图.有2种颜色.每个边缘只能有1种颜色.我想找到颜色变化有限的最短路径.从一个顶点可以出现最多2个边缘,其中有2种不同的颜色,2个边缘有2种不同的颜色.

例如,在此图中:

最短路径最多3个颜色变化将是9 最大0颜色变化最短路径6+1+4=11等.

我的解决方案是递归访问所有可能的路径并交换,如果递归找到一个更好的,使这个问题呈指数级.

是否存在针对此问题的非指数解决方案？

给出二分图.每个顶点都有一些整数值 - 权重.

是否有可能在多项式时间内在此图中找到最大加权独立顶点集？

如果存在这样的解决方案,这个问题的算法是什么？

我非常确定A* 算法中的* （星号）意味着该算法是可接受的，即如果该路径存在（当采用的启发式是乐观的时），则保证它找到图中的最短路径。