Работа с неориентированным графом - C#
Формулировка задачи:
Есть неориентированный граф 4х4, нужно составить алгоритм, который бы находил пути в которых принимают участие все элементы графа. Граф представлен в виде матрицы смежности.
Например есть массив 4Х4
0 1 1 0
1 0 1 1
1 1 0 1
0 1 1 0
То есть каждый элемент графа имеет прямую связь с другим, кроме первого и четвертого. И программа должна вывести пути, в которых принимают участие все элементы графа, следовательно для этого массива программа выведет
1, 2, 3, 4
1, 3, 2, 4
2, 1, 3, 4
3, 1, 2, 4
Программа не должна работать только с этой матрицей смежности.
Решение задачи: «Работа с неориентированным графом»
textual
Листинг программы
private static void Main() { int[,] matrix = { { 0, 1, 1, 0 }, { 1, 0, 1, 1 }, { 1, 1, 0, 1 }, { 0, 1, 1, 0 } }; int[] indexes = Enumerable.Range(0, matrix.GetLength(0)).ToArray(); do { var valid = true; for (var i = 1; i < indexes.Length; i++) if (matrix[indexes[i - 1], indexes[i]] == 0) { valid = false; break; } if (valid) Console.WriteLine(string.Join(" ", indexes.Select(x => x + 1))); } while (Generate(indexes)); } private static bool Generate(IList<int> array) { int j = array.Count - 2; while (j != -1 && array[j] >= array[j + 1]) j--; if (j == -1) return false; int k = array.Count - 1; while (array[j] >= array[k]) k--; Swap(array, j, k); int l = j + 1, r = array.Count - 1; while (l < r) Swap(array, l++, r--); return true; } private static void Swap(IList<int> array, int i, int j) { int temp = array[i]; array[i] = array[j]; array[j] = temp; }
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д