C Реализация алгоритма Крускала для MST - PullRequest
Новая
       39

C Реализация алгоритма Крускала для MST

4 голосов
/ 20 ноября 2011

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

И я наткнулся на следующую реализацию этого алгоритма. 

#include<iostream.h>

int p[10];

void kruskal(int w[10][10],int n)
{
    int min,sum=0,ne=0,i,j,u,v,a,b;
    for(i=1;i<=n;i++)
    p[i]=0;
    while(ne<n-1)
    {
        min=999;
        for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
        {
            if(w[i][j]<min)
            {
                    min=w[i][j];
                u=a=i;
                v=b=j;
            }
        }
        while(p[u])
            u=p[u];
        while(p[v])
            v=p[v];
        if(u!=v)
        {
            ne++;
            sum+=min;
            cout<<"\nedge "<<a<<"-->"<<b<<" is "<<min;
            p[v]=u;
        }
        w[a][b]=w[b][a]=999;
    }
    cout<<"\nmin cost spanning tree= "<<sum;
}

void main()
{
    int w[10][10],n,i,j;
    clrscr();
    cout<<"enter no.of vertices\n";
    cin>>n;
    cout<<"enter weight matrix\n";
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            cin>>w[i][j];
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            if(w[i][j]==0)
                w[i][j]=999;
    kruskal(w,n);
}

Что я не понимаю, так это необходимость: 

while(p[u])
    u=p[u];
while(p[v])
    v=p[v];

Что именно делают эти два цикла while?

edit: а также необходимость - 

for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            if(w[i][j]==0)
                w[i][j]=999;

1 Ответ

9 голосов
/ 20 ноября 2011

Алгоритм Крускала хочет добавить определенное ребро (a, b).Однако, прежде чем сделать это, он должен проверить, подключены ли a и b (если они есть, он не добавит ребро).

Ваши четыре заданные строки делают только эту проверку,a и b уже подключены.

Чтобы полностью это понять, необходимо знать следующее: Первоначально u и v установлены на a и b соответственно.Массив p хранит подключенные компоненты.То есть p[x] = y означает: x лежит в связанном компоненте y.Обратите внимание, что изначально каждая вершина представляет свой собственный связанный компонент, обозначенный p[n1] = 0, p[n2] = 0, ... (т.е. компонент имеет значение 0).

Кроме того, обратите внимание, что каждый связанный компонент представлен одной вершиной.

Итак, мы идем: while(p[u]) проверяет, является ли u представителем компонента (u является представителем, если p[u] == 0, что приводит к остановке цикла while).Итак, если u является представителем компонента, он останавливается.

Более интересная часть заключается в следующем: если u не является представителем, алгоритм ищет p[u], то есть он ищет, какой узел является представителем компонента u.Затем он обновляет u соответственно (u=p[u]).

Вы можете рассматривать всю эту игру как график.Рассмотрим следующую таблицу, представляющую подключенные компоненты: 

   u  |  1  2  3  4  5  6  7  8  9
 p[u] |  2  0  2  3  2  1  0  9  0

Это означает, что узел 1 принадлежит компоненту, представленному 2.4 принадлежит компоненту, представленному 3, который сам принадлежит компоненту, представленному 2.Обратите внимание, что 2 является представителем, поскольку он имеет запись 0.

. Вы можете визуализировать это в виде графика: 

  2      7  9
 /|\        |
1 3 5       8
| |
6 4

Видите ли, в настоящее время у нас есть 3 компонента, представленные 2, 7 и 9, соответственно.

Если мы теперь хотим добавить новое ребро (6,7), нам нужно «подняться по деревьям», пока мы не найдем представителей 2 и 7 соответственно.Как мы видим, представители не одинаковы, мы добавляем ребро.

Теперь еще один пример: мы хотим добавить ребро (6, 5), поэтому мы «поднимаемся по дереву» и находим представителя 2 воба случая.Таким образом, мы не добавляем ребро.

«Подниматься по деревьям» делают строки, которые были вами явно указаны.

...