Блог

Я работаю над проектом на C , который будет использовать алгоритм Примма для определения веса MST. Вот код, который у меня есть до сих пор:

 #include <iostream>
#include <fstream>
#include <iomanip>
#include <string>
#include <queue>
using namespace std;

const int maxVert = 'M'   1;
const int maxAns = maxVert - 'A';

struct edgeType
{
    char vertex1, vertex2;
    int weight;
};

struct qType
{
    char vertex1, vertex2;
    int weight;
    qType* link;
};

enum colorType { white, gray, black };
colorType color[maxVert];

void init(int adj[maxVert][maxVert], colorType color[maxVert], edgeType ans[maxAns]);
void createGraph(int adj[maxVert][maxVert]);
void printGraph(int adj[maxVert][maxVert], ofstreamamp; outf);
void createQueue(qType*amp; qHead, qType*amp; qTail);
bool emptyQueue(qType*amp; qHead, qType*amp; qTail);
void deQueue(qType* qHead, qType* qTail, charamp; vertex1, charamp; vertex2, intamp; weight);
void enQueue(qType* qHead, qType* qTail, char vertex1, char vertex2, int weight);
void mst(qType* qHead, qType* qTail, int adj[maxVert][maxVert], colorType color[maxVert], edgeType ans[maxAns], char startPoint, ofstreamamp; outf);

int main()
{   
    ofstream outf("output.ot");
    int adj[maxVert][maxVert];
    edgeType ans[maxAns];
    qType* qHead;
    qType* qTail;

    init(adj, color, ans);
    createGraph(adj);
    outf << "2D Adjacency Matrix:" << endl;
    printGraph(adj, outf);
    createQueue(qHead, qTail);
    mst(qHead, qTail, adj, color, ans, 'A', outf);

    return 0;
}

void init(int adj[maxVert][maxVert], colorType color[maxVert], edgeType ans[maxAns])
{
    for (int i = 0; i < maxVert; i  )
    {
        for (int j = 0; j < maxVert; j  )
        {
            adj[i][j] = 0;
            adj[j][i] = 0;
        }
    }

    for (int i = 0; i < maxVert; i  )
    {
        colorType color = white;
    }

    for (int i = 0; i < maxAns; i  )
    {
        ans->vertex1 = 0;
        ans->vertex2 = 0;
        ans->weight = 0;
    }
}

void createGraph(int adj[maxVert][maxVert])
{
    char vertex1, vertex2;
    int weight;
    fstream inf("input.dat");

    while (!inf.eof())
    {
        inf >> vertex1 >> vertex2 >> weight;
        adj[vertex1][vertex2] = weight;
        adj[vertex2][vertex1] = weight;
    }
}

void printGraph(int adj[maxVert][maxVert], ofstreamamp; outf)
{   
    int i, j;

    outf << setw(5) << " ";
    for (j = 'A'; j < maxVert; j  )
    {
        outf << setw(3) << (char)j;
    }
    outf << endl;
    
    for (i = 'A'; i < maxVert; i  )
    {
        outf << setw(5) << char(i);
        for (j = 'A'; j < maxVert; j  )
        {
            outf << setw(3) << adj[i][j];
        }
        outf << endl;
    }
    outf << endl;
}

void createQueue(qType*amp; qHead, qType*amp; qTail)
{
    qHead = new qType;
    qTail = new qType;  

    qHead->vertex1 = 'A';
    qTail->vertex1 = 'A';
    qHead->vertex2 = 'A';
    qTail->vertex2 = 'A';
    qHead->weight = 0;
    qTail-> weight = 0;

    qHead->link = qTail;
    qTail->link = NULL;
}

bool emptyQueue(qType*amp; qHead, qType*amp; qTail)
{
    return qHead->link == qTail;
}

void deQueue(qType* qHead, qType* qTail, charamp; vertex1, charamp; vertex2, intamp; weight)
{
    qType *c;
    c = qHead->link;
    qHead->link = c->link;
    vertex1 = c->vertex1;
    vertex2 = c->vertex2;
    weight = c->weight;
    delete c;
}

void enQueue(qType* qHead, qType* qTail, char ivertex1, char ivertex2, int weight)
{
    qType* knew, * next, * previous;
    knew = new qType;
    knew->vertex1 = ivertex1;
    knew->vertex2 = ivertex2;
    knew->weight = weight;
    previous = qHead;
    next = qHead->link;

    while ((next != qTail) amp;amp; (weight >= next->weight))
    {
        previous = next;
        next = next->link;
    }

    previous->link = knew;
    knew->link = next;
}

void mst(qType* qHead, qType* qTail, int adj[maxVert][maxVert], colorType color[maxVert], edgeType ans[maxAns], char startPoint, ofstreamamp; outf)
{
    //char vertex1, vertex2;
    //int weight;
    int counter = 0;
    enQueue(qHead, qTail, startPoint, 'X', 0);
    color[qHead->vertex1] = gray;
    while (!emptyQueue(qHead, qTail))
    {
        deQueue(qHead, qTail, qHead->vertex1, qHead->vertex2, qHead->weight);

        if (color[qHead->vertex1]!=black amp;amp; qHead->weight !=0)
        {
            ans[counter].vertex1 = qHead->vertex1;
            ans[counter].vertex2 = qHead->vertex2;
            ans[counter].weight = qHead->weight;
            counter  ;

            for (qHead->vertex2 = 'A'; qHead->vertex2 > 'M'; qHead->vertex2  )
            {
                if (adj[qHead->vertex1][qHead->vertex2] != 0 amp;amp; color[qHead->vertex2] != black)
                {
                    enQueue(qHead, qTail, qHead->vertex2, qHead->vertex1, adj[qHead->vertex1][qHead->vertex2]);
                    color[qHead->vertex2] = gray;
                }
            }
            color[qHead->vertex1] = black;
        }
    }   
    outf << ans->vertex1 << ans->vertex2 << ans->weight;
}
  

Я могу настроить свою матрицу смежности и присвоить значения веса, но у меня возникают проблемы с моей функцией mst. Я не уверен, использую ли я правильные переменные для передачи в мою очередь. Я хотел бы иметь возможность распечатать ребра и веса, которые охватывают это дерево, но я застрял. Любая помощь будет оценена.