Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Shadow0671
1 / 1 / 1
Регистрация: 07.05.2016
Сообщений: 71
#1

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

28.05.2017, 15:15. Просмотров 248. Ответов 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++):

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

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

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

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

Поиск значения минимального листа дерева/ошибка
всем привет, такая проблема: в чем ошибка поиска значения минимального листа?...

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

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

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

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

Поиск ободов в графе
К сожалению не получается решить эту задачу на Си. Вот исходный текст задачи:...

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


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

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

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