问题标签 [undirected-graph]

我有一个无向图，每条边的权重为 1。该图可能有循环。我需要在图中找到最长的路径（每个节点出现一次）。路径的长度是节点的数量。任何简单/有效的解决方案？谢谢！

给定一个无向图，我怎样才能找到所有的桥？我只发现 Tarjan 的算法似乎相当复杂。

似乎应该有多个线性时间解决方案，但我找不到任何东西。

我想在仅使用 BFS（不是 DFS）的无向图中找到第一个循环。所有来源都使用 DFS 解决了这个问题，但我必须使用 BFS 找到它。我怎样才能找到它？提前致谢！

我有一个List< List< int> > graph; 我用它来表示一个无向图。当我添加新边缘graph[u].Add[v];时，我无法迭代特定的边缘graph[u]。

我有一个数据框，其中包含在许多数据集中找到的元素对。对的顺序无关紧要，它们按字母顺序给出一次，但是第一个实例可能在数据库之间有所不同，如示例中所示。

我想为它们生成一个分数，以显示每个数据库中包含相同对的实例的比率。

我可以想象这样一个粗略的功能：

我希望从示例数据集（顺序不重要）中得到的结果是：

我可以看到这个粗略的循环系统是如何工作的，但我很确定有一个更优雅的解决方案，有人能帮忙吗？也许在图形库中有一个特定的功能。谢谢！

我有一个无向图结构的边缘列表。

我想从此数据集中检索闭合电路列表。有没有一种方法library(igraph)可以让你轻松做到这一点？

可以用相同方法解决的额外问题：顺便说一句，我意识到我一直想要从数据中只是将非常强连接的无向图中的元素聚类。也许闭路方法也可以解决在无向图中找到更多连接组的问题（可能超过任意阈值）。虽然是图论的新手，但这个关于图强度的维基百科页面有一些类似的东西。这个想法是根据互连结构在一组节点中找到自然组，组的数量完全取决于数据，一些节点可能属于纯单组。

我可以做一些预定义的方法或方法序列来获得它吗？谢谢！

是否可以将某个顶点的类型固定为boost::undirected_graph例如“int”？

'int' 顶点类型似乎是 的默认值boost::adjacency_list，并且以下代码有效：

boost::adjacency_list< boost::vecS, boost::vecS, boost::undirectedS> g; boost::add_edge(0 , 1 , g);

但因 undirected_graph 而失败。我应该做哪些额外的步骤来使用相同的语法将顶点添加到 undirected_graph？

我需要使用bron_kerbosch_all_cliques只接受 undirected_graph 作为输入的算法。

谢谢

给定两个带有加权边的完整图，我想分别在两个图上找到两个最小生成树（MST），条件是两个学习的 MST 在给定的边子集上具有公共边。请注意，这两个图具有相同数量的顶点，但边权重都不同。

例如，如果这两个图是具有顶点 {1,...,d} 的完整边加权图。我们要求两个学习的 MST 在具有顶点 {1,...,d/2} 的完整子图上具有相同的边。

我可以使用什么算法来查找此类 MST？我尝试使用 Kruskal 算法的修改，但无法使其工作。

我正在尝试优化图形遍历问题，但无法找出解决它的最佳方法。它看起来既不是 A* 搜索问题（因为我们想要最大化路径而不是最小化它），也不是旅行商问题（因为我们不必访问所有城市）。它的简化版本是这样的：

我们有一组节点和连接/边。连接是任意的，节点可以有一个或多个。连接也有与之关联的接口/类型，并且接口不能支持多个连接。因此，例如，如果 nodeA可以连接到节点B或C通过 interface alpha，并且我们决定将其连接到 node B，则 node 上的接口A不再支持其他连接，因此C无法再连接A。但是，如果节点碰巧具有相同的接口，我们可以将节点连接C到节点。Dalpha

我还应该提到，这些接口就像锁和钥匙一样工作，所以A可以连接到B或，C但不能相互连接（接口就像一面镜子）。此外，虽然不能再通过接口连接到任何东西，因为它被 使用，如果它碰巧有另一个接口（）并且其他东西可以连接到，那么我们可以将多个节点连接到。目标是获得最大的连接节点组（丢弃所有较小的组）。BCAalphaBbravobravoA

我正在考虑一些启发式方法：

• 更喜欢具有更多接口的节点（我已经丢弃了没有对的接口）
• 更喜欢更流行的界面

上述两个规则可用于优先尝试连接到下一个节点（现在我天真地将它们分组为一个等级 - 可连接节点的总数），但我的直觉告诉我我可以做得更好。此外，我认为这不会有利于最佳解决方案。

我试图弄清楚我是否可以以某种方式反转启发式以创建一个变体，A* Search使得 A*“乐观启发式成本”规则仍然适用（即启发式成本 = 丢弃的节点数，但是，这破坏了实际成本计算 -因为我们将从丢弃除一个节点之外的所有节点开始）。

我的另一个想法是计算从起始节点到每个节点的距离（中间节点的数量），并将其平均值用作启发式方法，目标是连接所有节点。但是，我不能保证所有节点都会连接。

编辑： 这是一个例子

• 虚线表示允许（但未激活/经过）的连接
• 接口不允许连接同名的接口，但可以连接自己的'版本
• 接口只能使用一次（如果我们连接A到Bvia α，我们将无法再连接A，C因为A不再有α可用的接口）
• 节点的数量是任意的（但在算法执行期间是恒定的），并且应该假设非常大
• 每个节点的接口数将至少为一个，如果它使问题更容易，我们可以假设一个上限 - 即 3
• 可能的连接数只是接口兼容性的函数，接口定义节点可以连接的内容，是否/如何使用该接口取决于您
• 激活连接的方向/顺序无关紧要
• 目标是生成最大的连接节点集（我们不关心使用的连接或接口的数量）

我目前正在研究一个计算魔方2x2和3x3魔方的神数和魔鬼算法的项目。我已经在 C 中使用我自己的结构类型成功地创建了图表，但希望像这样直观地表示：

现在的问题是2x2凯莱图有大约 350 万个节点和 1800 万条边，对于3x3. 如果有必要，我可以很容易地从我的程序中生成一个邻接矩阵，以便在外部包中使用。

CI中是否有可以使用的库？Matlab 可以为我创建这个吗？我该如何处理如此大量节点的图表？