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

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

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

Author24 — интернет-сервис помощи студентам
Помогите пожалуйста с программой:
Дан список смежности. Преобразовать в матрицу смежности. Выполнить обход графа в глубину.
Заранее спасибо.
0
26.02.2018, 16:38
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 2
Вот программа, она работает. На всякий рефакторинг времени не было.

Теоретический материал доступен здесь:
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
Ответ Создать тему

Редактор формул (кликните на картинку в правом углу, чтобы закрыть)
Новые блоги и статьи
Git не работает на MacOS после апдейта
hw_wired 13.02.2025
После очередного обновления MacOS многие разработчики сталкиваются с неприятным сюрпризом - Git перестает работать и выдает ошибку "xcrun: error: invalid active developer path". Эта проблема особенно. . .
Git отказывается объединять несвязанные истории
hw_wired 13.02.2025
Git работает безупречно, пока мы не сталкиваемся с особыми ситуациями вроде объединения веток с разными корнями истории. В таких случаях система контроля версий может преподнести неприятный сюрприз в. . .
Проверка email с помощью JavaScript
hw_wired 13.02.2025
Email-адреса имеют довольно запутанную спецификацию, которая допускает множество неочевидных вариантов написания. Например, знали ли вы, что адрес вида "name+tag@domain. com" или даже. . .
Замена всех вхождений строки с помощью JavaScript
hw_wired 13.02.2025
JavaScript предлагает несколько способов для выполнения операций замены в строках, каждый из которых имеет свои особенности и область применения. От простейшей замены первого найденного вхождения до. . .
Отличия между ~ и ^ в package.json. Версии в Node.js
hw_wired 13.02.2025
Управление зависимостями в Node. js проектах - это настоящее исскуство, требующее глубокого понимания механизмов версионирования пакетов. В центре этого процесса находится файл package. json, который. . .
Циклы в Python
hw_wired 13.02.2025
Когда мы пишем программы на Python, часто возникает необходимость выполнить одни и те же действия множество раз. Представьте, что вам нужно обработать список из тысячи элементов или вывести на экран. . .
Присоединяйтесь к вызову «В память о Дилане Буччи»
Programma_Boinc 13.02.2025
Присоединяйтесь к вызову «В память о Дилане Буччи» 19 февраля, базирующаяся в Виннипеге, кибер - академия старшей школы Сислера начнет командный вызов, который продлится 19 дней. Опубликовано:. . .
Микросервис с нуля на Go с Kafka
stackOverflow 12.02.2025
Когда я впервые столкнулся с необходимостью разделить монолитное приложение на микросервисы, передо мной встал вопрос выбора правильных технологий и подходов. После долгих экспериментов с различными. . .
Микросервис с нуля на C# с RabbitMQ
stackOverflow 12.02.2025
Переход от монолитной архитектуры к микросервисной - это не просто модное веяние, а закономерный этап эволюции программных систем. В отличие от монолита, где все компоненты тесно связаны между собой. . .
Docker для начинающих
stackOverflow 12.02.2025
В современном мире разработки программного обеспечения все чаще возникает необходимость быстро и надежно разворачивать приложения в различных средах. Разработчики постоянно сталкиваются с проблемой. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru