Задача: Найти минимальное остовное дерево графа с помощью алгоритма Краскала. Сортировку нужно реализовать самому (пользоваться библиотечной сортировкой нельзя, лабораторная работа по проге)).
Реализация: для хранения графа
graph.h
#pragma once
#include <iostream>
#include <string>
#include <vector>
#include <fstream>
const unsigned short MIN_DIST = 0;
const unsigned short MAX_DIST = 1023;
const int MAX_NODES = 50; // Максимальное кол-во вершин
const int MAX_EDGES = 1225; // Полный граф с N вершинами имеет N(N-1)/2 рёбер
// класс ребра
class Edge
{
private:
std::string FirstV, SecondV; // вершины между которыми связь // имя вершины в паре с цветом
int FirstVcolor, SecondVcolor;
unsigned short dist; // вес ребра с диапазоном 0-1023, проверяеться при вводе
public:
// конструктор
Edge() : dist(0), FirstVcolor(0), SecondVcolor(0), FirstV(""), SecondV("") {}
unsigned short getDist() const {
return dist;
}
void setDist(unsigned short dist) {
this->dist = dist;
}
friend class Graph;
};
// класс Графа
class Graph
{
private:
std::vector<Edge> edges; // ГРАФ - по сути массив ребер с вершинами
std::vector<Edge> disjointSet; // Минимальное остовное дерево Disjoint-set/Union-find Forest
int colorOf(std::string str);
void sortEdges(std::vector<Edge> disjointSet, int begin, int end);
void quickSort(std::vector<Edge> edges, int begin, int end); //сортировка ребер по возрастанию
void swapSort(std::vector<Edge> edges, Edge one, Edge Two); // свап для сортировки
public:
// конструктор
Graph() : edges(0), disjointSet(0) {}
void initGraphfromFile(); // Инициализация ГРАФА
void sortQuickSort(); // сортировка по возрастанию весов ребер
void Kruskal(); // алгоритм Краскала
void sortEdgesMST(); // Сортировка вершины в лексикографичеком порядке
void printUnionFindForest(); // вывод минимального остогого дерева на экран
};
Проблема: При сортировке вылетает, выдает это (см. рис.) Сортировка
graph.cpp
void Graph::sortQuickSort() {
quickSort(edges, 0, edges.size()-1);
std::cout << std::endl << "Сортировка ребер по возрастанию весов успешно завершена!" << std::endl;
}
void Graph::swapSort(std::vector<Edge> edges, Edge one, Edge two) {
Edge temp;
temp = one;
one = two;
two = temp;
}
void Graph::quickSort(std::vector<Edge> edges, int begin, int end) { // ?????
int i = begin;
int j = end;
int pivot = (int)(edges.size() / 2); // Выбор опорного элемента -- центр массива
while (i <= j) {
while (edges[i].getDist() < pivot) {
i++;
}
while (edges[j].getDist() > pivot) {
j--;
}
if (i <= j) {
swapSort(edges, edges[i], edges[j]);
i++;
j--;
}
}
if (j > begin) {
quickSort(edges, begin, j);
}
if (i < end) {
quickSort(edges, i, end);
}
}
Прошу указать на ошибки, при возможности предложить решение. Заранее спасибо
Проблема в реализации сортировки - она "тупая" и при обращении к i j элементам массива, выходит за рамки массива (отрицательные или больше реального размера массива).
Вы объявили в классе фунцию_член void quickSort(std::vector<Edge> edges, int begin, int end);
а при определении edges
у вас ссылька. Сигнатура должна быть одинаковая...
P.S. по поводу вашего кода можно сделать много замечаний:
void Edge::getDist() const
)...Айфон мало держит заряд, разбираемся с проблемой вместе с AppLab
Перевод документов на английский язык: Важность и ключевые аспекты
Сразу к сути: выполнял задание с университета Мой код:
Задание от преподавателя ООП в вузеВычислить сумму чисел наследуемых классов используя методы доступа