1
A
回答
0
我自己回答
static void Main(string[] args)
{
int k = 4;
for (int i = 0; i < graph.GetLength(0); i++)
for (int j = 0; j < graph.GetLength(1); j++)
{
findNewCycles(new int[] { graph[i, j] },k);
}
foreach (int[] cy in cycles)
{
string s = "" + cy[0];
for (int i = 1; i < cy.Length; i++)
s += "," + cy[i];
Console.WriteLine(s);
}
}
static void findNewCycles(int[] path, int k)
{
int n = path[0];
int x;
int[] sub = new int[path.Length + 1];
if (path.Length < k + 1)
{
for (int i = 0; i < graph.GetLength(0); i++)
for (int y = 0; y <= 1; y = y + 2)
if (graph[i, y] == n)
// edge referes to our current node
{
x = graph[i, (y + 1) % 2];
if (!visited(x, path))
// neighbor node not on path yet
{
sub[0] = x;
Array.Copy(path, 0, sub, 1, path.Length);
// explore extended path
findNewCycles(sub,k);
}
else if ((path.Length > 2) && (x == path[path.Length - 1]))
// cycle found
{
int[] p = normalize(path);
int[] inv = invert(p);
if (isNew(p) && isNew(inv))
cycles.Add(p);
}
}
}
}
static bool equals(int[] a, int[] b)
{
bool ret = (a[0] == b[0]) && (a.Length == b.Length);
for (int i = 1; ret && (i < a.Length); i++)
if (a[i] != b[i])
{
ret = false;
}
return ret;
}
static int[] invert(int[] path)
{
int[] p = new int[path.Length];
for (int i = 0; i < path.Length; i++)
p[i] = path[path.Length - 1 - i];
return normalize(p);
}
// rotate cycle path such that it begins with the smallest node
static int[] normalize(int[] path)
{
int[] p = new int[path.Length];
int x = smallest(path);
int n;
Array.Copy(path, 0, p, 0, path.Length);
while (p[0] != x)
{
n = p[0];
Array.Copy(p, 1, p, 0, p.Length - 1);
p[p.Length - 1] = n;
}
return p;
}
static bool isNew(int[] path)
{
bool ret = true;
foreach (int[] p in cycles)
if (equals(p, path))
{
ret = false;
break;
}
return ret;
}
static int smallest(int[] path)
{
int min = path[0];
foreach (int p in path)
if (p < min)
min = p;
return min;
}
static bool visited(int n, int[] path)
{
bool ret = false;
foreach (int p in path)
if (p == n)
{
ret = true;
break;
}
return ret;
}
}
相关问题
- 1. 查找有向图中的所有周期
- 2. 查找长度为k的所有递减序列的列表?
- 3. 查找图实现中的所有周期
- 4. 无向图中最长的周期
- 5. 有K个状态的NFA接受字符串的长度<= k
- 6. Matlab的有向图最短周期
- 7. 从长度为k的数组获得n上的所有组
- 8. 查找有循环的有向图中的所有路径
- 9. 查找可变长度周期内的最大输出
- 10. 无向图中最短周期的长度
- 11. 在有向图中找到正长度的最短长度的循环
- 12. 使用JGrapht找到有向边权图中的负周期
- 13. 发现列表的所有K-长度子集在序言
- 14. 每个节点的DFS是否会给出有向图中的所有周期
- 15. 如何查找列名长度大于5的所有列?
- 16. 使用面积和周长查找长度和宽度
- 17. Paypal - 结算周期长度?
- 18. 如何在Perl中生成长度为k的所有有序组合?
- 19. 查找图表中的周期数(Python)
- 20. 长度为k
- 21. 使用DFS检测有向图中的周期?
- 22. 中所有Hamilton周期
- 23. 查找公钥的长度
- 24. 查找以K为因子的最小长度间隔
- 25. 如何查找有序字典中的所有元素,实现为具有密钥k的二叉树k
- 26. 查找n个k个元素的所有组合
- 27. 查找出现超过n/k次的所有元素
- 28. BFS? - 找到所有从s到t最多有一定长度的路径
- 29. 在长度为N的列表中生成长度为K的循环移位的所有置换
- 30. 在FlowChart图中查找所有方法?
为什么给变量有意义的名字,一个很好的例子是绝对必要的。 – BenjaminPaul 2013-03-05 20:24:14
是的,如果你可以提供一些上下文,它会有所帮助。我甚至不确定这是什么语言。而'图'是一个具有邻接矩阵的全局变量?如果你可以描述你在伪代码中做了什么,那会很棒。 – Quantum7 2013-06-18 04:39:02
上下文似乎是[来自链接帖子的这个答案](http://stackoverflow.com/a/14115627/298609)。它用C#编写,这是一个天真的实现。约翰逊给出了更好的算法。 – Paya 2017-03-28 18:42:48