2 / 2 / 1
Регистрация: 07.05.2016
Сообщений: 74
1

Поиск минимального остовного дерева на графе

28.05.2017, 15:15. Показов 2223. Ответов 1
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Доброго времени суток, не могу уже несколько дней сделать лабораторку по дискретной математике
Дан граф (скрин ниже будет), для проги на вход количество вершин и матрица смежности.
Пробовал гуглить самое лучшее что есть это вот
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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include<conio.h>
#include<iostream>
 
using namespace std;
 
int a,b,u,v,n,i,j,ne=1;
int visited[10]={0},min,mincost=0,cost[10][10];
 
int main()
{
    int path[100]={0}; //В этот массив будут записываться вершины, по которым составиться путь
    int path_index=0;
 
    //clrscr();
    cout<<"Введи количество вершин  "; cin>>n;
    cout<<"Введи матрицу смежности\n";
 
 
 
    for(i=1;i<=n;i++)
    for(j=1;j<=n;j++)
    {
        cin>>cost[i][j];
        if(cost[i][j]==0)
            cost[i][j]=999; //999 - это что-типа бесконечности. Должно быть больше чем значения веса каждого из ребер в графе
    }
    visited[1]=1;
    cout<<"\n";
 
    while(ne < n)
    {
        for(i=1,min=999;i<=n;i++)
        {
 
        }
        for(j=1;j<=n;j++)
        {
 
        }
        if(cost[i][j]< min)
        if(visited[i]!=0)
        {
            min=cost[i][j];
            a=u=i;
            b=v=j;
        }
        if(visited[u]==0 || visited[v]==0)
        {
            path[path_index]=b;
            path_index++;
            //cout<<"\n "<<ne++<<"  "<<a<<"  "<<b<<min; //Можно вывести так
            ne++; //если строчку выше раскомментировать - эту закомментировать
            mincost+=min;
            visited[b]=1;
 
        }
        cost[a][b]=cost[b][a]=999;
    }
 
 
    cout<<"\n";
 
    cout<<1<<" --> ";
    for (int i=0;i<n-1;i++)
    {
      cout<<path[i];
      if (i<n-2) cout<<" --> ";
    }
 
    cout<<"\n Минимальная стоимость  "<<mincost;
 
 
    cin.get();
    cin.get();
}
Но оно не работает
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
28.05.2017, 15:15
Ответы с готовыми решениями:

Поиск минимального остовного дерева на графе
Переделал программу найденную в интернете, написал через функцию. #include &lt;iostream&gt;; #include...

Визуализация построения минимального остовного дерева
Помогите написать код для визуализации построения минимального остовного дерева (алгоритм...

Поиск минимального листа дерева
привет всем, очень нужна ваша помощь, помогите пожалуйста. поиск минимального листа дерева, из...

Поиск значения минимального листа дерева/ошибка
всем привет, такая проблема: в чем ошибка поиска значения минимального листа? #include &lt;tchar.h&gt;...

1
2 / 2 / 1
Регистрация: 07.05.2016
Сообщений: 74
28.05.2017, 15:17  [ТС] 2
Сам граф и пример остовного дерева
Миниатюры
Поиск минимального остовного дерева на графе  
1
28.05.2017, 15:17
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
28.05.2017, 15:17
Помогаю со студенческими работами здесь

Поиск минимального элемента идеально сбалансированного дерева
Как найти минимальный элемент? Вообще не представляю. зы. Дерево поиска другой разговор.

Поиск остовного леса методом Соллина
Доброго времени суток. Передо мной встала задача найти остовной лес минимальной стоимости методом...

Поиск циклов в графе. Поиск центра взвешенного графа
В интернете, к сожалению, по этим вопросам не так уж много нашел. Можете посоветовать...

Поиск минимального остовного дерева в несвязном графе. Алгоритм Прима-Краскала
Господа. Дело такое - нахожу я минимальное остовное дерево в связном графе (в котором каждая...


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

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru