CONEXITATE  IN GRAFURI

Se da un graf G=(X, U). Sa se determine numarul de componente conexe ale grafului.

Graful se va citi c o succesiune de muchii (doua varfuri). Numarul de muchii este m.

Odata cu citirea unei muchii se stabileste apartenenta celor doua varfuri la o componenta conexa. Astfel avem 3 cazuri:

1. Daca varfurile nu apartin de nici o componenta conexa atunci se va crea una noua care sa contina cele doua varfuri
2. Daca unul din varfuri apartine de o componenta conexa atunci se va introduce si celalalt sau ambele varfuri apartin de o componenta conexa, atunci nu se va face nimic.
3. Daca unul din varfuri apartine la o componenta conexa si celalalt la o alta componenta conexa atunci cele doua componente conexe se vor uni si va contine toate varfurile de la cele doua si numarul de componente conexe va scade cu 1.

Algoritmul de determinare a nr. de componente conexe.

Pentru I = 1 la m executa

  Citeste x[I], y[I];

  k=0;

  Pentru j = 1 la nc executa

   Daca ((x[I] apartine CompCon[j])  sau (y[I] apartine CompCon[j]))   atunci

            k = k+1;

            u[k] = j;

   SfDaca

 SfPentru

  Daca (k =0) atunci

      nc = nc + 1;

      CompCon[nc] = {x[I], y[I]}

      Altfel    Daca (k=1) atunci

                         CompCon[u[1]] = CompCon[u[1]] U {x[I], y[I]}

                    &nb sp;        Altfel

                          CompCon[u[1]] = CompCon[u[1]] U CompCon[u[2]];

                          nc = nc –1;

                     SfDaca

    SfDaca

SfPentru

           m – numarul de muchii

x[I] – sir ce contine prima extremitate a muchiei

y[I] - sir ce contine a doua extremitate a muchiei

nc – numarul de componente conexe

CompCon[j] – vector ce memoreaza varfurice ce fac parte din componenta conexa j.

u[k] – memoreaza numarul componentei conexe din care fac parte cele doua varfuri

k – ne spune in ce situatie ne aflam (1, 2, sau 3)