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

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

Войти
Регистрация
Восстановить пароль
 
nikolas982
1 / 1 / 0
Регистрация: 10.09.2012
Сообщений: 49
#1

Поиск с возвратом.Граф - C++

05.10.2012, 11:38. Просмотров 819. Ответов 4
Метки нет (Все метки)

Доброго времени суток.
Прощу помощи с решением задачи.


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

Для решения задачи достаточно начиная с любой точки на каждом шаге присоединять к связной части графа ближайшую к ней несвязную точку.


Буду очень благодарен.

Добавлено через 14 часов 34 минуты
Помогите пожалуйста(
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
05.10.2012, 11:38     Поиск с возвратом.Граф
Посмотрите здесь:

Поиск с возвратом для графа? - C++
Тема задачи: Поиск с возвратом. Задачи на графах. Условие задачи: В заданном неориентированном графе найти кратчайший путь,...

Перебор/поиск с возвратом в графе - C++
Подскажите пожалуйста где я могу найти пример такой программы? Уже пару часов гуглю и нигде не найти. Хочу разобраться, а примеров программ...

Функция с возвратом указателя и возвратом ссылки - C++
Найти максимальный и минимальный элемент в двумерном массиве и указать их номера. Указать номер первого отрицательного числа в массиве;...

Реализовать программу, осуществляющую поиск выхода из лабиринта методом поиска с возвратом. - C++
Реализовать программу, осуществляющую поиск выхода из лабиринта методом поиска с возвратом.

Реализовать программу, осуществляющую поиск выхода из лабиринта методом поиска с возвратом. - C++
Реализовать программу, осуществляющую поиск выхода из лабиринта методом поиска с возвратом. Общий алгоритм хотя бы. Ну а лучше всю прогу...

Классы Граф и Узел состоят в отношениях Агрегации. Реализовать поиск узла - C++
Классы Граф и Узел состоят в отношениях Агрегации. Нужно выполнить такие функции. включение в графу элемента со своими связями; вывода...

Функции.Перебор с возвратом - C++
Доброго времени суток Вам, уважаемые форумчане. Не получается решить универскую задачку повышенного уровня :( Подскажите,...

Алгоритмы с возвратом. Задача о весах - C++
Здравствуйте, попытался разобраться с данной задачкой на с++, но ничего не получилось. Нашел в интернете ее на как я понял паскале, но т.к....

Как создать меню с возвратом в консоли? - C++
имеется консольная программа, которая ищет минимальные пути различными методами. также имеет меню из пунктов. выбрав вариант программа ищет...

Решить задачу методом рекурсивного перебора с возвратом - C++
В Волшебной стране используются монетки достоинством A1, A2,..., AM. Волшебный человечек пришел в магазин и обнаружил, что у него есть...

Разъясните ситуацию с возвратом объекта или ссылки на объект - C++
CValue my_f(15, false); CValue my_t(5, false); ... my_f = my_t + 2; Переопределение операторов сложения и...

Прерывание бесконечного цикла с возвратом значения нажатой клавиши в main() - C++
Вкратце, в функции main() есть некий объект класса - scene, также есть бесконечно работающий цикл while(1), в котором вызывается...


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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
valeriikozlov
Эксперт C++
4669 / 2495 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
05.10.2012, 17:22     Поиск с возвратом.Граф #2
Цитата Сообщение от nikolas982 Посмотреть сообщение
Для решения задачи достаточно начиная с любой точки на каждом шаге присоединять к связной части графа ближайшую к ней несвязную точку.
У Вас даже алгоритм решения есть.
Считываете координаты всех точек. Заполняете матрицу смежности типа double a[N][N], где:
a[i][j]=a[j][i], расстояние между точками i и j.
Далее согласно алгоритма создаете еще одну матрицу смежности b[N][N] (можно типа bool), где значение b[i][j] равно true, если между вершинами есть связь. Или false, если между вершинами нет связи.

Цитата Сообщение от nikolas982 Посмотреть сообщение
Помогите пожалуйста(
в чем именно: полностью код написать или что-то конкретное подсказать?
nikolas982
1 / 1 / 0
Регистрация: 10.09.2012
Сообщений: 49
05.10.2012, 18:55  [ТС]     Поиск с возвратом.Граф #3
Конкретное.Как считать координаты нужных точек?
valeriikozlov
Эксперт C++
4669 / 2495 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
05.10.2012, 20:25     Поиск с возвратом.Граф #4
Цитата Сообщение от nikolas982 Посмотреть сообщение
Как считать координаты нужных точек?
да хоть вот так:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <iostream> 
using namespace std;
#define N_max 1000 
int main() 
{ 
    int a[N_max][2], i, n;
    cout<<"n= "; cin>>n;
    for(i=0; i<n; i++)
    {
        cout<<"X"<<i+1<<"= "; cin>>a[i][0];
        cout<<"Y"<<i+1<<"= "; cin>>a[i][1];
    }    
        return 0;
}
способов много...
nikolas982
1 / 1 / 0
Регистрация: 10.09.2012
Сообщений: 49
06.10.2012, 00:08  [ТС]     Поиск с возвратом.Граф #5
valeriikozlov, спасибо.
Yandex
Объявления
06.10.2012, 00:08     Поиск с возвратом.Граф
Ответ Создать тему
Опции темы

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