问题标签 [undirected-graph]

我正在解决尝试基于直边分割图像以尝试获得闭合四边形的问题。我已经能够使用边缘检测器提取线段。

有没有一种很好的方法来连接如果扩展将“几乎重合”的边缘，以便最终创建可以分割图像的封闭区域。

谁能检查我的代码并告诉我这里缺少哪个测试用例。在hackerearth 上只有60 /100。我在这里使用父变量来跟踪被认为是循环的单个边缘。

我想使用 Floyd-warshall 算法找到加权无向图的任意两个顶点之间的最大距离。为此，我做了一些更改：

1. 我添加负权重而不是正数。

2. 然后我找出最短路径。

但它没有给我正确的输出。有人可以指出我正在犯的错误。

相同的输入是：-

1[测试用例数]

5 4 [节点数，边数]

1 2 4 [第一个节点，第二个节点，权重]

3 2 3 [第一个节点，第二个节点，权重]

2 5 2 [第一个节点，第二个节点，权重]

4 1 1 [第一个节点，第二个节点，权重]

如果我有一个无向图，G = (V, E)并且我想找到其中的所有顶点至少与 中的其他顶点有连接的S顶点子集。最好的方法是什么？GSnS

城市通过电话线连接并进行通信。我想摧毁所有的城市，但又不想过早地惊动另一个城市，所以我在摧毁城镇之前断开了电线。我不想断开用作两个城市之间桥梁的城镇。

如果我没记错的话，它是无向图。但我不明白如何检查我可以删除哪些城市，哪些不能。我查看了 Tarjan 的算法，但我不明白。

这是测试输入：

输出可以是这样的：

问题正如标题所暗示的那样，图表以邻接表形式给出。我的方法是在任何一个顶点中调用 DFS，每当我在 DFS 递归步骤中遇到访问的顶点时，我都会从 0 开始递增全局变量的计数器，并且不为该访问的顶点调用 DFS（就像我们通常所做的那样）。这行得通吗，我想对了吗？我也没有在互联网上找到任何相关文章来了解#Number of Cycles in undirected graph。

阐述：我的意思是使用简单的 DFS 方法。虽然我们在遇到访问顶点的递归步骤中什么都不做，但我增加了counter这种情况下的全局变量值。我这样做是因为每当我遇到访问过的顶点时，都意味着我正在完成一个循环。我声称：在任何 DFS 运行中，图中的每个循环都只会遇到一次（至少和最多一次）。我的说法正确吗？

编辑：没有后边缘

我编写的以下 C# 算法在 O(n) 时间内检测到无向图中是否存在循环。它避免了递归，并通过字典和哈希集利用散列。但是有没有办法让我做得更好？

好吧，我得到了一个看起来像这样的无向图。

每个块代表一个天线（在无线电话网络中），黑线将事物分成不同的区域。
我们有一些事实，例如：

第一个参数是地区的名称，第二个是一个特定号码，将分配给他们所在地区的每个人（当​​前地区每个电话的前 4 个号码），第三个是包含所有地区的列表属于当前区域（电话中的下一个号码，在破折号之间）。

我的练习说，对同一区域的每次调用都是免费的，如果需要通过一个区域是 1，如果是两个区域之外是 2，等等。

我被分配创建 can_call/4 函数，该函数可以查找两个人之间特定通话的路线和费用。
例如

我创建了一个 connect/2 函数，它告诉我是否连接了 2 个块，但我真的无法考虑成本。
有什么建议吗？

我有一个有向图，其中代理从节点 1 移动到节点 2，如下所示

我想将此有向图更改为无向图，对边之间的流量求和，呈现如下结果

我尝试根据边缘创建个人 ID，但没有成功。

关于如何做的任何想法？

我正在使用 as.undirected 将有向图转换为无向图。但是，属性组合存在问题，特别是在第一行和第一列中。

这是有向图（网络）的样子：

net <- graph.data.frame(edges, nodes,directed=T) as.matrix(get.adjacency(net, attr = "weight"))

矩阵

然后...

netSym <- as.undirected(net, "collapse", edge.attr.comb="sum") as.matrix(get.adjacency(netSym, attr = "weight"))

组合属性的矩阵，以及莫名其妙的错误

基本上，一切都是正确的，除了OL和OM的组合。它应该是 10 而不是 11。

有没有人遇到过同样的问题？有人知道解决办法吗？

谢谢！