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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 12, средняя оценка - 4.58
nikolas982
1 / 1 / 0
Регистрация: 10.09.2012
Сообщений: 49
15.10.2012, 19:11     Построить связный граф с вершинами во всех точках так, чтобы суммарная длина его ребра была наименьшей #1
Здравствуйте, пожалуйста помогите...



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

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





Вторую неделю не получается ничего написать, есть мысли как нужно сделать, а написать не получается (глуп)...
Буду очень благодарен.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
15.10.2012, 19:11     Построить связный граф с вершинами во всех точках так, чтобы суммарная длина его ребра была наименьшей
Посмотрите здесь:

C++ Как сделать так, чтобы программа не компилилась, хотя синтаксически была бы правильной?
рабочая программа. но нужно ее переписать так, чтобы она была наиболее общей. C++
C++ Задача на графы. Удалить ребра так, чтобы степень любой вершины была равна 3 или 0
Связный список (Используя структуру описания даты, построить связный список студентов, сформированный в алфавитном порядке) C++
C++ Вставить равномерно пробелы в строку, чтобы его длина была ровно 50 символов
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
15.10.2012, 19:16     Построить связный граф с вершинами во всех точках так, чтобы суммарная длина его ребра была наименьшей #2
покажите что есть
nikolas982
1 / 1 / 0
Регистрация: 10.09.2012
Сообщений: 49
15.10.2012, 23:03  [ТС]     Построить связный граф с вершинами во всех точках так, чтобы суммарная длина его ребра была наименьшей #3
Я так понял, что нужно сначала задать координаты точек (я буду задавать четыре точки), потом следует формула нахождения суммарной длины ребер L=sqrt(x2-x1)^2+(y2-y1)^2.
Сказали, что нужно создать два массива первый для координат(задает пользователь), второй нужно задать самому и выглядеть он должен так
C++
1
2
3
4
0 1 1 1
1 0 1 1
1 1 0 1
1 1 1 0
А для чего он нужен до сих пор непонятно.
Подскажите пожалуйста, для чего нужен второй массив?Как можно реализовать, что бы пользователь сам мог вводить координаты точек?
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
16.10.2012, 06:06     Построить связный граф с вершинами во всех точках так, чтобы суммарная длина его ребра была наименьшей #4
Цитата Сообщение от nikolas982 Посмотреть сообщение
А для чего он нужен до сих пор непонятно.
Подскажите пожалуйста, для чего нужен второй массив?
У Вас задание:
Цитата Сообщение от nikolas982 Посмотреть сообщение
Построить связный граф с вершинами во всех этих точках так, чтобы суммарная длина его ребра была наименьшей.
результатом программы должна быть матрица смежности этого графа:
Цитата Сообщение от nikolas982 Посмотреть сообщение
0 1 1 1
1 0 1 1
1 1 0 1
1 1 1 0
в матрице смежности если 1 стоит в нулевом строке во втором столбце, то значит между 0-ой точкой и 2-ой точкой есть ребро. Если не знаете что такое матрица смежности, можно через поисковик найти материал и почитать.

Цитата Сообщение от nikolas982 Посмотреть сообщение
Как можно реализовать, что бы пользователь сам мог вводить координаты точек?
Да как угодно, например так:
Считываете значение n.
Создаете двумерный массив размером [n][2].
Затем в цикле:
C++
1
for(i=0; i<n; i++)
считываете значение координат в элементы: в [i][0] - координату x, в [i][1] - координату y
nikolas982
1 / 1 / 0
Регистрация: 10.09.2012
Сообщений: 49
16.10.2012, 13:36  [ТС]     Построить связный граф с вершинами во всех точках так, чтобы суммарная длина его ребра была наименьшей #5
Цитата Сообщение от valeriikozlov Посмотреть сообщение
Создаете двумерный массив размером [n][2]
Подскажите пожалуйста, а почему именно [n][2]?
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
16.10.2012, 21:33     Построить связный граф с вершинами во всех точках так, чтобы суммарная длина его ребра была наименьшей #6
Цитата Сообщение от nikolas982 Посмотреть сообщение
Подскажите пожалуйста, а почему именно [n][2]?
Вот задание:

Цитата Сообщение от nikolas982 Посмотреть сообщение
На плоскости своими координатами задано n точек.
Т.е. входные данные это: n иксов и n игреков. Всего 2*n чисел.
nikolas982
1 / 1 / 0
Регистрация: 10.09.2012
Сообщений: 49
18.10.2012, 19:59  [ТС]     Построить связный граф с вершинами во всех точках так, чтобы суммарная длина его ребра была наименьшей #7
А как можно задать точки координат?
Через двумерный массив.

Добавлено через 21 час 48 минут
Если кто может, пожалуйста, помогите написать программу.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
18.10.2012, 21:14     Построить связный граф с вершинами во всех точках так, чтобы суммарная длина его ребра была наименьшей
Еще ссылки по теме:

C++ Проверить, чтобы длина строки файла была не меньше двух символов
C++ Как обратиться к объекту bitset так, чтобы результатом была битовая маска
Если на трёх точках можно построить разносторонний остроугольный треугольник, найти его площадь C++

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

Или воспользуйтесь поиском по форуму:
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
18.10.2012, 21:14     Построить связный граф с вершинами во всех точках так, чтобы суммарная длина его ребра была наименьшей #8
Цитата Сообщение от nikolas982 Посмотреть сообщение
Если кто может, пожалуйста, помогите написать программу
ну попробуйте такой вариант:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <iostream>
using namespace std;
 
 
int main(){
    int N, i, j, c[100][100], i_min, j_min;
    double a[100][2], b[100][100], min;
    bool d[100]={false}, fl;
    cout<<"Kol-vo vershin: "; cin>>N;
    for(i=0; i<N; i++)
    {
        cout<<"X"<<i+1<<"= "; cin>>a[i][0];
        cout<<"Y"<<i+1<<"= "; cin>>a[i][1]; 
    }
    for(i=0; i<N; i++)
    {
        for(j=0; j<N; j++)
        {
            if(i!=j)
                b[i][j]=(a[i][0]-a[j][0])*(a[i][0]-a[j][0])+(a[i][1]-a[j][1])*(a[i][1]-a[j][1]);
            c[i][j]=0;
        }
    }
    d[0]=true;
    while(true)
    {
        fl=false;
        min=-1.;
        for(i=0; i<N; i++)
            if(d[i]==false)
            {
                fl=true;
                for(j=0; j<N; j++)
                    if(d[j]==true)
                    {
                        if(min==-1.)
                        {
                            min=b[i][j]; i_min=i; j_min=j;
                        }
                        else
                        {
                            if(min>b[i][j])
                            {
                                min=b[i][j]; i_min=i; j_min=j;
                            }
                        }
                    }
            }
        if(!fl)
            break;
        d[i_min]=true;
        c[i_min][j_min]=c[j_min][i_min]=1;
    }
    for(i=0; i<N; i++)
    {
        for(j=0; j<N; j++)
            cout<<c[i][j];
        cout<<endl;
    }
   return 0;
}
Yandex
Объявления
18.10.2012, 21:14     Построить связный граф с вершинами во всех точках так, чтобы суммарная длина его ребра была наименьшей
Ответ Создать тему
Опции темы

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