Kruskal Alghoritm - работает, но сложно - PullRequest
Новая
       7

Kruskal Alghoritm - работает, но сложно

0 голосов
/ 23 ноября 2018

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

Позвольте мне объяснить: на входе есть числа, например: 

7 6 1 5
1 7 20
7 2 5
2 3 9
4 2 4
5 2 7
6 5 3

В первой строке 4 цифры = количество узлов, количество ребер, начальный узел (с чего начать), конечный узел (где до конца).

В остальных строках 3 числа = один узел (скажем, x), второй узел (y), длина между ними.

На входе я получу кратчайший путь между началом иконечный узел.

В этом примере это будет номер 32.

У меня есть полностью рабочий код: 

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct edge{
    int goal, length;
    struct edge *p_next;
} EDGE;

typedef struct node{
    int name;
    EDGE *p_edges, *last;
} NODE;

int helper;

int getDist(int size, NODE *nodes[size+1], int from, int act, int goal)
{
    EDGE *p_act;

    for(p_act = nodes[act]->p_edges; p_act != 0; p_act = p_act->p_next)
    {
        if (p_act->goal == goal)
        {
            return p_act->length;
        }
        if (p_act->goal != from)
        {
            helper = getDist(size, nodes, act, p_act->goal, goal);
        }
        if (helper != 0)
        {
            return helper + p_act->length;
        }
    }
    return 0;
}

int main()
{
    int numV, numH, start, goal, i, length, a, b;
    EDGE *p_newEdge, *p_newEdge2;
    scanf("%d %d %d %d", &numV , &numH, &start, &goal);
    NODE *nodes [numV+1];

    for(i = 0; i <= numV; i++)
    {
        nodes[i] = (NODE*)malloc(sizeof(NODE));
    }
    for(i = 0; i < numH; i++)
    {
        scanf("%d %d %d",&a,&b,&length);
        p_newEdge = (EDGE*)malloc(sizeof(EDGE));
        p_newEdge->length = length;
        p_newEdge->goal = b;
        p_newEdge2 = (EDGE*)malloc(sizeof(EDGE));
        p_newEdge2->length = length;
        p_newEdge2->goal = a;
        if (nodes[a]->p_edges == 0)
        {
            nodes[a]->p_edges = p_newEdge;
            nodes[a]->last = p_newEdge;
        }
        else if (nodes[a]->p_edges != 0)
        {
            nodes[a]->last->p_next = p_newEdge;
            nodes[a]->last = nodes[a]->last->p_next;
        } 
        if (nodes[b]->p_edges != 0)
        {
            nodes[b]->last->p_next = p_newEdge2;
            nodes[b]->last = nodes[b]->last->p_next;
        }
        else if (nodes[b]->p_edges == 0)
        {
            nodes[b]->p_edges = p_newEdge2;
            nodes[b]->last = p_newEdge2;
        }        
    }
    printf("%d\n",getDist(numV ,nodes, 0, start, goal));
    return 0;
}

Но мой профессор сказал мне, что это оченьдолго, и я должен сделать это более простым (это была моя третья попытка, и для моего профессора она все еще слишком длинна и «сложна»).

Я понятия не имею, как сделать это более простым.Может ли кто-нибудь помочь мне с этим?

...