Работа с неориентированным графом

@HomBro · Регистрация: 14.12.2015

Студворк — интернет-сервис помощи студентам

Есть неориентированный граф 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
Программа не должна работать только с этой матрицей смежности.

@I2um1 · 12.12.2016, 21:05

Название: graf.png
Просмотров: 27

Размер: 8.8 Кб

Где например 1, 2, 4, 3?

Не по теме:

Кривоват немного граф, да~

@HomBro · 12.12.2016, 21:22 **[ТС]**

Ну забыл, главное чтобы прога не забыла

@I2um1 · 12.12.2016, 23:28

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
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;
}

@HomBro · 13.12.2016, 07:08 **[ТС]**

От души, спас просто

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий 8Observer8 02.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11680&d=1772460536 Одним из. . .	Реалии Hrethgir 01.03.2026 Нет, я не закончил до сих пор симулятор. Эта задача сложнее. Не получилось уйти в плавсостав, но оно и к лучшему, возможно. Точнее получалось - но сварщиком в палубную команду, а это значит, в моём. . .	Ритм жизни kumehtar 27.02.2026 Иногда приходится жить в ритме, где дел становится всё больше, а вовлечения в происходящее — всё меньше. Плотный график не даёт вниманию закрепиться ни на одном событии. Утро начинается с быстрых,. . .	SDL3 для Web (WebAssembly): Сборка библиотек: SDL3, Box2D, FreeType, SDL3_ttf, SDL3_mixer и SDL3_image из исходников с помощью CMake и Emscripten 8Observer8 27.02.2026 Недавно вышла версия 3. 4. 2 библиотеки SDL3. На странице официальной релиза доступны исходники, готовые DLL (для x86, x64, arm64), а также библиотеки для разработки под Android, MinGW и Visual Studio. . . .
SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .	Конвертировать закладки radiotray-ng в m3u-плейлист damix 19.02.2026 Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .	Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI Eddy_Em 18.02.2026 Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .

@HomBro 1 / 1 / 1 Регистрация: 14.12.2015 Сообщений: 128

	Работа с неориентированным графом 12.12.2016, 20:34. Показов 1637. Ответов 4 Метки нет (Все метки) Есть неориентированный граф 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 Программа не должна работать только с этой матрицей смежности. 0

@I2um1 Злой няш 2136 / 1505 / 565 Регистрация: 05.04.2010 Сообщений: 2,881
	12.12.2016, 21:05
	Где например 1, 2, 4, 3? Не по теме: Кривоват немного граф, да~ 0

@HomBro 1 / 1 / 1 Регистрация: 14.12.2015 Сообщений: 128
	12.12.2016, 21:22 [ТС]
	Ну забыл, главное чтобы прога не забыла 0

@HomBro 1 / 1 / 1 Регистрация: 14.12.2015 Сообщений: 128
	13.12.2016, 07:08 [ТС]
	От души, спас просто 0

Работа с неориентированным графом

Решение