Алгоритм Крускала в Си и что он делает - PullRequest
Новая
       15

Алгоритм Крускала в Си и что он делает

0 голосов
/ 03 июня 2019

У меня есть этот код, который мне дал мой профессор о поиске MST с использованием алгоритма Крускала.Однако я не совсем понимаю, зачем нужны 

int parent[10]

и что происходит, когда мы используем функции 

find()

и 

uni()

Ниже приведен полный код, который он нам дал. 

#include <stdio.h>

int parent[10];

int find(int i)
{
    while(parent[i])
    {
        i=parent[i];
    }
    return i;
}

int uni(int i,int j)
{
    if(i!=j)
    {
        parent[j]=i;
        return 1;
    }
    return 0;
}

int main(void) 
{
    int cost[10][10],u,v,i,j,min,mincost=0,n,ne=1,a,b;
    printf("Enter no. of vertices: ");
    scanf("%d",&n);

    printf("Enter Adjacency Matrix:\n");
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=n;j++)
        {
            scanf("%d",&cost[i][j]);
        }
    }

    while(ne<n)
    {
        min=999;
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=n;j++)
            {
                if(cost[i][j]<min)
                {
                    min=cost[i][j];
                    a=u=i;
                    b=v=j;
                }
            }
        }

        u=find(u);
        v=find(v);
        if(uni(u,v))
        {
            printf("\n%d edge(%d -> %d)=%d",ne++,a,b,min);
            mincost += min;
        }
        cost[a][b]=cost[b][a]=999;
    }

    printf("\nMin. cost of spanning tree=%d",mincost);

    return 0;
}

Я просто ищу объяснение трех вещей, которые я изложил выше.Я понимаю, как работает алгоритм, за исключением трех вещей, которые я изложил.

Спасибо

1 Ответ

1 голос
/ 03 июня 2019

Этот код поддерживает максимум 10 вершин.

  • parent отслеживает родителя узла.
  • find используется для нахождения вершины в наборе (скажем, A), у которого нет родителя. Поэтому, если u находится в множестве A, а v в множестве B, два набора объединяются функцией uni.

Этот код работает, но не так, как вы.

О самом алгоритме:

Крускал - это жадный алгоритм поиска минимального остовного дерева с наименьшим (или максимальным значением). Алгоритм выглядит следующим образом:

  • Сортировка всех весов в порядке возрастания или убывания.
  • Найдите ребро с минимальной (или максимальной стоимостью).
  • Если ребро uv, проверьте, принадлежат ли u и v к одному и тому же набору. Если да, ничего не повторяйте с шага 2.
  • Если нет объединения, наборы, в которых присутствуют u и v, т.е. если u находится в множестве A и v в множестве B, объединяют A и B как C и отбрасывают A и B. Теперь u и v принадлежат C. Повторите с шага 2.

Вот лучший код: https://github.com/26prajval98/DSA/blob/master/graph%20algorithms/kruskal/main.c

...