Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Rox11vi
#1

Алгоритм с перекраской двуцветных подграфов - C++

19.04.2011, 23:27. Просмотров 381. Ответов 0
Метки нет (Все метки)

Здравствуйте! Помогите пожалуйста реализовать алгоритм на си++, точнее мне нужна программа раскраски вершин графа. Она должна выводить число шагов, количество цветов и время. Есть псевдокод алгоритма:

Вход: Граф G с ПН – упорядоченными вершинами.
Выход: Субоптимальная раскраска вершин.

начало
j∶=1;
для i от 1 до n шаг 1 цикл
начало
m:= наименьший номер цвета, отсутствующего на вершинах, смежных с вершиной υ_i;
если m<=j то
окрасить вершину v_i в цвет c_m;
иначе начало
К:= множество цветов, представленных ровно один раз на вершинах, смежных с вершиной v_i;
Если найдется пара α,β∈K, такая, что верши¬ны v_α и v_β, смежные с v_i, и окрашенные в цвета α и β, не соединены двуцветной цепью то
начало
перекрасить ту компоненту двуцветного графа G_αβ, которая содержит вершину v_α;
окрасить вершину v_i в цвет α;
конец
иначе начало
j≔j+1;
окрасить вершину v_i в цвет c_j;
конец
конец
конец цикла;
конец
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
19.04.2011, 23:27
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Алгоритм с перекраской двуцветных подграфов (C++):

Нужен алгоритм поиска пути в этом лабиринте (будь то волновой алгоритм или алгоритм правой/левой руки ) - C++
#include &quot;stdafx.h&quot; #include &lt;iostream&gt; #include &lt;conio.h&gt; using namespace std; void lab () { int s1 = 0; int s2 =...

Волновой алгоритм поиска (Алгоритм A* / Алгоритм А стар) - C++
Хочу разработать алгоритм для решения головоломки с подвижными дисками (перестановочная головоломка). Определение. Перестано́вочные...

Число подграфов - Дискретная математика
Здравствуйте. Как найти число подграфов в полном графе с n вершинами ? Спасибо.

Поиск элементарных подграфов - Алгоритмы
Всем привет! Сразу оговорюсь, возможно я не совсем корректно обозвал тему, просто потому что не знаю, как правильно назвать такие подграфы....

Найдите количество остовных подграфов - Дискретная математика
Найдите количество остовных подграфов, являющихся деревьями, в полных подграфах с 3-мя, 4-мя, 5-ю, 6-ю вершинами. Остовный подграф —...

Линейный алгоритм, Алгоритм с ветвлениями, Циклический алгоритм Линейный алгоритм - Pascal
Линейный алгоритм, Алгоритм с ветвлениями, Циклический алгоритм Линейный алгоритм 1. Объясни, что будет напечатано программой Program...

0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
19.04.2011, 23:27
Привет! Вот еще темы с ответами:

Построить алгоритм Маркова, который ищет НОД (Алгоритм Евклида) - Алгоритмы
Здравствуйте, ребята, выручайте. Весь инет перерыл, всю голову сломал, но не могу сделать. Суть в чем, надо построить алгорифм Маркова,...

Построить алгоритм ДО и алгоритм ПОКА для вычислений значения функции на отрезке [a,b] с шагом h. - Free Pascal
Построить алгоритм ДО и алгоритм ПОКА для вычислений значения функции на отрезке с шагом h. Написать программу: F=3+tgx Мой...

Построить алгоритм ДО и алгоритм ПОКА дя вычислений значения функции на отрезке [а,b] с шагом h. Написать программу - Pascal
F=3+tg x

Составить алгоритм-вычисление квадрата суммы двух чисел и алгоритм для вычисления функции - Pascal ABC
Здравствуйте!Мне нужно все с самого начала и точно,помогите пожалуйста! 1.составить алгоритм-вычисление квадрата суммы двух чисел.


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

Или воспользуйтесь поиском по форуму:
1
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru