KI - Przechodzenie grafu DFS - macierze sąsiedztwa i incydencji

Zmianie ulega jedynie sposób wyszukiwania sąsiadów danego wierzchołka. Gdy graf był zdefiniowany za pomocą list sąsiedztwa, odpowiednie wierzchołki sąsiednie były umieszczone na liście skojarzonej z danym wierzchołkiem. Wystarczyło przejrzeć tę listę za pomocą iteratora. W przypadku macierzy sąsiedztwa z danym wierzchołkiem skojarzony jest wiersz tej macierzy. Musimy go przeglądnąć element po elemencie, aż natrafimy na wartość 1, która oznacza istnienie krawędzi od wierzchołka, którego numer odpowiada numerowi wiersza macierzy, do wierzchołka, którego numer odpowiada numerowi kolumny macierzy.

Stosowa metoda DFS

Code::Blocks

// Przechodzenie grafu w głąb - DFS, stos
// Graf nieskierowany - macierz sąsiedztwa
// (C)2011 mgr Jerzy Wałaszek
//----------------------------------------

#include <iostream>
#include <stack>

using namespace std;

int main()
{
  int n,m,i,j,v1,v2;

  // Odczytujemy n i m

  cin >> n >> m;

  // Tworzymy macierz sąsiedztwa

  bool ** A = new bool * [n];

  for(i = 0; i < n; i ++)
  {
    A[i] = new bool[n];
    for(j = 0; j < n; j++) A[i][j] = false;
  }

  // Wczytujemy poszczególne krawędzie i umieszczamy informację o nich w macierzy

  for(i = 0; i < m; i++)
  {
    cin >> v1 >> v2;

    A[v1][v2] = A[v2][v1] = true;
  }

  // Tworzymy dynamicznie tablicę odwiedzin

  bool * visited = new bool[n];

  // Utworzoną tablicę inicjujemy

  for(i = 0; i < n; i++) visited[i] = false;

  // Tworzymy stos

  stack<int> S;

  // Pobieramy wierzchołek startowy i umieszczamy go na stosie

  cin >> v1; S.push(v1);

  // W pętli przechodzimy graf w głąb - DFS

  cout << endl;

  while(!S.empty())
  {
      // Odczytujemy wierzchołek ze stosu. Usuwamy go ze stosu

      v1 = S.top();  S.pop();

      // Jeśli wierzchołek jest nieodwiedzony, to odwiedzamy go i
      // na stosie umieszczamy jego nieodwiedzonych sąsiadów

      if(!visited[v1])
      {
          visited[v1] = true;
          for(i = 0; i < n; i++) if(A[v1][i] && !visited[i]) S.push(i);

          // Odwiedzony wierzchołek wypisujemy

          cout << v1 << " ";
      }
  }

  cout << endl << endl;

  // Usuwamy tablice dynamiczne z pamięci komputera

  delete [] visited;
  
  for(i = 0; i < n; i++) delete [] A[i];

  delete [] A;
  
  return 0;
}

7 8
0 1
0 2
0 3
1 3
2 3
2 4
3 5
4 6
0

0 3 5 2 4 6 1

Rekurencyjna metoda DFS

Code::Blocks

// Przechodzenie grafu w głąb - DFS, rekurencja
// Graf nieskierowany - macierz sąsiedztwa
// (C)2011 mgr Jerzy Wałaszek
//---------------------------------------------

#include <iostream>

using namespace std;

// Zmienne globalne

int n;
bool ** A, * visited;

// Rekurencyjna metoda DFS
//------------------------

void DFS(int v)
{
  visited[v] = true;

  cout << v << " ";

  for(int i = 0; i < n; i++)
    if(A[v][i] && !visited[i]) DFS(i);
}

// Program główny

int main()
{
  int m,i,j,v1,v2;

  // Odczytujemy n i m

  cin >> n >> m;

  // Tworzymy macierz sąsiedztwa

  A = new bool * [n];

  for(i = 0; i < n; i ++)
  {
    A[i] = new bool[n];
    for(j = 0; j < n; j++) A[i][j] = false;
  }
 
  // Wczytujemy poszczególne krawędzie i umieszczamy informację o nich w macierzy

  for(i = 0; i < m; i++)
  {
    cin >> v1 >> v2;

    A[v1][v2] = A[v2][v1] = true;
  }

  // Tworzymy dynamicznie tablicę odwiedzin

  visited = new bool[n];

  // Utworzoną tablicę inicjujemy

  for(i = 0; i < n; i++) visited[i] = false;

  // Pobieramy wierzchołek startowy i wywołujemy rekurencyjnie DFS

  cin >> v1;

  cout << endl;

  DFS(v1);

  cout << endl << endl;

  // Usuwamy tablice dynamiczne z pamięci komputera

  delete [] visited;
  
  for(i = 0; i < n; i++) delete [] A[i];

  delete [] A;
  
  return 0;
}

7 8
0 1
0 2
0 3
1 3
2 3
2 4
3 5
4 6
0

0 1 3 2 4 6 5

Wyniki różnią się od metody stosowej, ponieważ przeglądanie grafu odbywa się w odwrotnym kierunku. Aby uzyskać te same wierzchołki, należy przeglądać wiersze macierzy sąsiedztwa od końca:

Code::Blocks

// Rekurencyjna metoda DFS
// Odwrotny kierunek przeglądania sąsiadów
//----------------------------------------

void DFS(int v)
{
  visited[v] = true;

  cout << v << " ";

  for(int i = n-1; i >= 0; i--)
    if(A[v][i] && !visited[i]) DFS(i);
}

7 8
0 1
0 2
0 3
1 3
2 3
2 4
3 5
4 6
0

0 3 5 2 4 6 1

Listy sąsiedztwa

Macierz sąsiedztwa

// DFS ze stosem

...
while(!S.empty())
{
  v1 = S.top();  S.pop();

  if(!visited[v1])
  {
     visited[v1] = true;
     for(list<int>::iterator it = A[v1].begin(); it != A[v1].end(); it++)
       if(!visited[*it]) S.push(*it);
     cout << v1 << " ";
  }
}

// DFS ze stosem

...
while(!S.empty())
{
  v1 = S.top();  S.pop();

  if(!visited[v1])
  {
     visited[v1] = true;
     for(i = 0; i < n; i++) if(A[v1][i] && !visited[i])
       S.push(i);
       cout << v1 << " ";
  }
}

// DFS rekurencyjna

void DFS(int v)
{
  visited[v] = true;
  cout << v << " ";
  for(list<int>::iterator it = A[v].begin(); it != A[v].end(); it++)
    if(!visited[*it]) DFS(*it);
}

// DFS rekurencyjna

void DFS(int v)
{
  visited[v] = true;
  cout << v << " ";
  for(int i = n-1; i >= 0; i--)
    if(A[v][i] && !visited[i]) DFS(i);
}

Na pierwszy rzut kod dla macierzy sąsiedztwa wydaje się prostszy - nie musimy stosować iteratorów. Jednakże w ogólnym przypadku listy sąsiedztwa są szybsze, ponieważ od razu dostajemy wierzchołki, które tworzą krawędź z przetwarzanym wierzchołkiem. W przypadku macierzy sąsiedztwa musimy ich szukać w wierszu, zatem wykonujemy puste przebiegi pętli. Powoduje to, iż DFS dla macierzy sąsiedztwa ma klasę złożoności O(n²), natomiast dla list sąsiedztwa klasa ta wynosi O(avg_deg x n), gdzie avg_deg oznacza dla danego grafu średni stopień jego wierzchołków. Jeśli graf nie jest grafem zupełnym (każdy wierzchołek jest połączony krawędzią z każdym innym wierzchołkiem w grafie), to stopień ten jest zwykle dużo niższy od n. Wynika z tego wniosek:

Graf zadany macierzą incydencji

Teraz to samo zadanie przeprowadźmy dla grafu reprezentowanego przez macierz incydencji. Przypominam - wiersze macierzy incydencji określają wierzchołki grafu. Kolumny macierzy incydencji określają kolejne krawędzie w grafie. Każda kolumna posiada dwa elementy równe 1 (dla grafu skierowanego odpowiednio 1 i -1). Elementy te oznaczają incydencję (przynależność) wierzchołka do danej krawędzi. Wierzchołek i-ty należy do krawędzi j-tej, jeśli w wierszu i-tym i kolumnie j-tej macierzy incydencji jest wartość różna od 0 (dla grafu skierowanego jest to 1 - wierzchołek początkowy i -1 - wierzchołek końcowy, w grafie nieskierowanym obie wartości są równe 1).

Tutaj strategia wyszukiwania sąsiadów jest następująca: Przeszukujemy wiersz macierzy incydencji. Jeśli w danej kolumnie natrafimy w tym wierszu na wartość 1, to szukamy w tej kolumnie drugiej wartości 1 (dla grafu skierowanego -1). Wiersz, w którym ta druga wartość występuje, da nam wierzchołek będący poszukiwanym sąsiadem.

Stosowa metoda DFS

Code::Blocks

// Przechodzenie grafu w głąb - DFS, stos
// Graf nieskierowany - macierz incydencji
// (C)2011 mgr Jerzy Wałaszek
//----------------------------------------

#include <iostream>
#include <stack>

using namespace std;

int main()
{
  int ** A,n,m,i,j,v1,v2;

  // Odczytujemy n i m

  cin >> n >> m;

  // Dynamicznie tworzymy macierz o wymiarze n x m

  A = new int * [n]; // n wierszy

  for(i = 0; i < n; i++) A[i] = new int [m]; // m wyrazów w wierszu

  // Zerujemy macierz

  for(i = 0; i < n; i++)
    for(j = 0; j < m; j++) A[i][j] = 0;

  // Wczytujemy poszczególne krawędzie i umieszczamy informację o nich w macierzy

  for(i = 0; i < m; i++)
  {
    cin >> v1 >> v2;
    A[v1][i] = A[v2][i] = 1;
  }

  // Tworzymy tablicę odwiedzin

  bool * visited = new bool[n];

  for(i = 0; i < n; i++) visited[i] = false;

  // DFS ze stosem

  // Odczytujemy wierzchołek startowy i umieszczamy go na stosie

  stack<int> S;

  cin >> v1; S.push(v1);

  cout << endl;

  while(!S.empty())
  {

    // Pobieramy ze stosu wierzchołek

    v1 = S.top();  S.pop();

    // Jeśli nie jest odwiedzony, przetwarzamy go

    if(!visited[v1])
    {
       visited[v1] = true;        // Zaznaczamy go jako odwiedzony

       // W pętli wyszukujemy sąsiadów. Sąsiedzi nie odwiedzeni trafiają na stos.

       for(i = 0; i < m; i++)     // Przeglądamy kolejne krawędzie
         if(A[v1][i])             // Jeśli krawędź zawiera wierzchołek v1,
           for(j = 0; j < n; j++) // to szukamy jej drugiego końca, czyli sąsiada v1
             if(j != v1 && A[j][i])
             {
               if(!visited[j]) S.push(j);
               break;
             }

       // Przetworzony wierzchołek wypisujemy

       cout << v1 << " ";
    }
  }

  cout << endl << endl;

  // Usuwamy macierze z pamięci komputera

  delete [] visited;

  for(i = 0; i < n; i++) delete [] A[i];

  delete [] A;

  return 0;
}

7 8
0 1
0 2
0 3
1 3
2 3
2 4
3 5
4 6
0

0 3 5 2 4 6 1

Rekurencyjna metoda DFS

Code::Blocks

// Przechodzenie grafu w głąb - DFS, rekurencja
// Graf nieskierowany - macierz incydencji
// (C)2011 mgr Jerzy Wałaszek
//---------------------------------------------

#include <iostream>

using namespace std;

// Zmienne globalne

int **A,n,m;
bool * visited;

// Rekurencyjna metoda DFS
//------------------------

void DFS(int v)
{
  visited[v] = true;              // Zaznaczamy wierzchołek jako odwiedzony

  cout << v << " ";               // Wypisujemy numer odwiedzonego wierzchołka

  for(int i = m-1; i >= 0; i--)   // Przeglądamy krawędzie od końca, 
                                  // aby wynik był taki sam jak dla DFS ze stosem
    if(A[v][i])                   // Jeśli v należy do i-tej krawędzi,
      for(int j = 0; j < n; j++)  // to szukamy jej drugiego końca
        if(j != v && A[j][i])
        {
          if(!visited[j]) DFS(j); // Jeśli nie odwiedzony, idziemy do niego
          break;
        }
}

// Program główny

int main()
{
  int i,j,v1,v2;

  // Odczytujemy n i m

  cin >> n >> m;

  // Dynamicznie tworzymy macierz o wymiarze n x m

  A = new int * [n]; // n wierszy

  for(i = 0; i < n; i++) A[i] = new int [m]; // m wyrazów w wierszu

  // Zerujemy macierz

  for(i = 0; i < n; i++)
    for(j = 0; j < m; j++) A[i][j] = 0;

  // Wczytujemy poszczególne krawędzie i umieszczamy informację o nich w macierzy

  for(i = 0; i < m; i++)
  {
    cin >> v1 >> v2;
    A[v1][i] = A[v2][i] = 1;
  }

  // Tworzymy tablicę odwiedzin

  visited = new bool[n];

  for(i = 0; i < n; i++) visited[i] = false;

  // Odczytujemy wierzchołek startowy i wywołujemy DFS

  cout << endl;

  cin >> v1;

  DFS(v1);

  cout << endl << endl;

  // Usuwamy macierze z pamięci komputera

  delete [] visited;

  for(i = 0; i < n; i++) delete [] A[i];

  delete [] A;

  return 0;
}

7 8
0 1
0 2
0 3
1 3
2 3
2 4
3 5
4 6
0

0 3 5 2 4 6 1

Listy sąsiedztwa

Macierz incydencji

// DFS ze stosem

...
while(!S.empty())
{
  v1 = S.top();  S.pop();

  if(!visited[v1])
  {
     visited[v1] = true;
     for(list<int>::iterator it = A[v1].begin(); it != A[v1].end(); it++)
       if(!visited[*it]) S.push(*it);
     cout << v1 << " ";
  }
}

// DFS ze stosem

...
while(!S.empty())
{
    v1 = S.top();  S.pop();
    if(!visited[v1])
    {
       visited[v1] = true;
       for(i = 0; i < m; i++)
         if(A[v1][i])
           for(j = 0; j < n; j++)
             if(j != v1 && A[j][i])
             {
               if(!visited[j]) S.push(j);
               break;
             }
       cout << v1 << " ";
    }
  }
}

// DFS rekurencyjna

void DFS(int v)
{
  visited[v] = true;
  cout << v << " ";
  for(list<int>::iterator it = A[v].begin(); it != A[v].end(); it++)
    if(!visited[*it]) DFS(*it);
}

// DFS rekurencyjna

void DFS(int v)
{
  visited[v] = true;
  cout << v << " ";
  for(int i = m-1; i >= 0; i--)
    if(A[v][i])
      for(int j = 0; j < n; j++)
        if(j != v && A[j][i])
        {
          if(!visited[j]) DFS(j);
          break;
        }
}

Już na pierwszy rzut oka widać, że macierz incydencji jest gorszą reprezentacją grafu dla DFS od list sąsiedztwa. Koszt znalezienia sąsiadów danego wierzchołka jest tu największy.

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.

Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl

W artykułach serwisu są używane cookies. Jeśli nie chcesz ich otrzymywać,
zablokuj je w swojej przeglądarce.
Informacje dodatkowe

Przechodzenie grafu metodą DFS

Graf zadany macierzą sąsiedztwa

Stosowa metoda DFS

Rekurencyjna metoda DFS

Graf zadany macierzą incydencji

Stosowa metoda DFS

Rekurencyjna metoda DFS