在长度< = k的有向图中找到所有循环

本文介绍了在长度< = k的有向图中找到所有循环的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

是否可以在

Finding all cycles in undirected graphs

将边视为有向边，并且仅将长度为< = k的循环视为？

to consider edges as directed and only cycles of length <= k ?

推荐答案

我自己回答

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; } }