Clasa a XI-a lecția 14

From Algopedia
Jump to navigationJump to search

Lectie

DFS

Parcurgerea în adâncime reprezintă explorarea “naturală” a unui graf neorientat. Este foarte asemănătoare cu modul în care un turist vizitează un oraș în care sunt obiective turistice (vârfurile grafului) și căi de acces între obiective (muchiile). Vizitarea orașului va avea loc din aproape în aproape: se pleacă de la un obiectiv de pornire, se continuă cu un obiectiv învecinat cu acesta, apoi unul învecinat cu al doilea, etc. Parcurgerea în adâncime se face astfel:

  • Se începe cu un vârf inițial x, care este în acest moment vârf curent.
  • Vârful x se vizitează. Se determină primul său vecin nevizitat y al lui x, care devine vârf curent.
  • Apoi se vizitează primul vecin nevizitat al lui y, şi aşa mai departe, mergând în adâncime, până când ajungem la un vârf care nu mai are vecini nevizitați. Când ajungem într-un astfel de vârf, ne întoarcem la “părintele” acestuia – vârful din care am ajuns în acesta.
  • Dacă acest vârf mai are vecini nevizitați, alegem următorul vecin nevizitat al său și continuam parcurgerea în același mod.
  • Dacă nici acest vârf nu mai are vecini nevizitați, revenim în vârful său părinte și continuăm în același mod, până când toate vârfurile accesibile din vârful de start sunt vizitate.

Observație Dacă graful nu este conex, nu ser vor vizita toate vârfurile. Exemplu

Parcurgerea din nodul 5: 5 2 1 4 6 3 7 8 9

Parcurgerea din nodul 1: 1 2 3 5 4 6 7 8 9 Parcurgerea din nodul 2: 2 1 4 5 7 8 9 6 3 Parcurgerea din nodul 9: 9 7 5 2 1 4 6 3 8

Pentru implementarea algoritmului se foloseşte un vector caracteristic pentru memorarea faptului că un anume vârf a fost sau nu vizitat, la un anumit moment al parcurgerii: v[i] = 0, vârful i nu a fost (încă) vizitat v[i] = 1, vârful i a fost vizitat Pentru a determina ordinea în care se parcurg nodurile care pot fi vizitate, se folosește o stivă: se analizează mereu nodurile adiacent cu nodul din vârful stivei dacă pentru nodul din vârful stivei găsim un vecin nevizitat, adăugăm nodul vecin pe stivă dacă pentru nodul din vârful stivei nu mai găsim niciun vecin nevizitat, îl eliminăm de pe stivă Pentru implementare se poate folosi ca stivă memoria STACK, prin intermediul recursivității.

DFS Rerecursiv - reprezentare cu matrice de adiacenta

Functia DFS primeste ca parametru un nod de pornire si va parcurge graful in adancime. Tiparim nodurile parcurse in timp ce le vizitam.

#include <fstream>
#define dim 100                     // nr maxim de noduri
using namespace std;

ifstream fin ( "dfs.in" );
ofstream fout ( "dfs.out" );

bool viz[dim+1], a[dim+1][dim+1];
int n;

void dfs( int nod ){
  fout << nod << " ";                       // afisam nodul curent
  viz[nod] = 1;                             // marcam nodul curent ca fiind vizitat
  for ( int i = 1; i <= n; i++ )            // parcurgem toti vecinii nodului curent
    if (a[nod][i] == 1 && viz[i] == 0 )     // daca nodul nu este vizitat
      dfs( i );                             // parcurgem in adancime din nodul respectiv
}
int main(){
  int m, start, x, y;
  fin >> n >> m >> start;          // citim nr de noduri, nr de muchii si nodul de start 
  for (int i = 1; i <= m; i++) {
    fin >> x >> y;                 // citim o muchie
    a[x][y] = a[y][x] = 1;         // marcam muchia in matricea de adiacenta
  }
  dfs(start);                      // pornim parcurgerea in adancime
  return 0;
}

DFS Recursiv - reprezentare cu liste de adiacenta, implementare cu vectori STL (optional)

#include <bits/stdc++.h>
#define nmax 150
using namespace std;

vector <int> L[nmax];                       // Listele de adiacenta
char viz[nmax];

void dfs( int nod ){
  printf( "%d ", nod );                     // afisam nodul curent
  viz[nod] = 1;                             // il marcam ca vizitat
  for( int i = 0; i < L[nod].size(); i++ )  // parcurgem lista vecinilo nodului curent
    if( viz[L[nod][i]] == 0 )               // daca vecinul i nu L fost vizitat
      dfs(L[nod][i]);                       // parcurgem in adancime din nodul i
}

int main(){
  freopen( "dfs.in", "r", stdin );
  freopen( "dfs.out", "w", stdout );
  int n, m, start, x, y;

  scanf("%d%d%d", &n, &m, &start);  // nr de noduri, nr de muchii, punctul de start
  for(int i = 1; i <= m; i++ ){    
    scanf("%d%d", &x, &y );
    L[x].push_back(y);              // in lista vecinilor lui x, L[x], punem nodul y 
    L[y].push_back(x);              // in lista vecinilor lui y, L[y], punem nodul x 
  }
  /* Daca dorim sa parcurgem vecinii in ordine, va trebui sa sortam listele cu vecini 
  for( i = 1; i <= n; i++ )
    sort( L[i].begin(), L[i].end());    // sortam fiecare lista de vecini, pentru L parcurge vecinii in ordine
  */
  dfs(s);

  return 0;
}

DFS recursiv - reprezentare cu liste de adiacenta, implementare liste alocate dinamic

#include <bits/stdc++.h>
#define nmax 150
using namespace std;

char viz[nmax];
struct nd{
  int x;
  nd *adr;
};
nd* L[nmax];         // listele de adiacenta

// adaugarea unui nod la o lista L; Noturile nu vor fi in ordine creascatoare in liste

void add( nd* &L, int nod ){
  nd* p = new nd;    // alocam un nou nod
  p -> x = nod;      // punem in nodul creat valoarea val
  p -> adr = L;      // legam nodul la lista L( adaugam nodul la inceputul listei )
  L = p;             // primul nod al listei devine p
}

void dfs( int nod ){
  nd* p;
  viz[nod] = 1;
  printf( "%d ", nod );
  // parcurgem lista de vecini ai nodului v
  p = L[nod];                // L[nod] e adresa primului nod din lista vecinilor nodului nod
  while ( p != NULL ){       // cata vreme nu am ajuns la sfarsitul listei ( lista se termina cu o adresa NULL )
    if ( !viz[p -> x] )      // daca vecinul e nevizitat ( p->x e vecinul lui nod )
      dfs( p -> x );         // parcurgem in adancime mai departe din nodul p->x )
    p = p -> adr;            // trecem la urmatorul vecin
  }
}

int main(){
  freopen( "dfs.in", "r", stdin );
  freopen( "dfs.out", "w", stdout );
  int n, m, start, x, y, i;

  scanf("%d%d%d", &n, &m, &start);     // nr de noduri, nr de muchii, punctul de start
  for( i = 1; i <= m; i++ ){
    scanf( "%d%d", &x, &y );           // citim o muchie [x, y]
      add( L[x], y );                  // in lista vecinilor lui x, L[x], punem nodul y
      add( L[y], x );                  // in lista vecinilor lui y, L[y], punem nodul x
  }
  
  dfs(start);
  return 0;
}

Lant, Ciclu, Conexitate - Componente conexe, componente biconexe

Lanț

Definiție: Se numește lanț o succesiune de vârfuri L = [x1,x2,⋯xk] cu proprietatea că oricare două vârfuri consecutive sunt adiacente ( adica exista muchie intre ele ).

  • Vârfurile x1 şi xk se numesc extremitățile lanțului.
  • Numărul k-1 se numește lungimea lanțului și este numărul de muchii din care este format.
  • Lanțul care conține numai vârfuri distincte, două câte două, este lanț elementar.
  • Lanțul care conține numai muchii distincte este lanț simplu.
  • Dacă muchiile unui lanț nu sunt distincte se numește lanț compus.

Exemplu Lant - generarea tuturor lanturilor intre 2 noduri date

Se dă lista muchiilor unui graf neorientat cu n vârfuri și două vârfuri p q. Să se determine toate lanțurile elementare cu extremitățile p și q.

#include <fstream>

using namespace std;

ifstream in("lant.in");
ofstream out("lant.out");

int n,m, p, q, r;
int a[21][21], lant[21];
bool viz[21];

void afish( int k ){
  for (int i = 1; i <= k; i++ )
     out << lant[i] <<' ';
  out << endl;
}

void backtr( int k, int nod ){
  lant[k] = nod;		  // notez nodul curent in lant
  viz[nod] = 1;          	  // marcam ca am vizitat nodul "nod"
  if ( nod == q )           	  // daca am ajuns la nodul q am terminat de construit lantul
    afish( k );                   // afisez sol daca nu a fost vizitat si nodul k
  else
    for (int i = 1; i <= n; i++ ) // adaugam in lant toate nodurile care nevizitate
      if ( a[nod][i] == 1 && viz[i] == 0 )       
        backtr( k + 1, i );
      
  viz[nod] = 0;                   // demarcam ca vizitat nodul, pentru a putea gasi alt lant care il contine
}

int main(){
  in >> n >> m;
  int x, y;
  for ( int i = 1; i <= m; i++ ){
    in >> x >> y;
    a[x][y] = a[y][x] = 1;
  }
  in >> p >> q;         // dorim toate lanturile care incep din p si se termina in q 
  
  backtr( 1, p );       // pornim construirea lantului de la nodul p, vectorul solutie construindu-se de la pozitia 1

  return 0;
}

Probleme similare- Generarea tuturor lanturilor intr-un graf

  • Lant - TEORIE - generarea tuturor lanturilor intre 2 noduri date
  • Lanturi - TEORIE - toate lanturile intre p si q care trec prin r
  • Lanturi1 - LABORATOR - toate lanturile intre p si q care NU trec prin r
  • LantMaxim - LABORATOR - din toatel lanturile generate, il salvez pe cel mai lung

Ciclu

Definiție: Se numește ciclu un lanț simplu ( adica graful are numai muchii distincte ) în care primul vârf este identic cu ultimul.

  • Dacă toate vârfurile sunt distincte, mai puțin primul și ultimul, se numește ciclu elementar.
  • Lungimea unui ciclu este egală cu numărul de muchii din ciclu. Lungimea minimă a unui ciclu este 3.
  • Un ciclu se numește par dacă lungimea sa este pară, respectiv impar în caz contrar.
  • Un graf neorientat care nu conține nici un ciclu se numește aciclic'.

Exemple: În graful de mai jos:

  • [2,4,1,3,5,7] este un lanț elementar
  • [3,5,7,6,5,1] este un lanț neelementar, dar simplu
  • [2,3,5,7,6,5,3,1] este un lanț compus
  • [1,5,3,2,4,1] este un ciclu elementar
  • [1,3,5,7,6,5,1] este un ciclu neelementar

Graf conex. Componente conexe

Definiție: Un graf neorientat se numește graf conex dacă pentru oricare două vârfuri x și y diferite ale sale, există cel puțin un lanț care le leagă, adică x este extremitatea inițială și y este extremitatea finală.

Un graf cu un singur nod este, prin definiție, conex.

Definiție: Se numește componentă conexă a unui graf G=(X,U) un subgraf H=(Y, V), conex, al lui G care are proprietatea că nu există nici un lanț în G care să lege un vârf din Y cu un vârf din X – Y.

Subgraful H este conex și maximal cu această proprietate (dacă s-ar mai adăuga un vârf nu ar mai fi conex.)

Un graf este conex dacă admite o singură componentă conexă.

Exemple: graful din imaginea de mai sus este conex, graful din imaginea urmatoare nu este conex :

Definiție: Un graf este biconex dacă este conex şi pentru orice vârf eliminat subgraful generat îşi păstrează proprietatea de conexitate.

Rezolvarea problelor de conexitate: Urmatoarele probleme sunt legate de verificarea conexitatii grafurilor.

  • Verificam daca un graf este conex parcurgand graful dintr-un nod oarecare (cu DFS sau BFS ). Daca am ajuns in toate nodurile grafului atunci graful este conex.
  • Numaram componentele conexe ale unui graf parcurgand graful (cu DFS sau BFS )

Exemplu ComponenteConexe

Afisarea componentelor conexe

Se dă lista muchiilor unui graf neorientat. Să se afișeze componentele conexe ale acestui graf.

#include <fstream>
#define dim 100                     // nr maxim de noduri
using namespace std;

ifstream in ("componenteconexe.in");
ofstream out ("componenteconexe.out");

char viz[dim+1];
char a[dim+1][dim+1];
int n, cnt;

void dfs( int nod ){
  //out << nod << " ";                           // afisam nodul curent
  viz[nod] = cnt;                                // marcam nodul curent cu nr componentei conexe
  for ( int i = 1; i <= n; i++ )                 // parcurgem toti vecinii nodului curent
      if (a[nod][i] == 1 && viz[i] == 0 )        // daca nodul nu este vizitat
          dfs(i);                                // parcurgem in adancime din nodul respectiv
}
int main(){
  int m, x, y, i;
  in >> n ;                      // citim nr de noduri
  while ( in >> x >> y ) {       // citim o muchie
    a[x][y] = a[y][x] = 1;       // marcam muchia in matricea de adiacenta
  }

  cnt = 0;
  for (i = 1; i <= n; i++ )
    if( !viz[i] ){
      cnt ++;
      dfs(i);
    }

  out << cnt << '\n';
  for ( int c = 1; c <= cnt; c++ ) {
    for (int i = 1; i <= n; i++ )
      if ( viz[i] == c )
        out << i  << " ";
    out << '\n';
  }
  return 0;
}

Componente biconexe (optional)

Se dă un graf neorientat G = (V, E). Un graf se numeşte graf biconex dacă nu are puncte de articulaţie. Un nod se numeşte punct de articulaţie dacă subgraful obţinut prin eliminarea nodului şi a muchiilor incidente cu acesta nu mai este conex. O componentă biconexă a unui graf este un subgraf biconex maximal cu această proprietate.

Articol si probleme: https://www.infoarena.ro/problema/biconex

TEMA

Probelme rezolvate in curs

Implementati problemele rezolvate in curs

Tema Teorie

VerifLant

Se dă lista muchiilor unui graf neorientat cu n vârfuri și o succesiune de k vârfuri. Să se verifice dacă vârfurile din succesiune formează un lanț.

Lanturi - toate lanturile intre p si q care trec prin r

(vezi problema lant din curs )

Se dă lista muchiilor unui graf neorientat cu n vârfuri și trei vârfuri p q r. Să se determine toate lanțurile elementare cu extremitățile în p și q care conțin vârful r.

ciclu

Se dă lista muchiilor unui graf neorientat cu n vârfuri și un vârf p. Să se determine un ciclu elementar care conține vârful p.

Conex

Se dă lista muchiilor unui graf neorientat. Să se verifice dacă graful este sau nu conex.

ComponenteConexe1

Nr minim de muchii de adaugat pentru ca graful sa devina conex

Se dă lista muchiilor unui graf neorientat. Să se determine numărul minim de muchii care trebuie adăugate pentru ca graful să devină conex, precum și un set de asemenea muchii.

Tema Laborator

LantMaxim

Se dă lista muchiilor unui graf neorientat cu n vârfuri și două vârfuri p q. Să se determine cel mai lung lanț elementar cu extremitățile p și q.

Lanturi1

Se dă lista muchiilor unui graf neorientat cu n vârfuri și trei vârfuri p q r. Să se determine toate lanțurile elementare cu extremitățile în p și q care nu conțin vârful r.

ComponenteConexe2

Nr maxim de muchii ce pot fi eliminate astfel incat graful sa ramana conex

Se dă lista muchiilor unui graf neorientat. Să se determine numărul de muchii care pot fi eliminate din graf astfel încât numărul de componente conexe ale grafului să nu se modifice.

ComponenteConexe3

Componenta conexa cu nr maxim de noduri, reprezentantul componentei conexe = nodul cu nr cel mai mic Se dă lista muchiilor unui graf neorientat. Pentru fiecare componentă conexă numim cel mai mic vârf de ea reprezentant al componentei conexe. Determinați reprezentantul componentei conexe cu cele mai multe vârfuri și câte noduri conține aceasta.

ComponenteConexe4 - UNION FIND

Se consideră un graf neorientat cu n vârfuri și m muchii. Cele m muchii se elimină pe rând din graf. Pentru fiecare muchie eliminată trebuie să spuneți câte componente conexe are graful.

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e5;
const int MAXM = 5e5;

int node1[MAXM], node2[MAXM];
int component[MAXN + 1], ans[MAXM];

int find_component(int node) {
  if (component[node] != node)
    component[node] = find_component(component[node]);
  return component[node];
}

int main(){
    int n, m;
    //ifstream cin("componenteconexe4.in");
    //ofstream cout("componenteconexe4.out");
    cin >> n >> m;
    for (int i = 0; i < m; ++i)
      cin >> node1[i] >> node2[i];
    
    // initial fiecare nod i face parte din componenta conexa cu nr  i (toate nodurile sunt izolate si au ca reprezentant pe ele insele)
    for ( int i = 1; i <= n; ++i )
      component[i] = i;
    
    // avem de eliminat m muchii, dupa ultima eliminare voi avea n componente conexe
    ans[m - 1] = n;
    // vom adauga pe rand cate o muchie in graf, in ordinea inversa eliminarii 
    // si vom determina nr de comp conexe  rzultate( vom verifica daca am unit cu o muchie 2 comp conexe                                        
    for (int i = m - 2; i >= 0;  --i ) {
      int x = find_component(node1[i + 1]);     // determinam reprezentantul comp conexe din care face parte x
      int y = find_component(node2[i + 1]);     // determinam reprezentantul comp conexe din care face parte y
      ans[i] = ans[i + 1];                      // nr componente conexe e cel anterior
      if ( x != y ) {                           // daca x si y nu fac parte din aceeasi comp conexa, 
        --ans[i];                               // atunci inseamna ca prin muchia x,y unim 2 comp conexe deci scade nr de comp cu 1
        component[x] = y;                       // reprezentantul componentei conexe x devine nodul y;
      }
    }

    // afisam raspunsurile 
    for (int i = 0; i < m; ++i)
      cout << ans[i] << '\n';
    return 0;
}

Bazine

Nr componentelor conexe

La ştrandul Junior din oraşul nostru s-au construit n bazine pentru înot. Fiecare bazin a fost dotat cu câte un robinet pentru umplerea acestuia cu apă. Între m perechi distincte de bazine, a fost instalată câte o ţeavă prin care apa din cele două bazine din fiecare pereche să poată circula. Astfel, cele două bazine din pereche pot fi umplute prin deschiderea unui singur robinet. Administratorul bazei a numerotat bazinele cu numerele distincte de la 1 la n şi a notat în registrul lui cele m perechi de numere (x1,y1), (x2,y2),…., (xm,ym) corespunzând perechilor de bazine între care a fost instalată câte o ţeavă. Pentru a umple toate bazinele cu apă, administratorul doreşte să deschidă un număr minim de robinete. Scrieţi un program care să citească numerele naturale n şi m, şi cele 2*m numere naturale x1, y1, x2, y2,…., xm, ym, cu semnificația din enunț, şi care să afişeze cel mai mic număr k de robinete pe care trebuie să le deschidă administratorul astfel încât să fie umplute cu apă toate bazinele.

#1707 Retea

Se consideră o rețea formată din n servere, numerotate de la 1 la n. În rețea există m perechi de servere x y cunoscute între care există legături de comunicație directe. Între oricare două servere din rețea există legături, fie directe, fie prin intermediul altor servere.

Stabiliți pentru fiecare dintre cele n servere dacă eliminarea sa din rețea conduce la pierderea legăturii dintre cel puțin două servere rămase.

#1462 Gasti

Să se determine câte găști există în orașul Nicăieri și în câte moduri se poate forma o nouă relație de prietenie, astfel încât, să se obțină o nouă gașcă, cu număr maxim de membri.

Tema Optionala Pregatire Oli

recapitulare DFS pe matrice (FILL)(ambele probleme admit sol si cu BFS )

mediu

greu

mai multe probleme aici:


  • Entries ONI 2001, clasele XI-XII - UNION FIND

Se consideră un graf care inițial este format din P noduri izolate, etichetate de la 1 la P. Se mai consideră N intrări, unde intrare poate însemna:

comandă – o comandă are forma I + J, cu semnificația că în graf se adaugă muchia care unește nodurile I și J (dacă I și J erau deja unite în acel moment, nu se întreprinde nici o acțiune); întrebare – o întrebare este de forma I ? J, adică se întreabă dacă în acel moment I și J sunt în aceeași componentă conexă. Se pleacă deci de la un graf inițial format din noduri izolate, care pe parcurs se “unifică”. Tot pe parcurs sunteți întrebat dacă anumite perechi de noduri sunt sau nu în aceeași componentă conexă. Scrieți un program care să răspundă la întrebările din fișierul de intrare.