Работа с неориентированным графом - 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;
}

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

7   голосов , оценка 3.571 из 5
Похожие ответы