Форум программистов, компьютерный форум CyberForum.ru

Помогите написать программу в С++. Найти наибольшую клику в заданном орграфе, используя алгоритм нахождения независимых множеств - C++

Восстановить пароль Регистрация
Другие темы раздела
C++ Удалить из списка всех неуспевающих студентов (имеющих двойки) http://www.cyberforum.ru/cpp-beginners/thread518225.html
Ребята, всем привет. Помогите, пожалуйста! Есть задание : Создать структуру с именем Student с полями: фамилия, имя, номер группы, успеваемость (массив из пяти элементов). Сформировать двусвязный список. Удалить из списка всех неуспевающих студентов (имеющих двойки). Вывести измененный список. Проблема состоит в удалении.. Я понимаю, что надо создать условие, если оно будет выполняться, то...
C++ Сума четных елементов и т.д. Здравствуйте, нужно сделать такое задание: 1) нужно создать числовой файл из случайных чисел 2) организовать его просмотр 3) найти сумму четных, не четных, положительных, и отрицательных елементов. 1 и 2 я сделал. #include <iostream.h> #include <conio.h> #include <stdio.h> #include <stdlib.h> http://www.cyberforum.ru/cpp-beginners/thread518222.html
Посоветуйте литературу для MFC проектов C++ 2010 C++
Посоветуйте литературу на которой можно разобрать MFC. А то преподаватель задал л.р. на MFC или CLR и вся группа ничего не знает. Я создал проект в С++ 2010 и там столько всего понаписано, я даже не знаю где и что прописывать для создания хотя бы кнопки.
C++ Многопоточность
Здравствуйте. Подскажите пожалуйста как лучше всего организовать многопоточность? Программа должна обрабатывать строки из файла. вариант1 Сейчас пробую загружать файл в вектор, делить на части и каждый поток запускаеться со своей частью. Работает крайне медленно если размер файла более 5Мб. Вариант2 Не делить файл на части, сразу запускать потоки, каждый поток со своей строкой и ждать...
C++ шаблон класса списка http://www.cyberforum.ru/cpp-beginners/thread518195.html
Уважаемые программисты! помогите пожалуйста с шаблоном класса списка вот код: template <class T> class ListClass { private: struct Node { T Value; Node* next; }; Node* first; //первый элемент Node *current; //последний элемент
C++ Работа с массивом Привет. Прошу помощи вот с какой ситуацией. Нам в универе задали сделать лабораторную по массивам, но я в них вообще не разбираюсь как и в программировании в целом :(. Пожалуйста, сделайте, кто может, а то вообще беда :(. уже все, спасибо :) подробнее

Показать сообщение отдельно
Betokuha
 Аватар для Betokuha
32 / 29 / 9
Регистрация: 05.03.2012
Сообщений: 114
13.03.2012, 21:59     Помогите написать программу в С++. Найти наибольшую клику в заданном орграфе, используя алгоритм нахождения независимых множеств
Клика – полный подграф неориентированного графа. Другими словами, клика графа есть подмножество его вершин, такое, что между каждой парой вершин этого подмножества существует ребро и, кроме того, это подмножество не принадлежит никакому большому подмножеству с тем же свойством.
Подграф графа — граф, содержащий некое подмножество вершин данного графа и некое подмножество инцидентных им рёбер.
Граф – совокупность непустого множества вершин и множества пар вершин.
Неориентированный граф – упорядоченная пара G: = (V,E), для которой выполнены следующие условия:
V это непустое множество вершин или узлов
E это множество пар (в случае неориентированного графа неупорядоченных) вершин, называемых ребрами.

1. Описание алгоритма нахождения клик

В качестве алгоритма поиска клик был выбран алгоритм Брона-Кербоша ("Algorithm 457: Finding All Cliques of an Undirected Graph".), заявленный как один из самых быстрых алгоритмов поиска клик (Cazals, F.; Karande, C. (2008), "A note on the problem of reporting maximal cliques"). Алгоритм разработан голландскими математиками Броном и Кербошем (Bron and Kerbosh) в 1973 году.
Алгоритм использует тот факт, что всякая клика в графе является его максимальным по включению полным подграфом. Начиная с одиночной вершины (образующей полный подграф), алгоритм на каждом шаге пытается увеличить уже построенный полный подграф, добавляя в него вершины из множества кандидатов. Высокая скорость обеспечивается отсечением при переборе вариантов, которые заведомо не приведут к построению клики, для чего используется дополнительное множество, в которое помещаются вершины, которые уже были использованы для увеличения полного подграфа.
На листинге 1.1 приведена реализация алгоритма псевдокодом. M – текущее независимое множество, K – множество кандидатов (вершин, способных образовать клику. На начальном этапе это множество содержит все вершины графа), P – множество отсеянных вершин, которые не могут более добавляться в M, v – просматриваемая вершина, G(i) – множество вершин, смежных с i.

Листинг 1.1 – реализация алгоритма Брона-Кербоша псевдокодом
while K != 0 or M != 0:
if K != 0:
v = K.first
push M, K, P, v
M = M + {v}
K = K – G(v) – {v}
P = P – G(v)
else:
if P == 0:
print M
pop v, P, K, M
K = K – {v}
P = P + {v}

Нуждаюсь помоши
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
Текущее время: 13:08. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru