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

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

Восстановить пароль Регистрация
 
nikolas982
1 / 1 / 0
Регистрация: 10.09.2012
Сообщений: 49
05.10.2012, 11:38     Поиск с возвратом.Граф #1
Доброго времени суток.
Прощу помощи с решением задачи.


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

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


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

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

Реализовать программу, осуществляющую поиск выхода из лабиринта методом поиска с возвратом. C++
C++ Реализовать программу, осуществляющую поиск выхода из лабиринта методом поиска с возвратом.
Считать граф из файла (граф задан матрицей) представить его в виде списка и записать список заново в файл C++
Поиск с возвратом для графа? C++
Функция с возвратом указателя и возвратом ссылки C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 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++
 Аватар для valeriikozlov
4660 / 2486 / 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     Поиск с возвратом.Граф
Ответ Создать тему
Опции темы

Текущее время: 16:12. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru