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

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

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

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

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

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


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

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


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

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

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

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

Нахождение кратчайшего пути, поиск с возвратом - C++
Описание проблемы: Есть матрица MxN, на матрицы есть дом школьника и школа. Школьник может двигаться в 4 направления. На прохождения 1ой...

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

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

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

4
valeriikozlov
Эксперт С++
4670 / 2496 / 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 Посмотреть сообщение
Помогите пожалуйста(
в чем именно: полностью код написать или что-то конкретное подсказать?
0
nikolas982
1 / 1 / 0
Регистрация: 10.09.2012
Сообщений: 49
05.10.2012, 18:55  [ТС] #3
Конкретное.Как считать координаты нужных точек?
0
valeriikozlov
Эксперт С++
4670 / 2496 / 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;
}
способов много...
1
nikolas982
1 / 1 / 0
Регистрация: 10.09.2012
Сообщений: 49
06.10.2012, 00:08  [ТС] #5
valeriikozlov, спасибо.
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
06.10.2012, 00:08
Привет! Вот еще темы с ответами:

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

Считать граф из файла (граф задан матрицей) представить его в виде списка и записать список заново в файл - C++
помогите очень срочно надо. считать граф из файла (граф задан матрицей) представить его в виде списка и записать список заново в файл ...

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

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


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

Или воспользуйтесь поиском по форуму:
5
Yandex
Объявления
06.10.2012, 00:08
Ответ Создать тему
Опции темы

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