Форум программистов, компьютерный форум, киберфорум
Наши страницы
C++
Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Перенаправление вывода fwrite http://www.cyberforum.ru/cpp/thread2390726.html
Всем привет. Имеется сишная dll, в ней все функции используют fopen->fwrite->flose для вывода на диск. Как можно перенаправить вывод в буфер памяти?
Удаление элементов из вектора C++
Всем привет, каким образом можно удалить элементы из вектора, не изобретая велосипеда? К примеру есть у меня вектор строк: vector <string> logical_sign = {...
Как деформировать сетку элипсоида и сферы? C++
Как деформировать сетку элипсоида и сферы? сфера: http://www.100byte.ru/stdntswrks/cshrp/sphTK/sphTK.html элипсоид: http://www.cyberforum.ru/multimedia-dev/thread1352290.html тут мне...
C++ Задача на бинпоиск Условие задачи: Скоро новый год и Санта-Клаус уже начал готовить свою волшебную оленью упряжку, на которой он развозит подарки детям. Известно, что упряжку везут несколько волшебных оленей, на... http://www.cyberforum.ru/cpp/thread2390205.html
C++ Хеш-функция и хеш-таблица http://www.cyberforum.ru/cpp/thread2390168.html
Всем привет, написал хеш-функцию для строки: #include <iostream> //Главная библиотека #include <string> //Библиотека для работы со строками в потоке #include <vector> //Библиотека для работы с...
Текст в бинарном файле C++
Все привет, запись происходит сишным методом: ...... FILE *F; if ((F = fopen("Test.dat", "wb")) == NULL) { ...... return; } ......
C++ Опции компилятора Gw/Gy
Может кто разъяснит на, что конкретно влияют опции компилятора Gw и Gy, когда их устанавливаешь одновременно обе то почему-то ниже приведенная функция возвращает "рандомно" не правильные значения....
C++ Парсер Здравствуйте! Помогите довести код до ума! Задание: Выявление возможных ошибок и контроля правильности построения предложений языка в исходном тексте необходимо иметь: 1. Предложение языка,... http://www.cyberforum.ru/cpp/thread2388923.html
C++ Сканер http://www.cyberforum.ru/cpp/thread2388918.html
Здравствуйте! Помогите довести до ума код. Задание: 1. Произвести анализ заданного программного фрагмента на языке PASCAL и выделить все типы имеющихся в нём лексем. 2. Сформировать таблицу...
C++ Чем отличается define и typedef в контексте создания синонима для типа? Чем отличается define и typedef в контексте создания синонима для типа? #define IntVector1 vector<int> typedef vector<int> IntVector2; И если define позволяет делать то же самое, что и typedef, то... http://www.cyberforum.ru/cpp/thread2388898.html
lone_luke
0 / 0 / 0
Регистрация: 07.12.2016
Сообщений: 2
0

Взвешанный граф, алгоритм Флойда

19.01.2019, 16:27. Просмотров 970. Ответов 0
Метки (Все метки)

Добрый день! Помогите правильно переписать программу составления графа (т.е. нужно самой вводить данные по поводу вершин и ребер, а не рандомное заполнение графа), и подскажите как написать алгоритм Флойда для нахождения центра взвешенного орграфа для данной программы (знаю программу только для нахождения кратчайшего ребра).

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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
#include <iostream>
#include "graph.h"
#include <iomanip>
#include <time.h>
#include <stdlib.h>
 
using namespace std;
// Вариант 1
 
// Реализация АТД «Взвешенный орграф». Граф представлен в виде списков смежности. Алгоритм определения центра взвешенного орграфа на основе алгоритма Флойда (центр – множество вершин с минимальным эксцентриситетом).
 
int main()
{
    srand(time(0));
    int choice = -1;
    Graph<float, char> *graph = 0;
    unsigned int V_COUNT = 15, E_COUNT = 20;
    unsigned int start = 0, end = 0, set_v = 0;
    float weight = 0.0;
    bool inserted = false, removed = false, has_edge = false, edge_set = false;
    char data = 0;
    
 
    while (true) {
        choice = 0;
        cout << endl << std::setfill('=') << std::setw(18) << " Graph " << std::setw(15) << ' ' << endl;
        cout << "Available actions:" << endl;
        cout << "1 - create sample graph," << endl << "2 - insert edge," << endl;
        cout << "3 - add vertex," << endl << "4 - remove edge," << endl;
        cout << "5 - check if edge exists," << endl << "6 - set edge parameters," << endl;
        cout << "7 - print graph," << endl << "8 - set vertex." << endl;
        cout << "9 - Floid algoritm" << endl;
        cout << "0 - exit." << endl << "Choice: ";
        cin >> choice;
        cout << endl;
 
        switch (choice) {
        case 1:
            // create sample graph
            if (graph) delete graph;
            graph = new Graph<>();
            for (unsigned int i = 0; i<V_COUNT; i++) {
                graph->add_vertex('a' + i);
            }
            for (unsigned int i = 0; i<E_COUNT; i++) {
                unsigned int start = rand() % V_COUNT, end = rand() % E_COUNT;
                float w = (rand() % 99 + 1) / 100.0;
                graph->insert_edge(start, end, w);
            }
            cout << graph->vertex_count() << " vertices." << endl;
            graph->print();
            break;
 
        case 2:
            // insert edge
            cout << "Enter start vertex (unsigned): "; cin >> start;
            cout << "Enter end vertex (unsigned): "; cin >> end;
            cout << "Enter edge weight (float): "; cin >> weight;
            if (!graph) graph = new Graph<>();
            inserted = graph->insert_edge(start, end, weight);
            if (inserted) {
                cout << "Inserted edge " << start << "-" << end << "(" << weight << ")" << endl;
            }
            else {
                cout << "Cannot insert, start or end vertex doesnt exist in graph." << endl;
            }
            break;
 
        case 3:
            // add vertex
            if (graph) {
                cout << "Enter new vertex data (single character): "; cin >> data;
                graph->add_vertex(data);
                cout << "Added vertex (" << data << ")" << endl;
            }
            else {
                cout << "Empty graph." << endl;
            }
            break;
 
        case 4:
            // remove edge
            if (graph) {
                cout << "Enter start vertex (unsigned): "; cin >> start;
                cout << "Enter end vertex (unsigned): "; cin >> end;
                removed = graph->remove_edge(start, end);
                if (removed) {
                    cout << "Removed edge " << start << "-" << end << endl;
                }
                else {
                    cout << "Cannot remove edge, edge doesnt exist." << endl;
                }
            }
            else {
                cout << "Empty graph." << endl;
            }
            break;
 
        case 5:
            // check if edge exists
            if (graph) {
                cout << "Enter start vertex (unsigned): "; cin >> start;
                cout << "Enter end vertex (unsigned): "; cin >> end;
                has_edge = graph->has_edge(start, end);
                if (has_edge) {
                    cout << "Edge exists." << endl;
                }
                else {
                    cout << "Edge does not exist." << endl;
                }
            }
            else {
                cout << "Empty graph." << endl;
            }
            break;
 
        case 6:
            // set edge parameters
            if (graph) {
                cout << "Enter start vertex (unsigned): "; cin >> start;
                cout << "Enter end vertex (unsigned): "; cin >> end;
                cout << "Enter edge weight (float): "; cin >> weight;
                edge_set = graph->set_edge(start, end, weight);
                if (edge_set) {
                    cout << "Edge " << start << "-" << end << " set to weight " << weight << endl;
                }
                else {
                    cout << "Edge does not exist." << endl;
                }
            }
            else {
                cout << "Empty graph." << endl;
            }
            break;
 
        case 7:
            // print graph
            if (graph) graph->print();
            else cout << "Empty graph.";
            cout << endl;
            break;
 
        case 8:
            if (graph) {
                cout << "Enter vertex index: "; cin >> set_v;
                cout << "Enter new data: "; cin >> data;
                inserted = graph->set_vertex(set_v, data);
                if (inserted) {
                    cout << "Vertex data changed." << endl;
                }
                else {
                    cout << "Incorrect vertex index." << endl;
                }
            }
            else {
                cout << "Empty graph." << endl;
            }
            break;
 
        
        case 0:
            return 0;
            break;
 
        default:
            cout << "Incorrect command. Try again." << endl;
        }
    }
    return 0;
}
Файл graph.h
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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
#ifndef GRAPH_H
#define GRAPH_H
#include <iostream>
 
using namespace std;
 
/*
1) Реализация АТД «Взвешенный орграф». Граф представлен в виде списков смежности. Алгоритм определения центра взвешенного орграфа на основе алгоритма Флойда (центр – множество вершин с минимальным эксцентриситетом).
*/
 
template<typename W = float>
class Edge {
public:
    W weight;
    unsigned int start, end;
    Edge<W> *next;
 
    Edge(int, int, W);
    ~Edge();
};
 
 
template<typename W = float, typename V = char>
class Vertex {
public:
    V data;
    Edge<W> *incident_edges;
 
    Vertex(V);
    ~Vertex();
};
 
 
template<typename W = float, typename V = char>
class Graph {
protected:
    static const size_t INIT_COUNT = 2;
    size_t v_count;
    Vertex<W, V> **vertices;
    size_t max_v_count;
 
public:
    Vertex<W, V>* get_vertex(unsigned int);
    size_t vertex_count();
    bool insert_edge(unsigned int, unsigned int, W);
    void add_vertex(V);
    bool remove_edge(unsigned int, unsigned int);
    bool has_edge(unsigned int, unsigned int);
    Edge<W>* get_edge(unsigned int, unsigned int);
    bool set_edge(unsigned int, unsigned int, W);
    void print();
    bool set_vertex(unsigned int, V);
 
    Graph();
    ~Graph();
};
 
//---------------------------------------------------------------------------//
 
template<typename W, typename V> // Constructor Vertex
Vertex<W, V>::Vertex(V new_data)
{
    this->incident_edges = 0;
    this->data = new_data;
}
 
template<typename W, typename V> // Destructor Vertex
Vertex<W, V>::~Vertex()
{
    if (incident_edges) delete incident_edges;
}
 
template<typename W> // Constructor Edge
Edge<W>::Edge(int new_start, int new_end, W new_weight) : next(0)
{
    this->start = new_start;
    this->end = new_end;
    this->weight = new_weight;
}
 
template<typename W> // Destructor Edge
Edge<W>::~Edge()
{
    if (next) delete next;
}
 
template<typename W, typename V> // Constructor Graph
Graph<W, V>::Graph() : v_count(0)
{
    max_v_count = INIT_COUNT;
    vertices = new Vertex<W, V>*[max_v_count];
}
 
template<typename W, typename V> // Destructor Graph
Graph<W, V>::~Graph()
{
    if (vertices) delete[] vertices;
}
 
template<typename W, typename V> // get_vertex()
Vertex<W, V>* Graph<W, V>::get_vertex(unsigned int index) {
    if (index >= this->v_count) return 0;
    return this->vertices[index];
}
 
 
template<typename W, typename V> // insert_edge()
bool Graph<W, V>::insert_edge(unsigned int new_start, unsigned int new_end, W new_weight) {
    if (new_start >= this->v_count || new_end >= this->v_count) {
        return false;
    }
    if (new_start == new_end) {
        return false;
    }
    if (this->has_edge(new_start, new_end)) {
        return false;
    }
    Edge<W> *new_edge = new Edge<W>(new_start, new_end, new_weight);
    Vertex<W, V> *v_start = vertices[new_start];
    Edge<W> *it_start = v_start->incident_edges;
 
    if (!it_start) {
        v_start->incident_edges = new_edge;
    }
    else {
        while (it_start->next) it_start = it_start->next;
        it_start->next = new_edge;
    }
 
    return true;
}
 
template<typename W, typename V> // add_vertex()
void Graph<W, V>::add_vertex(V new_data) {
    if (this->v_count == this->max_v_count) {
        Vertex<W, V> **new_vertices = new Vertex<W, V>*[max_v_count * 2];
        unsigned int i;
        for (i = 0; i<max_v_count; i++) {
            new_vertices[i] = this->vertices[i];
        }
        new_vertices[i] = new Vertex<W, V>(new_data);
        this->max_v_count *= 2;
        delete this->vertices;
        this->vertices = new_vertices;
    }
    else {
        this->vertices[this->v_count] = new Vertex<W, V>(new_data);
    }
    this->v_count++;
}
 
template<typename W, typename V> // print()
void Graph<W, V>::print() {
    cout << "Vertex(vertex data): incident edges" << endl;
    unsigned int i;
    for (i = 0; i<this->v_count; i++) {
        Vertex<W, V> *v = this->vertices[i];
        cout << i << "(" << v->data << "):\t";
        if (!v->incident_edges) {
            cout << "null";
        }
        else {
            for (Edge<W> *it = this->vertices[i]->incident_edges; it; it = it->next) {
                cout << it->start << ".." << it->end << "(" << it->weight << ") ";
            }
        }
        cout << endl;
    }
}
 
template<typename W, typename V> // vertex_count()
size_t Graph<W, V>::vertex_count() {
    return this->v_count;
}
 
template<typename W, typename V> // has_edge()
bool Graph<W, V>::has_edge(unsigned int start, unsigned int end) {
    return !!(this->get_edge(start, end));
}
 
template<typename W, typename V> // get_edge()
Edge<W>* Graph<W, V>::get_edge(unsigned int start, unsigned int end) {
    Edge<W> *it = this->vertices[start]->incident_edges;
    while (it) {
        if (it->start == start && it->end == end) return it;
        it = it->next;
    }
    return 0;
}
 
template<typename W, typename V> // set_edge()
bool Graph<W, V>::set_edge(unsigned int start, unsigned int end, W weight) {
    if (start > this->v_count || end > this->v_count) {
        return false;
    }
    Edge<W> *edge = this->get_edge(start, end);
    if (edge) {
        edge->weight = weight;
        return true;
    }
    else return false;
}
 
template<typename W, typename V> // remove()
bool Graph<W, V>::remove_edge(unsigned int start, unsigned int end) {
    Edge<W> *prev = this->vertices[start]->incident_edges;
    if (!prev) return false;
 
    if (prev->start == start && prev->end == end) {
        this->vertices[start]->incident_edges = prev->next;
        delete prev;
    }
    else {
        Edge<W> *it = prev->next;
        while (it) {
            if (it->start == start && it->end == end) {
                prev->next = it->next;
                delete it;
            }
            it = it->next;
            prev = prev->next;
        }
    }
    return true;
}
 
template<typename W, typename V> // set_vertex()
bool Graph<W, V>::set_vertex(unsigned int key, V new_data) {
    if (key > this->v_count) {
        return false;
    }
    this->vertices[key]->data = new_data;
    return true;
}
 
 
#endif // GRAPH_H


Вернуться к обсуждению:
Взвешанный граф, алгоритм Флойда
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
19.01.2019, 16:27
Готовые ответы и решения:

Алгоритм Флойда
Помогите переделать программу вот нашел #include &lt;iostream&gt; const int inf=1E9; using namespace...

Алгоритм Флойда для заполнения двумерного массива
Доброго времени суток, вообщем задача стоит такая, есть динамический двумерный массив который...

Алгоритм Флойда-Уоршалла граф
Собственно мне дан ориентированный граф,в котором вес ребра между вершинами i и j допустим-это шанс...

Алгоритм Флойда - Уоршелла
не получается реализовать алгоритм Флойда-Уоршелла, вроде все должнен выводить, а выводит или нули...

Алгоритм Флойда Оршала
Найти наикратчайшее расстояние от каждой до каждой. Задание представляет собой любую матрицу 4*4....

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