Форум программистов, компьютерный форум, киберфорум
Наши страницы
C++
Войти
Регистрация
Восстановить пароль
 
lone_luke
0 / 0 / 0
Регистрация: 07.12.2016
Сообщений: 2
1

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

19.01.2019, 16:27. Просмотров 948. Ответов 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
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
19.01.2019, 16:27

Алгоритм Флойда–Уоршелла
for (int k=0; k&lt;n; k++) for (int i=0; i&lt;n; i++) for (int j=0; j&lt;n; j++)как сделать так,...

Алгоритм Флойда С++ реализация
Есть такой код класса Помогите, пожалуйста найти по методу Флойда самый короткий путь, он описан в...

Алгоритм Флойда-Уоршела
Ребят, помогите. На завтра нужно сдать алгоритм флойда. Вроде нашел код, но он не выводит САМО...


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

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

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