graph-theory

2热度

1回答

我试图实现社交网络追随者图。要求是这样的，为了简单起见，我们可以假设图中每个用户u的概况由一个正整数值P [u]表示。我被要求提供约会服务。目标是为每个用户生成一个好的约会合作伙伴。如果可以通过一系列跟随你的人（如果有的话）完全相同的人来访问这个人，那么合作伙伴是很好的。这是一个图遍历问题，我可以自己实现，但这里的问题是我不确定在这种情况下使用DFS或BFS是否更好？

1热度

1回答

卡住DFS/BFS任务（USACO银）

这里有竞争力的编程noob。我一直在试图解决这个问题： http://www.usaco.org/index.php?page=viewproblem2&cpid=646 我写的代码只与第一个测试用例一起工作，并给出了超出内存限制的错误 - 或（'！'）用于其余的测试用例。这是我的代码（意外地混合起来，M和N）： #include <vector> #include <algorithm>

1热度

1回答

该图表中Prim算法的正确顶点顺序是什么？

我想知道从这个图中的Prim算法的顶点顺序：我的回答是{a,c,b,e,f,g,d}，但也有人说{a,c,b,e,d,f,g}或{a,c,d,e,b,f,g}。哪个答案正确？

3热度

2回答

从字符串对查找未知排列

假设我有一堆字符串对，表示“before”和“after”值。为了给出一个简单的例子： aaaabbbb -> aabbbbaa abbbbbbb -> bbbbbbab aaabbbaa -> abbbaaaa cccccccc -> cccccccc 如何将确定一个可能的排列可以是[6,7，0，1，2，3，4，5]，或者换句话说，所有的字符都是向左旋转两个空格？有没有关于这个问题的

0热度

1回答

如何在Sage中绘制自己的图表？

如何在Sage中绘制我自己的图形：我想要一个带$ 4 $顶点的图表，比如$ 1,2,3,4 $。我想要一个介于$ 1,2 $和$ 3,4 $之间的边缘。我写在SageMath以下： $ H = \文本{格拉夫}（\ {{1：[2]，3：[4]} \}）$ $ \文本{}阴谋（H）$ 但我失败了它的说法回溯错误：我应该怎么做请帮

0热度

2回答

查找诱发周期的所有边的高效算法

如果添加到图中，找到所有边的最快方式是什么？将在有向非循环图中引发周期？正式：假设你有一个DAG $ G =（V，E）$，边集为$ E \ subset V \ times V $。在V \ times V-E $中查找所有$ e \，使得$ G（e）=（V，E \ cup {e}）$至少有一个循环。蛮力方法是使用DFS来检查$ G（e）$是否具有在V \ times V-E $中的所有$ e

0热度

1回答

边缘权重加倍的最短路径每个其他跳

我该如何最优地解决一个图论问题，其中边缘权重每隔一个甚至第三跳变化？我仍然可以使用某种改进的Dijkstra算法吗？

0热度

2回答

图的O（m + n）时间算法

我刚刚开始学习关于图的知识，似乎无法为此问题想出一个算法，甚至不知道从哪里开始。我将衷心感谢您的帮助！对于给定的连通图G =（V，E），设计O（n + m）时间算法以找到节点v∈V，因此移除v及其所有相邻边将不会断开连接G. 预先感谢您！

0热度

1回答

试图在图中查找组件时出现运行时错误

我正在尝试在Hackerrank中解决这个graph problem，这是迄今为止我所知道的。我正在使用Python字典来表示图形，并让我的DFS函数返回它所遍历的连接组件的长度。我的代码通过了第一个测试用例，但给我一些其他测试用例的运行时错误。这是一个优化问题吗？如果是这样，我应该尝试优化哪部分代码？或者我应该尝试完全不同的方法？ import sys n = input() # Graph

1热度

1回答

在无向图中查找非相交2周期的最大数量

我有一个adjecency矩阵和一个adjecency列表（我可以使用）都表示一个图。基本上，我该如何在图中配对连接的顶点，以便剩下最不成对的（和断开的）顶点？我已经尝试过这种蛮力策略： def max_pairs(adj_matrix): if len(adj_matrix) % 2: # If there are an odd amount of vertices,