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

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

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

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

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

Доброго времени суток, не могу уже несколько дней сделать лабораторку по дискретной математике
Дан граф (скрин ниже будет), для проги на вход количество вершин и матрица смежности.
Пробовал гуглить самое лучшее что есть это вот
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
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
28.05.2017, 15:15
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Поиск минимального остовного дерева на графе (C++):

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

Визуализация построения минимального остовного дерева - C++
Помогите написать код для визуализации построения минимального остовного дерева (алгоритм Краскала). Заданы координаты вершин графов, нужно...

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

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

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

Поиск остовного леса методом Соллина - C++
Доброго времени суток. Передо мной встала задача найти остовной лес минимальной стоимости методом Соллина. Интернет предложил единственный...

1
Shadow0671
1 / 1 / 0
Регистрация: 07.05.2016
Сообщений: 63
28.05.2017, 15:17  [ТС] #2
Сам граф и пример остовного дерева
0
Миниатюры
Поиск минимального остовного дерева на графе  
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
28.05.2017, 15:17
Привет! Вот еще темы с ответами:

Поиск циклов в графе. Поиск центра взвешенного графа - C++
В интернете, к сожалению, по этим вопросам не так уж много нашел. Можете посоветовать статью/пособие, где было бы подробно об этом написано?

Поиск на графе - C++
Доброго времени суток. Мне не совсем понятна реализация в коде поиска на графе в высоту и ширину. Т.к. в книге они описаны не совсем...

Поиск циклов в графе - C++
Как узнать что граф имеет цикл?

Поиск мостов в графе - C++
Доброй ночи,задача состоит в отыскании мостов в графе. Много где есть в свободном доступе алгоритм примерно такого рода: ...


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

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

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