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

Поиск компонент связности графа, не работает алгоритм

12.01.2017, 15:59. Показов 2559. Ответов 1
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Работаю с MFI представлением графа
Тест 1. ME = 2 5 1 3 4 5 4 2 3 2 5 1 2 4, MV = 0 2 6 8 11 14. p1 = 5, q1 = 7; В результате 0
Тест 2. ME = 2 4 1 3 5 7 2 5 6 7 1 2 3 6 8 3 5 8 2 3 5 6, MV = 0 2 6 10 11 15 18 20 22, p1 =8, q1 = 11; В результате 0.
Второй тест прорешивал вручную, компонент связности там точно не одна

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
static int p1, q1, p2, q2; //p - вершины, q - ребра
        static List<int> me1 = new List<int>();
        static List<int> mv1 = new List<int>();
        /*Для поиска в глубину*/
        static List<List<int>> g = new List<List<int>>();
        int n = p1;
        static List<bool> used = new List<bool>(p1);
 
        /*попытка поиска в глубину*/
        public void dfs(int v)
        {
            used[v] = true;
            for (int i = 0; i < g[v].Count; ++i)
            {
                int to = g[v][i];
                if (!used[to])
                    dfs(to);
            }
        }
 
        //поиск компонент связности
        public int find_comps()
        {
            int cnt = 0;
            for (int i = 0; i < n; ++i)
                if (!used[i])
                {
                    dfs(i);
                    ++cnt;
                }
            return cnt;
        }
 
        //ввод списков смежности из MFO
        void getMFO()
        {
            for (int i = 0; i < mv1.Count - 1; i++)
            {
                g.Add(new List<int>());
                for (int j = mv1[i]; j < mv1[i+1]; j++)
                {
                    g[i].Add(me1[j]);
                }
            }
        }
Добавлено через 9 минут
Прошу прощения, работа с MFO представлением.

Добавлено через 25 минут
Немного дописал, но все равно.. Функция dfs не вызывается, if не выполняется ни в какую, что бы я туда не прописывал Оо
C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
//поиск компонент связности
        public int find_comps()
        {
         for (int i = 0; i < n; ++i)
                used[i] = false;
            int cnt = 0;
            for (int i = 0; i < n; ++i)
                if (!used[i])
                {
                    dfs(i);
                    ++cnt;
                }
            return cnt;
        }
Добавлено через 22 минуты
Окей, проблема была в переменной n, она походу содержала null.
Но теперь во всех вариантах оно находит только одну компоненту связности
0
Programming
Эксперт
39485 / 9562 / 3019
Регистрация: 12.04.2006
Сообщений: 41,671
Блог
12.01.2017, 15:59
Ответы с готовыми решениями:

Посчитать количество компонент связности графа
Дан граф. Необходимо посчитать количество его компонент связности и вывести их. Добавлено через...

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

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

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

1
0 / 0 / 0
Регистрация: 18.10.2015
Сообщений: 38
13.01.2017, 18:55 2
Я на этой неделе готовился к экзаменну по дискретке, завтро пишу. Искал ответ на один из вопросов по графам, наткнулся на целый список задач и их решение на c++. попробуй поискать в ya.ru мож найдешь свой.
0
13.01.2017, 18:55
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
13.01.2017, 18:55
Помогаю со студенческими работами здесь

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

Подсчитать количество компонент связности графа
Всем привет, есть задача, которую я решил на с++, а надо на питоне, может кто-нибудь помочь...

Посчитать количество компонент связности графа
Дан неориентированный невзвешенный граф. Необходимо посчитать количество его компонент связности и...

Как найти компонент связности графа обходом в глубину?
Всем привет. Сижу уже несколько часов и не могу понять как найти ответ на указанный в заголовке...


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

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Новые блоги и статьи
Rust или Go? А может C++?
hw_wired 28.01.2025
С каждой новой технологией или методологией появляются новые языки программирования, призванные решать конкретные задачи либо улучшать аспекты производительности и безопасности. Среди множества. . .
Fortran и WinAPI: как создать приложение с графическим интерфейсом
hw_wired 28.01.2025
Fortran — это один из старейших высокоуровневых языков программирования, широко используемый в науке и инженерии уже несколько десятилетий. Его название происходит от "Formula Translation" (перевод. . .
Списки в Haskell
hw_wired 28.01.2025
Haskell является функциональным языком программирования, который отличается лаконичностью синтаксиса и мощными абстракциями. Важным концептом в Haskell являются списки — упорядоченные коллекции. . .
Функции высшего порядка в Haskell
hw_wired 28.01.2025
Haskell – это современный функциональный язык программирования, который получил широкое распространение благодаря своей выразительности и мощным абстракциям. Одной из ключевых особенностей Haskell. . .
Как в цикле обойти все поля объекта в JavaScript
bytestream 28.01.2025
Объекты в JavaScript представляют собой фундаментальные структуры данных, которые позволяют хранить и организовывать связанную информацию в виде пар ключ-значение. Каждый объект можно представить как. . .
Как выбрать строки в DataFrame по значению столбца в Pandas
bytestream 28.01.2025
В области анализа данных библиотека Pandas стала незаменимым инструментом для работы с табличными данными в Python. Эта мощная библиотека предоставляет множество функций для эффективной обработки и. . .
Как сделать перенос строки в Bash
bytestream 28.01.2025
При работе с командной оболочкой Bash разработчики часто сталкиваются с необходимостью форматирования текстового вывода, где ключевую роль играет правильное управление переносами строк. Умение. . .
Поиск подстроки в строке с помощью Bash
bytestream 28.01.2025
Поиск подстроки в строке является одной из важных задач в программировании и обработке текстов. Применение такого поиска можно найти в самых разных областях, от анализа данных до разработки. . .
[golang] 169. Majority Element
alhaos 28.01.2025
Тут надо вернуть "мажористый" элемент который встречается в слайсе больше чем в половине случаев. По условиям задачи во входных данных такой элемент обязан присутствовать. / / . . .
Когда лучше использовать LinkedList вместо ArrayList в Java
bytestream 28.01.2025
При разработке Java-приложений выбор правильной структуры данных играет ключевую роль в обеспечении эффективности и производительности программы. ArrayList и LinkedList являются двумя. . .
Какой ответ HTTP лучше использовать: 403 Forbidden или 401 Unauthorized, когда недостаточно прав
bytestream 28.01.2025
В современной веб-разработке правильная обработка ошибок и точное информирование клиентов о статусе их запросов играют критическую роль в создании надежных и безопасных приложений. Особое внимание. . .
Как получить список всех файлов коммита в Git
bytestream 28.01.2025
Система контроля версий Git представляет собой мощный инструмент для управления изменениями в программном коде и других файлах проекта. В основе работы Git лежит концепция коммитов - снимков. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru