Dijkstra and Kruskal algorithm

c918

Graph Visualization & Algorithms in Qt (QGraphicsScene)
A complete walkthrough of building an interactive weighted-graph visualizer with Dijkstra's shortest path and Kruskal's MST, rendered entirely through QGraphicsScene / QGraphicsView.
Qt version: 5.15+ / 6.x | Standard: C++17 | Modules: core gui widgets

What This Project Does
The application loads or constructs a weighted undirected graph, runs two classic algorithms on it, and draws everything into a QGraphicsScene:

Grey edges -- normal connections
Green edges -- Dijkstra's shortest path between two chosen vertices
Blue edges -- Kruskal's minimum spanning tree
Red circles -- vertices, labelled with ID and coordinates

The rendering approach uses a multi-pass strategy: draw normal edges first, then overlay highlighted algorithm results on top so they are always visible.

Project Structure
Grafy/
Grafy.pro -- qmake project file
main.cpp -- application entry point
mainwindow.h -- MainWindow declaration
mainwindow.cpp -- MainWindow implementation + rendering logic
mainwindow.ui -- Qt Designer form (QGraphicsView in a grid layout)
The .pro file is minimal -- only core gui widgets, C++17, and the standard source/header/form lists.
Data Structures
Before the rendering code does anything useful you need three structs and a few containers on MainWindow.
3.1 Vertex
cppstruct Vrchol {
int mId; // unique index (0-based, matches position in mVrcholy)
double mX; // scene X coordinate
double mY; // scene Y coordinate
};
3.2 Edge
cppstruct Hrana {
int mIdA; // index of first endpoint in mVrcholy
int mIdB; // index of second endpoint in mVrcholy
double mVaha; // weight (cost / distance)
};
3.3 MainWindow Members
Add these to mainwindow.h inside the private section:
cppQVector<Vrchol*> mVrcholy; // all vertices (owned)
QVector<Hrana*> mHrany; // all edges (owned)

QVector<Vrchol*> mNejkratsiCesta; // ordered list of vertices on the shortest path
QVector<Vrchol*> mKostraGrafu; // MST as flat vertex pairs [a0,b0, a1,b1, ...]

Memory note: The vectors own the raw pointers. Clean them up in the destructor with qDeleteAll(mVrcholy); qDeleteAll(mHrany);.

Building a Sample Graph
For testing, hardcode a small graph inside the constructor or a dedicated nactiGraf() method:
cppvoid MainWindow::nactiGraf()
{
// --- vertices ---
auto v = [&](int id, double x, double y) {
auto* vtx = new Vrchol{id, x, y};
mVrcholy.append(vtx);
};
v(0, 100, 100);
v(1, 300, 50);
v(2, 500, 100);
v(3, 200, 300);
v(4, 400, 300);

// --- edges ---
auto e = [&](int a, int b, double w) {
mHrany.append(new Hrana{a, b, w});
};
e(0, 1, 4);
e(0, 3, 2);
e(1, 2, 5);
e(1, 3, 1);
e(2, 4, 3);
e(3, 4, 7);
}
Call nactiGraf() in the constructor before vykresliGraf().
Dijkstra's Shortest Path
A textbook priority-queue implementation that fills mNejkratsiCesta.
cpp#include <queue>
#include <limits>

void MainWindow::dijkstra(int startId, int endId)
{
const int n = mVrcholy.size();
QVector<double> dist(n, std::numeric_limits<double>::infinity());
QVector<int> prev(n, -1);
dist[startId] = 0.0;

// min-heap: (distance, vertexId)
using Pair = std::pair<double, int>;
std::priority_queue<Pair, std::vector<Pair>, std::greater<Pair>> pq;
pq.push({0.0, startId});

while (!pq.empty()) {
    auto [d, u] = pq.top(); pq.pop();
    if (d > dist[u]) continue;           // stale entry

    for (const Hrana* h : mHrany) {       // scan adjacency
        int neighbour = -1;
        if (h->mIdA == u)      neighbour = h->mIdB;
        else if (h->mIdB == u) neighbour = h->mIdA;
        else continue;

        double alt = dist[u] + h->mVaha;
        if (alt < dist[neighbour]) {
            dist[neighbour] = alt;
            prev[neighbour] = u;
            pq.push({alt, neighbour});
        }
    }
}

// reconstruct path
mNejkratsiCesta.clear();
if (prev[endId] == -1 && endId != startId) return;   // unreachable

for (int at = endId; at != -1; at = prev[at])
    mNejkratsiCesta.prepend(mVrcholy[at]);

}
Complexity: O((V + E) log V) with binary heap.

Kruskal's MST
Sort edges by weight, use Union-Find to avoid cycles.
cpp#include <algorithm>
#include <numeric>

void MainWindow::kruskal()
{
const int n = mVrcholy.size();
mKostraGrafu.clear();

// ---- Union-Find ----
QVector<int> parent(n), rank(n, 0);
std::iota(parent.begin(), parent.end(), 0);

std::function<int(int)> find = [&](int x) -> int {
    return parent[x] == x ? x : (parent[x] = find(parent[x]));
};
auto unite = [&](int a, int b) -> bool {
    a = find(a); b = find(b);
    if (a == b) return false;
    if (rank[a] < rank[b]) std::swap(a, b);
    parent[b] = a;
    if (rank[a] == rank[b]) ++rank[a];
    return true;
};

// ---- sort edges by weight ----
QVector<Hrana*> sorted = mHrany;
std::sort(sorted.begin(), sorted.end(),
          [](const Hrana* a, const Hrana* b){ return a->mVaha < b->mVaha; });

// ---- greedily pick edges ----
for (const Hrana* h : sorted) {
    if (unite(h->mIdA, h->mIdB)) {
        mKostraGrafu.append(mVrcholy[h->mIdA]);
        mKostraGrafu.append(mVrcholy[h->mIdB]);
    }
}

}
Complexity: O(E log E) dominated by the sort.

Rendering with QGraphicsScene
This is the core of the visual side. The vykresliGraf() method clears the scene and redraws everything in four passes.
7.1 Why Multi-Pass?
If you draw all edges in a single loop, the highlighted (green/blue) lines may end up underneath grey ones or under vertex circles. Drawing in layers (normal edges -> path edges -> MST edges -> vertices) guarantees correct Z-ordering without manually setting zValue.
7.2 Edge Key Helper
Because the graph is undirected, edge (2,5) and (5,2) are the same. A small lambda normalizes the pair:
cppauto edgeKey = [](int a, int b) -> QPair<int,int> {
return {std::min(a, b), std::max(a, b)};
};
7.3 Building Lookup Sets
Before drawing, convert algorithm results into QSet for O(1) membership test so you can decide which colour each edge gets:
cppQSet<QPair<int,int>> pathEdges;
for (int i = 0; i + 1 < mNejkratsiCesta.size(); ++i)
pathEdges.insert(edgeKey(mNejkratsiCesta[i]->mId,
mNejkratsiCesta[i + 1]->mId));

QSet<QPair<int,int>> mstEdges;
for (int i = 0; i + 1 < mKostraGrafu.size(); i += 2)
mstEdges.insert(edgeKey(mKostraGrafu[i]->mId,
mKostraGrafu[i + 1]->mId));
7.4 Full Rendering Method
cppvoid MainWindow::vykresliGraf()
{
mScene->clear();

QFont smallFont;
smallFont.setPointSize(8);

const QColor normalColor(180, 180, 180);
const QPen   normalPen(normalColor, 1);
const QPen   pathPen(Qt::green, 3);
const QPen   mstPen(Qt::blue, 3);

auto edgeKey = [](int a, int b) -> QPair<int,int> {
    return {std::min(a, b), std::max(a, b)};
};

// -- build lookup sets (see 7.3) --
QSet<QPair<int,int>> pathEdges;
for (int i = 0; i + 1 < mNejkratsiCesta.size(); ++i)
    pathEdges.insert(edgeKey(mNejkratsiCesta[i]->mId,
                             mNejkratsiCesta[i + 1]->mId));

QSet<QPair<int,int>> mstEdges;
for (int i = 0; i + 1 < mKostraGrafu.size(); i += 2)
    mstEdges.insert(edgeKey(mKostraGrafu[i]->mId,
                            mKostraGrafu[i + 1]->mId));

// ── Pass 1: normal edges (grey, thin) ──
for (const Hrana* h : mHrany) {
    QPair<int,int> key = edgeKey(h->mIdA, h->mIdB);
    if (pathEdges.contains(key) || mstEdges.contains(key))
        continue;

    const Vrchol* va = mVrcholy[h->mIdA];
    const Vrchol* vb = mVrcholy[h->mIdB];
    QPointF p1(va->mX, va->mY), p2(vb->mX, vb->mY);

    mScene->addLine(QLineF(p1, p2), normalPen);

    QGraphicsTextItem* wLabel = mScene->addText(QString::number(h->mVaha));
    wLabel->setFont(smallFont);
    wLabel->setPos((p1 + p2) / 2.0);
    wLabel->setDefaultTextColor(normalColor);
}

// ── Pass 2: shortest-path edges (green, thick) ──
for (const Hrana* h : mHrany) {
    QPair<int,int> key = edgeKey(h->mIdA, h->mIdB);
    if (!pathEdges.contains(key)) continue;

    const Vrchol* va = mVrcholy[h->mIdA];
    const Vrchol* vb = mVrcholy[h->mIdB];
    QPointF p1(va->mX, va->mY), p2(vb->mX, vb->mY);

    mScene->addLine(QLineF(p1, p2), pathPen);

    QGraphicsTextItem* wLabel = mScene->addText(QString::number(h->mVaha));
    wLabel->setFont(smallFont);
    wLabel->setPos((p1 + p2) / 2.0);
    wLabel->setDefaultTextColor(Qt::green);
}

// ── Pass 3: MST edges (blue, thick) ──
for (const Hrana* h : mHrany) {
    QPair<int,int> key = edgeKey(h->mIdA, h->mIdB);
    if (!mstEdges.contains(key)) continue;

    const Vrchol* va = mVrcholy[h->mIdA];
    const Vrchol* vb = mVrcholy[h->mIdB];
    QPointF p1(va->mX, va->mY), p2(vb->mX, vb->mY);

    mScene->addLine(QLineF(p1, p2), mstPen);

    QGraphicsTextItem* wLabel = mScene->addText(QString::number(h->mVaha));
    wLabel->setFont(smallFont);
    wLabel->setPos((p1 + p2) / 2.0);
    wLabel->setDefaultTextColor(Qt::blue);
}

// ── Pass 4: vertices (always on top) ──
const int r = 10;
for (const Vrchol* v : mVrcholy) {
    mScene->addEllipse(v->mX - r, v->mY - r, 2 * r, 2 * r,
                       QPen(Qt::black), QBrush(Qt::red));

    QString lbl = QString::number(v->mId) +
                  " [" + QString::number(v->mX) +
                  "," + QString::number(v->mY) + "]";
    QGraphicsTextItem* txt = mScene->addText(lbl);
    txt->setFont(smallFont);
    txt->setPos(v->mX - r, v->mY - 2 * r - 16);
    txt->setDefaultTextColor(Qt::darkBlue);
}

}

Putting It All Together
Your constructor should look like this:
cppMainWindow::MainWindow(QWidget *parent)
: QMainWindow(parent)
, ui(new Ui::MainWindow)
{
ui->setupUi(this);
mScene = new QGraphicsScene(this);
ui->graphicsView->setScene(mScene);
ui->graphicsView->setTransformationAnchor(QGraphicsView::AnchorUnderMouse);

nactiGraf(); // step 1: load/build graph
dijkstra(0, 4); // step 2: shortest path from vertex 0 to 4
kruskal(); // step 3: minimum spanning tree
vykresliGraf(); // step 4: draw everything
}
And the destructor:
cppMainWindow::~MainWindow()
{
qDeleteAll(mVrcholy);
qDeleteAll(mHrany);
delete ui;
}
How the Rendering Pipeline Works (Visual Summary)
nactiGraf() dijkstra() / kruskal() vykresliGraf()
┌───────────┐ ┌──────────────────────┐ ┌─────────────────┐
│ populate │──────>│ fill mNejkratsiCesta │─────>│ Pass 1: grey │
│ mVrcholy │ │ fill mKostraGrafu │ │ Pass 2: green │
│ mHrany │ └──────────────────────┘ │ Pass 3: blue │
└───────────┘ │ Pass 4: circles │
└─────────────────┘
Extending the Project
10.1 Mouse Wheel Zoom
Override eventFilter on the QGraphicsView:
cppbool MainWindow::eventFilter(QObject* obj, QEvent* event)
{
if (obj == ui->graphicsView && event->type() == QEvent::Wheel) {
auto* we = static_cast<QWheelEvent*>(event);
double factor = (we->angleDelta().y() > 0) ? 1.15 : 1.0 / 1.15;
ui->graphicsView->scale(factor, factor);
return true;
}
return QMainWindow::eventFilter(obj, event);
}
Don't forget to declare eventFilter as protected in the header and note that setTransformationAnchor(AnchorUnderMouse) is already set in the starter code so the zoom is anchored to the cursor position.
10.2 Loading From File
A simple text format -- first line: vertex count and edge count, then vertices (id x y), then edges (idA idB weight):
5 6
0 100 100
1 300 50
2 500 100
3 200 300
4 400 300
0 1 4
0 3 2
1 2 5
1 3 1
2 4 3
3 4 7
Parse with QFile + QTextStream in nactiGraf().
10.3 Interactive Vertex Dragging
Subclass QGraphicsEllipseItem, store a pointer back to the Vrchol, and override itemChange(ItemPositionHasChanged, ...) to sync mX/mY. Set the flag ItemIsMovable | ItemSendsGeometryChanges. After a move, call vykresliGraf() to redraw edges.
10.4 Edge Overlap Handling
When the shortest path and MST share an edge, the current code draws it in whichever pass runs last (blue wins over green). If you want a dual-colour line, draw two parallel lines offset by a pixel or two, or use a dashed pen for one of them.
Key Qt Concepts Used
ConceptWhereWhyQGraphicsScene / QGraphicsViewCentral widgetScene-graph based 2D rendering with built-in pan/zoom supportaddLine(), addEllipse(), addText()vykresliGraf()Convenience methods that create items and add them to the scene in one callQGraphicsTextItemEdge weight labelsRich-text capable label that sits at a scene coordinateQPen width parameterPass 2/3Thick pen (width 3) makes highlighted edges stand out against thin (width 1) normal edgesQSet<QPair<int,int>>Lookup setsO(1) membership test to classify each edge during renderingeventFilterZoomIntercept wheel events on the view without subclassing QGraphicsView
Building
bash# qmake
qmake Grafy.pro
make

or CMake (create your own CMakeLists.txt)

cmake -B build
cmake --build build
Works on Linux, macOS, and Windows with Qt 5.15+ or Qt 6.x.

Common Pitfalls
Duplicate edgeKey sets -- The original commented-out code had QSet<QPair<int,int>> pathEdges declared twice. This won't compile. Make sure each set is declared only once.
mKostraGrafu flat-pair format -- The MST result stores vertex pointers as consecutive pairs [a0, b0, a1, b1, ...], not as a tree. The loop must step by 2: i += 2, not i++.
Floating-point edge weights -- If you use int for mVaha, QString::number() works directly. With double, consider formatting to a fixed number of decimals to keep the labels clean.
Scene coordinate origin -- QGraphicsScene uses standard math coordinates (Y increases downward in screen space). If your vertex coordinates assume Y-up, flip them: mScene->setSceneRect(...) and negate Y values.

Feel free to ask questions or share improvements. The complete starter project (.pro + all sources) is attached above.

c918

#include "mainwindow.h"
#include "ui_mainwindow.h"

#include <QGraphicsScene>
#include <QGraphicsTextItem>
#include <QWheelEvent>

#include <queue>
#include <limits>
#include <algorithm>
#include <numeric>
#include <functional>

// ═══════════════════════════════════════════════════════════════════
// Constructor / Destructor
// ═══════════════════════════════════════════════════════════════════

MainWindow::MainWindow(QWidget *parent)
: QMainWindow(parent)
, ui(new Ui::MainWindow)
{
ui->setupUi(this);

mScene = new QGraphicsScene(this);
ui->graphicsView->setScene(mScene);
ui->graphicsView->setTransformationAnchor(QGraphicsView::AnchorUnderMouse);
ui->graphicsView->installEventFilter(this);

nactiGraf();          // 1) load / build graph
dijkstra(0, 4);       // 2) shortest path  (vertex 0 → 4)
kruskal();            // 3) minimum spanning tree
vykresliGraf();       // 4) render everything

}

MainWindow::~MainWindow()
{
qDeleteAll(mVrcholy);
qDeleteAll(mHrany);
delete ui;
}

// ═══════════════════════════════════════════════════════════════════
// Event Filter (mouse-wheel zoom)
// ═══════════════════════════════════════════════════════════════════

bool MainWindow::eventFilter(QObject* obj, QEvent* event)
{
if (obj == ui->graphicsView && event->type() == QEvent::Wheel) {
auto* we = static_cast<QWheelEvent*>(event);
double factor = (we->angleDelta().y() > 0) ? 1.15 : 1.0 / 1.15;
ui->graphicsView->scale(factor, factor);
return true;
}
return QMainWindow::eventFilter(obj, event);
}

// ═══════════════════════════════════════════════════════════════════
// Graph Data
// ═══════════════════════════════════════════════════════════════════

void MainWindow::nactiGraf()
{
auto v = [&](int id, double x, double y) {
mVrcholy.append(new Vrchol{id, x, y});
};
auto e = [&](int a, int b, double w) {
mHrany.append(new Hrana{a, b, w});
};

//        id    x     y
v(         0,  100,  100);
v(         1,  300,   50);
v(         2,  500,  100);
v(         3,  200,  300);
v(         4,  400,  300);

//      from  to  weight
e(         0,  1,     4);
e(         0,  3,     2);
e(         1,  2,     5);
e(         1,  3,     1);
e(         2,  4,     3);
e(         3,  4,     7);

}

// ═══════════════════════════════════════════════════════════════════
// Dijkstra's Shortest Path
// ═══════════════════════════════════════════════════════════════════

void MainWindow::dijkstra(int startId, int endId)
{
const int n = mVrcholy.size();

// dist[i]  = shortest known distance from startId to vertex i
// prev[i]  = predecessor of vertex i on the shortest path
QVector<double> dist(n, std::numeric_limits<double>::infinity());
QVector<int>    prev(n, -1);
dist[startId] = 0.0;

// Min-heap: (distance, vertexId)
using Pair = std::pair<double, int>;
std::priority_queue<Pair, std::vector<Pair>, std::greater<Pair>> pq;
pq.push({0.0, startId});

while (!pq.empty()) {
    auto [d, u] = pq.top();          // C++17 structured binding
    pq.pop();

    if (d > dist[u]) continue;       // stale entry (lazy deletion)
    if (u == endId)  break;           // destination reached

    // Scan all edges for neighbours of u
    for (const Hrana* h : mHrany) {
        int neighbour = -1;
        if      (h->mIdA == u) neighbour = h->mIdB;
        else if (h->mIdB == u) neighbour = h->mIdA;
        else continue;

        double alt = dist[u] + h->mVaha;
        if (alt < dist[neighbour]) {
            dist[neighbour] = alt;
            prev[neighbour] = u;
            pq.push({alt, neighbour});
        }
    }
}

// ── Reconstruct path ──
mNejkratsiCesta.clear();
if (prev[endId] == -1 && endId != startId)
    return;                            // unreachable

for (int at = endId; at != -1; at = prev[at])
    mNejkratsiCesta.prepend(mVrcholy[at]);

}

// ═══════════════════════════════════════════════════════════════════
// Kruskal's Minimum Spanning Tree
// ═══════════════════════════════════════════════════════════════════

void MainWindow::kruskal()
{
const int n = mVrcholy.size();
mKostraGrafu.clear();

// ── Union-Find ──
QVector<int> parent(n), rank(n, 0);
std::iota(parent.begin(), parent.end(), 0);

std::function<int(int)> find = [&](int x) -> int {
    return parent[x] == x ? x : (parent[x] = find(parent[x]));
};

auto unite = [&](int a, int b) -> bool {
    a = find(a);  b = find(b);
    if (a == b) return false;
    if (rank[a] < rank[b]) std::swap(a, b);
    parent[b] = a;
    if (rank[a] == rank[b]) ++rank[a];
    return true;
};

// ── Sort edges by weight (ascending) ──
QVector<Hrana*> sorted = mHrany;
std::sort(sorted.begin(), sorted.end(),
          [](const Hrana* a, const Hrana* b) {
              return a->mVaha < b->mVaha;
          });

// ── Greedily pick edges ──
int edgesAdded = 0;
for (const Hrana* h : sorted) {
    if (unite(h->mIdA, h->mIdB)) {
        mKostraGrafu.append(mVrcholy[h->mIdA]);
        mKostraGrafu.append(mVrcholy[h->mIdB]);
        if (++edgesAdded == n - 1) break;
    }
}

}

// ═══════════════════════════════════════════════════════════════════
// Rendering (4-pass: grey → green → blue → vertices)
// ═══════════════════════════════════════════════════════════════════

void MainWindow::vykresliGraf()
{
mScene->clear();

QFont smallFont;
smallFont.setPointSize(8);

const QColor normalColor(180, 180, 180);
const QPen   normalPen(normalColor, 1);
const QPen   pathPen(Qt::green, 3);
const QPen   mstPen(Qt::blue, 3);

// Canonical edge key (undirected → smaller id first)
auto edgeKey = [](int a, int b) -> QPair<int,int> {
    return {std::min(a, b), std::max(a, b)};
};

// ── Build O(1) lookup sets from algorithm results ──

QSet<QPair<int,int>> pathEdges;
for (int i = 0; i + 1 < mNejkratsiCesta.size(); ++i)
    pathEdges.insert(edgeKey(mNejkratsiCesta[i]->mId,
                             mNejkratsiCesta[i + 1]->mId));

QSet<QPair<int,int>> mstEdges;
for (int i = 0; i + 1 < mKostraGrafu.size(); i += 2)
    mstEdges.insert(edgeKey(mKostraGrafu[i]->mId,
                            mKostraGrafu[i + 1]->mId));

// ── Pass 1: normal edges (grey, thin) ────────────────────────

for (const Hrana* h : mHrany) {
    QPair<int,int> key = edgeKey(h->mIdA, h->mIdB);
    if (pathEdges.contains(key) || mstEdges.contains(key))
        continue;

    const Vrchol* va = mVrcholy[h->mIdA];
    const Vrchol* vb = mVrcholy[h->mIdB];
    QPointF p1(va->mX, va->mY), p2(vb->mX, vb->mY);

    mScene->addLine(QLineF(p1, p2), normalPen);

    QGraphicsTextItem* wLabel = mScene->addText(QString::number(h->mVaha));
    wLabel->setFont(smallFont);
    wLabel->setPos((p1 + p2) / 2.0);
    wLabel->setDefaultTextColor(normalColor);
}

// ── Pass 2: shortest-path edges (green, thick) ───────────────

for (const Hrana* h : mHrany) {
    QPair<int,int> key = edgeKey(h->mIdA, h->mIdB);
    if (!pathEdges.contains(key))
        continue;

    const Vrchol* va = mVrcholy[h->mIdA];
    const Vrchol* vb = mVrcholy[h->mIdB];
    QPointF p1(va->mX, va->mY), p2(vb->mX, vb->mY);

    mScene->addLine(QLineF(p1, p2), pathPen);

    QGraphicsTextItem* wLabel = mScene->addText(QString::number(h->mVaha));
    wLabel->setFont(smallFont);
    wLabel->setPos((p1 + p2) / 2.0);
    wLabel->setDefaultTextColor(Qt::green);
}

// ── Pass 3: MST edges (blue, thick) ──────────────────────────

for (const Hrana* h : mHrany) {
    QPair<int,int> key = edgeKey(h->mIdA, h->mIdB);
    if (!mstEdges.contains(key))
        continue;

    const Vrchol* va = mVrcholy[h->mIdA];
    const Vrchol* vb = mVrcholy[h->mIdB];
    QPointF p1(va->mX, va->mY), p2(vb->mX, vb->mY);

    mScene->addLine(QLineF(p1, p2), mstPen);

    QGraphicsTextItem* wLabel = mScene->addText(QString::number(h->mVaha));
    wLabel->setFont(smallFont);
    wLabel->setPos((p1 + p2) / 2.0);
    wLabel->setDefaultTextColor(Qt::blue);
}

// ── Pass 4: vertices (always on top) ─────────────────────────

const int r = 10;
for (const Vrchol* v : mVrcholy) {
    mScene->addEllipse(v->mX - r, v->mY - r, 2 * r, 2 * r,
                       QPen(Qt::black), QBrush(Qt::red));

    QString lbl = QString::number(v->mId) +
                  " [" + QString::number(v->mX) +
                  "," + QString::number(v->mY) + "]";
    QGraphicsTextItem* txt = mScene->addText(lbl);
    txt->setFont(smallFont);
    txt->setPos(v->mX - r, v->mY - 2 * r - 16);
    txt->setDefaultTextColor(Qt::darkBlue);
}

}
#ifndef MAINWINDOW_H
#define MAINWINDOW_H

#include <QMainWindow>
#include <QVector>
#include <QSet>
#include <QPair>

QT_BEGIN_NAMESPACE
namespace Ui {
class MainWindow;
}
QT_END_NAMESPACE

class QGraphicsScene;

// ── Graph data structures ────────────────────────────────────────

struct Vrchol {
int mId; // unique index (0-based, matches position in mVrcholy)
double mX; // scene X coordinate
double mY; // scene Y coordinate
};

struct Hrana {
int mIdA; // index of first endpoint in mVrcholy
int mIdB; // index of second endpoint in mVrcholy
double mVaha; // weight (cost / distance)
};

// ── MainWindow ───────────────────────────────────────────────────

class MainWindow : public QMainWindow
{
Q_OBJECT

public:
MainWindow(QWidget *parent = nullptr);
~MainWindow();

protected:
bool eventFilter(QObject* obj, QEvent* event) override;

private:
Ui::MainWindow ui;
QGraphicsScene mScene;

// Graph storage (owned by this class)
QVector<Vrchol*> mVrcholy;         // all vertices
QVector<Hrana*>  mHrany;           // all edges

// Algorithm results
QVector<Vrchol*> mNejkratsiCesta;  // shortest path: ordered vertex sequence
QVector<Vrchol*> mKostraGrafu;     // MST: flat pairs [a0,b0, a1,b1, ...]

// Methods
void nactiGraf();
void dijkstra(int startId, int endId);
void kruskal();
void vykresliGraf();

};

#endif // MAINWINDOW_H

#include "mainwindow.h"

#include <QApplication>

int main(int argc, char *argv[])
{
QApplication a(argc, argv);
MainWindow w;
w.show();
return a.exec();
}

c918

#include "mainwindow.h"
#include "ui_mainwindow.h"

#include <QGraphicsTextItem>
#include <QWheelEvent>

#include <queue>
#include <limits>
#include <algorithm>
#include <numeric>
#include <functional>

// ═══════════════════════════════════════════════════════════════════
// Constructor / Destructor
// ═══════════════════════════════════════════════════════════════════

MainWindow::MainWindow(QWidget *parent)
: QMainWindow(parent)
, ui(new Ui::MainWindow)
{
ui->setupUi(this);
mScene = new QGraphicsScene(this);
ui->graphicsView->setScene(mScene);
ui->graphicsView->setTransformationAnchor(QGraphicsView::AnchorUnderMouse);
ui->graphicsView->installEventFilter(this);

nactiGraf();
dijkstra(0, 4);
kruskal();
vykresliGraf();

}

MainWindow::~MainWindow()
{
qDeleteAll(mVrcholy);
qDeleteAll(mHrany);
delete ui;
}

// ═══════════════════════════════════════════════════════════════════
// Event Filter (mouse-wheel zoom)
// ═══════════════════════════════════════════════════════════════════

bool MainWindow::eventFilter(QObject* obj, QEvent* event)
{
if (obj == ui->graphicsView && event->type() == QEvent::Wheel) {
auto* we = static_cast<QWheelEvent*>(event);
double factor = (we->angleDelta().y() > 0) ? 1.15 : 1.0 / 1.15;
ui->graphicsView->scale(factor, factor);
return true;
}
return QMainWindow::eventFilter(obj, event);
}

// ═══════════════════════════════════════════════════════════════════
// Graph Data
// ═══════════════════════════════════════════════════════════════════

void MainWindow::nactiGraf()
{
auto v = [&](int id, double x, double y) {
mVrcholy.append(new Vrchol{id, x, y});
};
auto e = [&](int a, int b, double w) {
mHrany.append(new Hrana{a, b, w});
};

v(0, 100, 100);
v(1, 300,  50);
v(2, 500, 100);
v(3, 200, 300);
v(4, 400, 300);

e(0, 1, 4);
e(0, 3, 2);
e(1, 2, 5);
e(1, 3, 1);
e(2, 4, 3);
e(3, 4, 7);

}

// ═══════════════════════════════════════════════════════════════════
// Dijkstra's Shortest Path
// ═══════════════════════════════════════════════════════════════════

void MainWindow::dijkstra(int startId, int endId)
{
const int n = mVrcholy.size();

QVector<double> dist(n, std::numeric_limits<double>::infinity());
QVector<int>    prev(n, -1);
dist[startId] = 0.0;

using Pair = std::pair<double, int>;
std::priority_queue<Pair, std::vector<Pair>, std::greater<Pair>> pq;
pq.push({0.0, startId});

while (!pq.empty()) {
    auto [d, u] = pq.top();
    pq.pop();

    if (d > dist[u]) continue;
    if (u == endId)  break;

    for (const Hrana* h : mHrany) {
        int neighbour = -1;
        if      (h->mIdA == u) neighbour = h->mIdB;
        else if (h->mIdB == u) neighbour = h->mIdA;
        else continue;

        double alt = dist[u] + h->mVaha;
        if (alt < dist[neighbour]) {
            dist[neighbour] = alt;
            prev[neighbour] = u;
            pq.push({alt, neighbour});
        }
    }
}

mNejkratsiCesta.clear();
if (prev[endId] == -1 && endId != startId)
    return;

for (int at = endId; at != -1; at = prev[at])
    mNejkratsiCesta.prepend(mVrcholy[at]);

}

// ═══════════════════════════════════════════════════════════════════
// Kruskal's Minimum Spanning Tree
// ═══════════════════════════════════════════════════════════════════

void MainWindow::kruskal()
{
const int n = mVrcholy.size();
mKostraGrafu.clear();

QVector<int> parent(n), rank(n, 0);
std::iota(parent.begin(), parent.end(), 0);

std::function<int(int)> find = [&](int x) -> int {
    return parent[x] == x ? x : (parent[x] = find(parent[x]));
};

auto unite = [&](int a, int b) -> bool {
    a = find(a);  b = find(b);
    if (a == b) return false;
    if (rank[a] < rank[b]) std::swap(a, b);
    parent[b] = a;
    if (rank[a] == rank[b]) ++rank[a];
    return true;
};

QVector<Hrana*> sorted = mHrany;
std::sort(sorted.begin(), sorted.end(),
          [](const Hrana* a, const Hrana* b) {
              return a->mVaha < b->mVaha;
          });

int edgesAdded = 0;
for (const Hrana* h : sorted) {
    if (unite(h->mIdA, h->mIdB)) {
        mKostraGrafu.append(mVrcholy[h->mIdA]);
        mKostraGrafu.append(mVrcholy[h->mIdB]);
        if (++edgesAdded == n - 1) break;
    }
}

}

// ═══════════════════════════════════════════════════════════════════
// Rendering
// ═══════════════════════════════════════════════════════════════════

void MainWindow::vykresliGraf()
{
mScene->clear();

QFont smallFont;
smallFont.setPointSize(8);

const QColor normalColor(180, 180, 180);
const QPen   normalPen(normalColor, 1);

// Build lookup sets for highlighted edges (O(1) membership test)
// mNejkratsiCesta: vertices in path order; consecutive pairs are path edges
auto edgeKey = [](int a, int b) -> QPair<int,int> {
    return {std::min(a, b), std::max(a, b)};
};

QSet<QPair<int,int>> pathEdges;
for (int i = 0; i + 1 < mNejkratsiCesta.size(); ++i) {
    pathEdges.insert(edgeKey(mNejkratsiCesta[i]->mId, mNejkratsiCesta[i + 1]->mId));
}

// mKostraGrafu: flat list of vertex pairs [va0, vb0, va1, vb1, ...]; each pair is one MST edge
QSet<QPair<int,int>> mstEdges;
for (int i = 0; i + 1 < mKostraGrafu.size(); i += 2) {
    mstEdges.insert(edgeKey(mKostraGrafu[i]->mId, mKostraGrafu[i + 1]->mId));
}

// ── Pass 1: normal edges ──────────────────────────────────────────────────
for (const Hrana* h : mHrany) {
    QPair<int,int> key = edgeKey(h->mIdA, h->mIdB);
    if (pathEdges.contains(key) || mstEdges.contains(key))
        continue;

    const Vrchol* va = mVrcholy[h->mIdA];
    const Vrchol* vb = mVrcholy[h->mIdB];
    QPointF p1(va->mX, va->mY), p2(vb->mX, vb->mY);

    mScene->addLine(QLineF(p1, p2), normalPen);

    QGraphicsTextItem* wLabel = mScene->addText(QString::number(h->mVaha));
    wLabel->setFont(smallFont);
    wLabel->setPos((p1 + p2) / 2.0);
    wLabel->setDefaultTextColor(normalColor);
}

// ── Pass 2: shortest-path edges (green) ──────────────────────────────────
const QPen pathPen(Qt::green, 3);
for (const Hrana* h : mHrany) {
    QPair<int,int> key = edgeKey(h->mIdA, h->mIdB);
    if (!pathEdges.contains(key))
        continue;

    const Vrchol* va = mVrcholy[h->mIdA];
    const Vrchol* vb = mVrcholy[h->mIdB];
    QPointF p1(va->mX, va->mY), p2(vb->mX, vb->mY);

    mScene->addLine(QLineF(p1, p2), pathPen);

    QGraphicsTextItem* wLabel = mScene->addText(QString::number(h->mVaha));
    wLabel->setFont(smallFont);
    wLabel->setPos((p1 + p2) / 2.0);
    wLabel->setDefaultTextColor(Qt::green);
}

// ── Pass 3: MST edges (blue) ──────────────────────────────────────────────
const QPen mstPen(Qt::blue, 3);
for (const Hrana* h : mHrany) {
    QPair<int,int> key = edgeKey(h->mIdA, h->mIdB);
    if (!mstEdges.contains(key))
        continue;

    const Vrchol* va = mVrcholy[h->mIdA];
    const Vrchol* vb = mVrcholy[h->mIdB];
    QPointF p1(va->mX, va->mY), p2(vb->mX, vb->mY);

    mScene->addLine(QLineF(p1, p2), mstPen);

    QGraphicsTextItem* wLabel = mScene->addText(QString::number(h->mVaha));
    wLabel->setFont(smallFont);
    wLabel->setPos((p1 + p2) / 2.0);
    wLabel->setDefaultTextColor(Qt::blue);
}

// ── Pass 4: vertices (always on top) ─────────────────────────────────────
const int r = 10;
for (const Vrchol* v : mVrcholy) {
    mScene->addEllipse(v->mX - r, v->mY - r, 2 * r, 2 * r,
                       QPen(Qt::black), QBrush(Qt::red));

    QString lbl = QString::number(v->mId) +
                  " [" + QString::number(v->mX) +
                  "," + QString::number(v->mY) + "]";
    QGraphicsTextItem* txt = mScene->addText(lbl);
    txt->setFont(smallFont);
    txt->setPos(v->mX - r, v->mY - 2 * r - 16);
    txt->setDefaultTextColor(Qt::darkBlue);
}

}

****************************************************************************/
#ifndef MAINWINDOW_H
#define MAINWINDOW_H

#include <QMainWindow>
#include <QVector>
#include <QSet>
#include <QPair>

QT_BEGIN_NAMESPACE
namespace Ui {
class MainWindow;
}
QT_END_NAMESPACE

class QGraphicsScene;

// ── Graph data structures ────────────────────────────────────────

struct Vrchol {
int mId;
double mX;
double mY;
};

struct Hrana {
int mIdA;
int mIdB;
double mVaha;
};

// ── MainWindow ───────────────────────────────────────────────────

class MainWindow : public QMainWindow
{
Q_OBJECT

public:
MainWindow(QWidget *parent = nullptr);
~MainWindow();

protected:
bool eventFilter(QObject* obj, QEvent* event) override;

private:
Ui::MainWindow ui;
QGraphicsScene mScene;

QVector<Vrchol*> mVrcholy;
QVector<Hrana*>  mHrany;

QVector<Vrchol*> mNejkratsiCesta;  // shortest path (ordered vertex sequence)
QVector<Vrchol*> mKostraGrafu;     // MST (flat pairs [a0,b0, a1,b1, ...])

void nactiGraf();
void dijkstra(int startId, int endId);
void kruskal();
void vykresliGraf();

};

#endif // MAINWINDOW_H

Tondatriskal

This post is deleted!

jsulm

Moved to Showcase forum