Форум программистов, компьютерный форум, киберфорум
C# для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.68/47: Рейтинг темы: голосов - 47, средняя оценка - 4.68
0 / 0 / 0
Регистрация: 25.10.2017
Сообщений: 10

Из списка смежности в матрицу смежности. Выполнить обход графа глубину

26.02.2018, 16:38. Показов 9413. Ответов 1
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Помогите пожалуйста с программой:
Дан список смежности. Преобразовать в матрицу смежности. Выполнить обход графа в глубину.
Заранее спасибо.
0
Programming
Эксперт
39485 / 9562 / 3019
Регистрация: 12.04.2006
Сообщений: 41,671
Блог
26.02.2018, 16:38
Ответы с готовыми решениями:

Вывести матрицу смежности и список смежности графа
Всем привет!! Уважаемые форумчане, помогите плиз с заданием! Я написала код в Си по которому вводим матрицу инцидентности и выводим...

Преобразование списка смежности в матрицу смежности
Помогите пожалуйста, нужно разработать алгоритм преобразования списка смежности в матрицу смежности, для неорентированного графа. И все...

Матрица смежности графа - поиск в глубину
Здравствуйте дорогие форумчане. У меня тут небольшая ошибка. Никак не могу понять что к чему. Объясните пожалуйста. #include...

1
134 / 130 / 107
Регистрация: 17.03.2009
Сообщений: 364
28.02.2018, 17:02
Вот программа, она работает. На всякий рефакторинг времени не было.

Теоретический материал доступен здесь:
http://shpargalum.ru/shpora-go... ubinu.html


Код:

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
 
namespace ConsoleApplication1
{
 
 
    public class Program
    {
 
        /// <summary>
        /// Преобразует списко смежности в матрицу смежности
        /// </summary>
        /// <param name="list"></param>
        /// <returns></returns>
        public static int[,] AjancenyListToMatr(int[][]list)
        {
            var length = 0;
            foreach(var item in list) {
                length++;
            };
            var result = new int[length, length];
            var i = -1;
            foreach (var row in list)
            {
                i++;
                foreach (var j in row)
                {
                    result[i, j] = result[j, i] = 1;
 
                }
            };
 
 
            return result;
        }
 
 
        /// <summary>
        /// Осуществляет поиск в глубину
        /// </summary>
        /// <param name="index"></param>
        /// <param name="_matr"></param>
        /// <returns></returns>
        public static HashSet<int> SearchInDepth(int index, int[,] _matr)
        {
            var list = new HashSet<int>();
            list.Add(index);
            for (int j = 0; j < _matr.GetLength(1); j++)
            {
                if (_matr[index, j] == 1)
                {
                    _matr[index, j] = _matr[j, index] = 0;
                    list.UnionWith(SearchInDepth(j, _matr));
 
                }
            }
            return list;
        }
 
        public static void Main(string[] args)
        {
            //Задаем граф в виде списка смежности
            int[][] adjacencyList = new int[][]
            {
               new int[] {1, 1, 1, 1},
               new int[] {0, 4},
               new int[] {0, 3},
               new int[] {0, 2},
               new int[] {0, 1}
            };
 
            
            //Печать списка смежности
            PrintAdjacencyList(adjacencyList);
            
            //Преобразуем список смежности в матрицу смежности
            var matr = AjancenyListToMatr(adjacencyList);
 
            PrintMatr(matr); //Печать матрицы смежности 
 
            //Осуществляем поиск в глубину
            var result = SearchInDepth(1, matr);
 
           
            
            //Печать списка прохождения вершин
            PrintSearchInDepthResult(result);
 
            Console.ReadKey();
        }
 
        private static void PrintAdjacencyList(int[][] adjacencyList)
        {
            var i = 0;
            foreach (var row in adjacencyList)
            {
                Console.Write(i + " ");
                foreach (var j in row)
                {
                    Console.Write(j + " ");
                }
                Console.WriteLine();
                i++;
            };
        }
 
        private static void PrintSearchInDepthResult(HashSet<int> result)
        {
            Console.WriteLine();
            Console.WriteLine();
            Console.WriteLine(String.Join(" ", result));
        }
 
        private static void PrintMatr(int[,] matr)
        {
            for (var i = 0; i < matr.GetLength(0); i++)
            {
                Console.WriteLine();
                for (var j = 0; j < matr.GetLength(1); j++)
                {
                    Console.Write(matr[i, j] + " ");
                }
            }
 
        }
    }
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
28.02.2018, 17:02
Помогаю со студенческими работами здесь

Список смежности и обход графа в ширину
нужно создать список смежности и пройти граф в ширину. как с помощью struct{}; создать список смежности? список смежности: 0: 5 ...

Поиск в глубину. DFC (для списка смежности)
Напишите пожалуйста код на паскале - Поиск в глубину используя списки смежности (да,да не матрица смежности) и также с метками.

Матрица смежности некоторого графа. Сделать обход в длину и вывести результат обхода по возрастанию
Задание: дана матрица смежности некоторого графа. Сделать обход в длину и вывести результат обхода по возрастанию. Было у меня два...

Сгенерировать матрицу смежности полного графа
1. Сгенерировать матрицу смежности полного графа (количество вершин n = 3) и найти минимальный гамильтонова цикла методом полного перебора....

Составить матрицу смежности для графа


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Новые блоги и статьи
Загрузка PNG с альфа-каналом на SDL3 для Android: с помощью SDL3_image
8Observer8 27.01.2026
Содержание блога SDL3_image - это библиотека для загрузки и работы с изображениями. Эта пошаговая инструкция покажет, как загрузить и вывести на экран смартфона картинку с альфа-каналом, то есть с. . .
влияние грибов на сукцессию
anaschu 26.01.2026
Бифуркационные изменения массы гриба происходят тогда, когда мы уменьшаем массу компоста в 10 раз, а скорость прироста биомассы уменьшаем в три раза. Скорость прироста биомассы может уменьшаться за. . .
Воспроизведение звукового файла с помощью SDL3_mixer при касании экрана Android
8Observer8 26.01.2026
Содержание блога SDL3_mixer - это библиотека я для воспроизведения аудио. В отличие от инструкции по добавлению текста код по проигрыванию звука уже содержится в шаблоне примера. Нужно только. . .
Установка Android SDK, NDK, JDK, CMake и т.д.
8Observer8 25.01.2026
Содержание блога Перейдите по ссылке: https:/ / developer. android. com/ studio и в самом низу страницы кликните по архиву "commandlinetools-win-xxxxxx_latest. zip" Извлеките архив и вы увидите. . .
Вывод текста со шрифтом TTF на Android с помощью библиотеки SDL3_ttf
8Observer8 25.01.2026
Содержание блога Если у вас не установлены Android SDK, NDK, JDK, и т. д. то сделайте это по следующей инструкции: Установка Android SDK, NDK, JDK, CMake и т. д. Сборка примера Скачайте. . .
Использование SDL3-callbacks вместо функции main() на Android, Desktop и WebAssembly
8Observer8 24.01.2026
Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .
моя боль
iceja 24.01.2026
Выложила интерполяцию кубическими сплайнами www. iceja. net REST сервисы временно не работают, только через Web. Написала за 56 рабочих часов этот сайт с нуля. При помощи perplexity. ai PRO , при. . .
Модель сукцессии микоризы
anaschu 24.01.2026
Решили писать научную статью с неким РОманом
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru