标签: graph-theory

I\xe2\x80\x99m 正在解决一个问题，我有一个nxn矩阵，我需要确定覆盖矩阵中所有零的最小行数（水平和垂直）。本质上，我想找到一种分配这些线路的最佳方法，以最大限度地减少总覆盖范围。

这是一个例子：

(0, 1, 0, 1, 1)\n(1, 1, 0, 1, 1)\n(1, 0, 0, 0, 1)\n(1, 1, 0, 1, 1)\n(1, 0, 0, 1, 0)\n

解决方案必须是：

(x, x, x, x, x)\n(1, 1, x, 1, 1)\n(x, x, x, x, x)\n(1, 1, x, 1, 1)\n(x, x, x, x, x)\n

在这种情况下，最小行数为 4。

有什么算法可以解决吗？

我尝试创建一个二维数组，在其中我可以看到一行中的零之和并且可以。

上面示例的数组：

{ \n  [0, 1, 2, 5, 1, 1]\n  [2, 0, 0, 0, 0, 0]\n  [1, 0, 0, 0, …

在图论中,最小距离(Dijkstra算法找到的)和最小路径(我不确定它是什么)之间的区别是什么？

给定n个节点在坐标平面上互连的图形,找到包含m个节点的最小距离子树的最佳方法是什么？

我发现这个问题的唯一解决方案是生成连接的所有节点组合,并尝试通过Kruskal或Prim的算法连接这些节点,而忽略其余的,然后比较所有创建的树并找到最小的树,但这当涉及到更大的树木时,效率并不高.

有更快,更有效的算法/方法吗？

我有一个带有图形的程序,其节点代表一些进程,并且进程计算时间是节点的成本.该图形作为节点列表在内存中维护,每个节点都有一个父节点和子节点列表,以及它的执行时间.

我必须找到具有最短执行时间的路径.

• 每个节点可以与任何其他节点连接.
• 只有一个起始节点和一个终端节点.
• 一个节点可以有各种"父"和"子"

有人能告诉我最好的方法吗？

用语言,有人可以发布在简单图中找到"最大"独立集的方向吗？

我从ETH网站上读到了一些东西,它说可以在O(n)中找到这样的东西,只需选择一个随机顶点v,然后扫描其余的并试图找出是否有从v到其余部分的边缘.

谢谢

我有一个非常非常大的图,我想找到从一个顶点到另一个顶点的最短路径.该图是有针对性的,未加权的.

我考虑过使用Dijkstra算法的一些修改,但我通常将它用于加权无向图.

所以我的另一个想法是使用DFS,因为我可以将所有权重视为一个.

有什么建议？一个

编辑:好的,我想说BFS,对不起.

我正在尝试用RaphaelJS绘制图论样式图。例如：

尽管在RaphaelJS中创建圆/节点很容易，但是我还没有弄清楚如何将每个节点与标签关联（并在每个节点内包含标签）。

RaphaelJS可行吗？

有一个题为" Facebook图搜索如何工作？ " 的封闭式问题.

简单来说,OP问(甚至给出了他试过的样本):

Facebook Graph Search如何运作？他举了一个例子:Friends from France who likes England

如何将上述实现为现实世界的信息检索问题？

由于我的回答不符合评论,所以想到重新构思问题并在Stack Overflow Q&A风格中回答它.

给定具有正权重的无向图,有两种边:锁定边和未锁定边.确定给定边缘是锁定边缘还是解锁边缘需要O(1).

1. 对于给定的两个顶点s,t和正数k = O(1),如何找到s和t之间最短路径,其中包含最多 k个锁定边缘？

2. 对于给定的两个顶点s,t和一个正数k = O(1),如何找到包含正好k个锁定边的s和t之间的最短路径？

我不知道我怎么能在这个图运行Dijkstra算法找出给定顶点之间的最短路径,以及如何改造无向图,为指导之一.

给定一个偶数个单元格的网格,其中网格边缘上的两个单元格缺失,我想形成成对的相邻单元格,使得没有合作伙伴没有剩余单元格(不计算"缺失"单元格) .

根据放置两个"缺失"单元的位置,我相信它总是可能或总是不可能做出这样的安排.我在这里画了两个例子,左边的绘图是成功的尝试,右边的绘图是不成功的尝试(两个单元格没有合作伙伴).为摇摇欲坠的相机手道歉.

单元格内的箭头表示该单元与哪个邻居合作.

我有两个问题:

1. 我怎么知道放置"缺失"细胞的安全位置,而不是让每个细胞都成为伴侣？

2. 在给定上面提到的条件的情况下,创建这样的排列的算法会是什么样的,并且还假设单元格表可以更大(尽管总是具有偶数个单元格)并且不一定是正方形(但是矩形)？示例可以是3x4网格或6x6网格.

我还不知道如何知道放置"缺失"单元的安全位置,但只要它们处于已知安全的位置,我的算法如下:

1. For each cell that isn't "missing" or already paired, iterating from top-left to bottom right, horizontally first:
2. Choose a random neighbor to form a pair with: either right or bottom.
3. Check all the cells to see if there are any cells that cannot make a pair, if so:
4. Undo the last pair, go back to 2 and choose the other neighbor.

我完全不知道图论或其他什么可以帮助我找到一个好的解决方案,所以我非常感谢你能给予的任何帮助.任何非超级晦涩的语言中的伪代码或真实代码都会很棒,简单的文本解释也是如此.