KI - Przechodzenie grafu DFS

Napisz program, który sprawdza, czy pomiędzy dwoma wskazanymi wierzchołkami grafu skierowanego istnieje ścieżka.

Zadanie sprowadza się do prostej modyfikacji metody DFS. Przejście grafu rozpoczynamy w punkcie startowym. Następnie w każdym obiegu pętli sprawdzamy, czy odwiedzany wierzchołek jest wierzchołkiem docelowym - jeśli tak, wychodzimy z pętli wypisując odpowiednią informację, np. słowo "TAK". Jeśli natomiast metoda DFS przejdzie przez wszystkie dostępne jej wierzchołki grafu bez napotkania wierzchołka docelowego, to poszukiwana ścieżka nie istnieje.

Do przetestowania zadania wykorzystamy poniższy graf skierowany. Na końcu definicji grafu znajdują się numery wierzchołka startowego i końcowego oznaczone kolorem czerwonym. W pierwszym przypadku będzie istniała ścieżka pomiędzy dwoma wybranymi wierzchołkami (zielony oznacza wierzchołek startowy, a niebieski oznacza wierzchołek końcowy), a w drugim przypadku takiej ścieżki nie będzie:

Ścieżka istnieje

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

Ścieżka nie istnieje

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

Code::Blocks

// Sprawdzanie, czy istnieje ścieżka łącząca dwa wierzchołki
// Graf skierowany - DFS ze stosem
// (C)2011 mgr Jerzy Wałaszek
//-----------------------------

#include <iostream>
#include <list>
#include <stack>

using namespace std;

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

  // Odczytujemy n i m

  cin >> n >> m;

  // Tworzymy tablicę n pustych list

  list<int> * A;

  A = new list<int> [n];

  // Wczytujemy poszczególne krawędzie i umieszczamy informację o nich na listach

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

    // Do listy A[v1] dodajemy wierzchołek v2

    A[v1].push_back(v2);

  }

  // Tworzymy dynamicznie tablicę odwiedzin

  bool * visited = new bool[n];

  // Utworzoną tablicę inicjujemy

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

  // Zmienna found będzie zawierała informację, czy ścieżka została znaleziona

  bool found = false;

  // Tworzymy stos

  stack<int> S;

  // Pobieramy wierzchołek startowy i końcowy

  cin >> v1 >> v2;

  // wierzchołek startowy umieszczamy na stosie

  S.push(v1);

  // W pętli przechodzimy graf w głąb aż do napotkania wierzchołka końcowego
  // lub przejścia przez wszystkie dostępne ścieżki w grafie.

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

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

      if(!visited[v1])        // Jeśli wierzchołek jest nieodwiedzony,
      {
        visited[v1] = true;   // zaznaczamy wierzchołek jako odwiedzony
        if(v1 == v2)          // Jeśli wierzchołek końcowy, to:
        {
          found = true;       // zaznaczamy istnienie ścieżki i
          break;              // przerywamy pętlę
        }

        // Na stosie umieszczamy wszystkich nieodwiedzonych jeszcze sąsiadów

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

      }
  }

  // Wypisujemy wynik poszukiwań

  cout << endl;

  if(found) cout << "TAK";
  else      cout << "NIE";

  cout << endl << endl;

  // Usuwamy ewentualne elementy ze stosu

  while(!S.empty()) S.pop();

  // Usuwamy tablice dynamiczne z pamięci komputera

  delete [] visited;
  delete [] A;

  return 0;
}

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

TAK

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

NIE

Zadanie 13

Napisz program, który wyszukuje ścieżkę pomiędzy dwoma wskazanymi wierzchołkami. Wynikiem działania programu ma być ciąg wierzchołków, przez które należy przejść, aby dotrzeć do wskazanego wierzchołka grafu lub informacja, że takiej ścieżki nie ma.

To zadanie jest podobne do poprzedniego - mamy znaleźć ścieżkę łączącą dwa wybrane wierzchołki grafu, jednakże teraz należy tę ścieżkę zapamiętać, aby na końcu programu wypisać ciąg przebytych po drodze wierzchołków. Do rozwiązania wykorzystamy rekurencyjną metodę DFS. Mijane po drodze wierzchołki będziemy umieszczali na liście. Zasada będzie następująca:

Na początku lista mijanych wierzchołków jest pusta. Przeglądanie grafu rozpoczynamy od wierzchołka startowego. Dla każdego wywołania rekurencyjnego DFS wykonujemy co następuje:

Code::Blocks

// Sprawdzanie, czy istnieje ścieżka łącząca dwa wierzchołki
// Graf skierowany - DFS rekurencyjna
// (C)2011 mgr Jerzy Wałaszek
//-----------------------------

#include <iostream>
#include <list>

using namespace std;

// Zmienne globalne

list<int> * A;   // Tablica list sąsiedztwa
list<int> Path;  // Szukana ścieżka
bool * visited;  // Tablica wierzchołków odwiedzonych
bool found;      // Określa, czy znaleziono ścieżkę
int vd;          // Wierzchołek docelowy, do którego ma prowadzić ścieżka

// Rekurencyjna metoda DFS

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

  Path.push_back(v);      // Dopisujemy go do końca listy

  if(v == vd)             // Sprawdzamy, czy jest to wierzchołek docelowy
  {
    found = true;         // Ścieżka znaleziona
    return;               // Przerywamy procedurę
  }

  // inaczej próbujemy odwiedzać wszystkich nieodwiedzonych jeszcze sąsiadów

  for(list<int>::iterator i = A[v].begin(); i != A[v].end(); i++)

    if(!visited[* i])      // Jeśli sąsiad nie jest jeszcze odwiedzony,
    {
        DFS(* i);          // to odwiedzamy go.
        if(found) return;  // Jeśli ścieżka została znaleziona, kończymy DFS
    }

  // Odwiedziliśmy wszystkich sąsiadów i żadna z dróg nie prowadziła do wierzchołka docelowego.
  // Zatem nie tędy droga - usuwamy wierzchołek bieżący z listy Path i wracamy na wyższy
  // poziom w rekurencji.

  Path.pop_back();
}

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

  // Odczytujemy n i m

  cin >> n >> m;

  // Tworzymy tablicę n pustych list

  A = new list<int> [n];

  // Wczytujemy poszczególne krawędzie i umieszczamy informację o nich na listach

  for(i = 0; i < m; i++)
  {
    cin >> v1 >> v2;     // odczytujemy krawędźod v1 do v2

    A[v1].push_back(v2); // Do listy A[v1] dodajemy wierzchołek v2

  }

  // Tworzymy dynamicznie tablicę odwiedzin

  visited = new bool[n];

  // Utworzoną tablicę inicjujemy

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

  // Zmienna found będzie zawierała informację, czy ścieżka została znaleziona

  found = false;

  // Pobieramy wierzchołek startowy i końcowy

  cin >> v1 >> vd;

  // Wywołujemy rekurencyjnie procedurę DFS z wierzchołkiem startowym

  DFS(v1);

  // Jeśli ścieżka znaleziona, wypisujemy ją

  cout << endl;

  if(found)
    for(list<int>::iterator it = Path.begin(); it != Path.end(); it++)
      cout << * it << " ";
  else
    cout << "BRAK";

  cout << endl << endl;

  // Czyścimy listę wierzchołków na ścieżce

  Path.clear();

  // Usuwamy tablice dynamiczne z pamięci komputera

  delete [] visited;
  delete [] A;

  return 0;
}

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

0 3 5 2 1 6 8

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

BRAK

obrazek

Zadanie 14

Graf jest grafem spójnym (ang. connected graph), jeśli istnieją ścieżki pomiędzy wszystkimi parami jego wierzchołków - tzn. każde dowolnie wybrane dwa wierzchołki musi w tym grafie łączyć ścieżka. Dla grafu nieskierowanego problem rozwiązujemy bardzo prosto: wystarczy uruchomić DFS z dowolnie wybranego wierzchołka grafu, a następnie sprawdzić, czy wszystkie wierzchołki w grafie zostały odwiedzone. Jeśli tak, graf jest spójny, a niespójny w przypadku przeciwnym.

Spójny graf nieskierowany

obrazek

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

Niespójny graf nieskierowany

obrazek

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

Code::Blocks

// Sprawdzanie spójności grafu nieskierowanego
// za pomocą przejścia metodą DFS
// (C)2011 mgr Jerzy Wałaszek
//--------------------------------------------

#include <iostream>
#include <stack>
#include <list>

using namespace std;

int main()
{
  list<int> * A;   // Tablica list sąsiedztwa
  bool * visited;  // Tablica wierzchołków odwiedzonych
  int n,m,i,v1,v2;
  bool connected;
  stack<int>S;     // Stos dla DFS

  // Odczytujemy n i m

  cin >> n >> m;

  // Tworzymy tablicę n pustych list

  A = new list<int> [n];

  // Wczytujemy poszczególne krawędzie i umieszczamy informację o nich na listach

  for(i = 0; i < m; i++)
  {
    cin >> v1 >> v2;     // Odczytujemy krawędź od v1 do v2

    A[v1].push_back(v2); // Do listy A[v1] dodajemy wierzchołek v2
    A[v2].push_back(v1); // Do listy A[v2] dodajemy wierzchołek v1 -> graf nieskierowany
  }

  // Tworzymy dynamicznie tablicę odwiedzin

  visited = new bool[n];

  // Utworzoną tablicę inicjujemy

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

  // Za pomocą DFS przechodzimy graf od wierzchołka nr 0

  S.push(0);    // Na stos wierzchołek startowy

  while(!S.empty())
  {
    v1 = S.top(); S.pop();        // Pobieramy wierzchołek ze szczytu stosu

    if(!visited[v1])              // Jeśli nie jest on odwiedzony,
    {
        visited[v1] = true;       // Odwiedzamy go i na stosie umieszczamy nieodwiedzonych sąsiadów

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

  // Metoda DFS przeszła przez graf. Sprawdzamy, czy odwiedziła wszystkie wierzchołki
  // Zmienna connected będzie zawierała informację, czy graf jest spójny

  connected = true;  // Początkowo zakładamy, że tak

  for(i = 0; i < n; i++)
      if(!visited[i])
      {
          connected = false;    // Graf nie jest spójny, zmieniamy stan zmiennej connected
          break;                // Dalsze kontynuowanie pętli nie ma sensu
      }

  cout << endl;

  // W zależności od stanu zmiennej connected wypisujemy odpowiedni komunikat

  if(connected) cout << "TAK"; else cout << "NIE";

  cout << endl << endl;

  // Usuwamy tablice dynamiczne z pamięci komputera

  delete [] visited;
  delete [] A;

  return 0;
}

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

TAK

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

NIE

Dla grafu skierowanego należy uruchamiać DFS z każdego wierzchołka grafu i sprawdzać, czy odwiedziła wszystkie wierzchołki. Jeśli któryś z wierzchołków w danym obiegu DFS nie będzie odwiedzony, graf nie jest spójny.

Spójny graf skierowany

obrazek

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

Niespójny graf skierowany

obrazek

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

Code::Blocks

// Sprawdzanie spójności grafu skierowanego
// za pomocą przejścia metodą DFS
// (C)2011 mgr Jerzy Wałaszek
//-----------------------------

#include <iostream>
#include <stack>
#include <list>

using namespace std;

int main()
{
  list<int> * A;   // Tablica list sąsiedztwa
  bool * visited;  // Tablica wierzchołków odwiedzonych
  int n,m,i,j,v1,v2;
  bool connected;
  stack<int>S;     // Stos dla DFS

  // Odczytujemy n i m

  cin >> n >> m;

  // Tworzymy tablicę n pustych list

  A = new list<int> [n];

  // Wczytujemy poszczególne krawędzie i umieszczamy informację o nich na listach

  for(i = 0; i < m; i++)
  {
    cin >> v1 >> v2;     // Odczytujemy krawędź od v1 do v2

    A[v1].push_back(v2); // Do listy A[v1] dodajemy wierzchołek v2
  }

  // Tworzymy dynamicznie tablicę odwiedzin

  visited = new bool[n];

  // W pętli przechodzimy graf za pomocą DFS. Zmienna connected będzie wskazywała
  // spójność grafu. Na początku inicjujemy ją na true:

  connected = true;

  for(i = 0; connected && i < n; i++)
  {
      // Zerujemy tablicę odwiedzin

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

      S.push(i);    // Na stos wierzchołek startowy

      while(!S.empty())
      {
          v1 = S.top(); S.pop();    // Pobieramy wierzchołek ze szczytu stosu

          if(!visited[v1])          // Jeśli nie jest on odwiedzony,
          {
              visited[v1] = true;   // Odwiedzamy go i na stosie umieszczamy nieodwiedzonych sąsiadów

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

      // Metoda DFS przeszła przez graf. Sprawdzamy, czy odwiedziła wszystkie wierzchołki

      for(j = 0; j < n; j++)
          if(!visited[j])
          {
              connected = false;    // Graf nie jest spójny
              break;                // Przerywamy tę pętlę - główna pętla też się przerwie
          }
  }

  cout << endl;

  if(connected) cout << "TAK"; else cout << "NIE";

  cout << endl << endl;

  // Usuwamy tablice dynamiczne z pamięci komputera

  delete [] visited;
  delete [] A;

  return 0;
}

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

TAK

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

NIE

Zadanie 15

Napisz program, który dla danego grafu spójnego wyznacza jego drzewo rozpinające w postaci tablicy list sąsiedztwa.

Drzewo rozpinające (ang. spanning tree) jest podgrafem, który zawiera wszystkie wierzchołki grafu i nie tworzy cykli (cykl - ścieżka wychodząca z danego wierzchołka i wracająca do niego, nie myl z pętlą, która jest krawędzią wychodzącą i wchodzącą do tego samego wierzchołka). Do utworzenia drzewa rozpinającego możemy wykorzystać algorytm DFS. Zasada jest następująca:

Na stosie DFS należy umieszczać dwa wierzchołki - startowy, z którego wychodzimy, oraz docelowy, do którego prowadzi ścieżka. Dzięki temu po odczycie ze stosu tych wierzchołków będziemy mogli dokonać odpowiednich wpisów do tablicy list sąsiedztwa drzewa rozpinającego. Powstałe drzewo rozpinające jest grafem skierowanym - posiada krawędzie zgodne z kierunkami przejść DFS.

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

Code::Blocks
// Tworzenie drzewa rozpinającego // za pomocą przejścia metodą DFS // Graf nieskierowany, spójny // (C)2011 mgr Jerzy Wałaszek //----------------------------- #include <iostream> #include <stack> #include <list> using namespace std; int main() { list<int> * A; // Tablica list sąsiedztwa grafu list<int> * T; // Tablica list sąsiedztwa drzewa rozpinającego bool * visited; // Tablica wierzchołków odwiedzonych int n,m,i,v1,v2; stack<int>S; // Stos dla DFS // Odczytujemy n i m cin >> n >> m; // Tworzymy 2 tablice n pustych list sąsiedztwa A = new list<int> [n]; // Dla grafu T = new list<int> [n]; // Dla drzewa rozpinającego grafu // Wczytujemy poszczególne krawędzie i umieszczamy informację o nich na listach for(i = 0; i < m; i++) { cin >> v1 >> v2; // Odczytujemy krawędź od v1 do v2 A[v1].push_back(v2); // Do listy A[v1] dodajemy wierzchołek v2 A[v2].push_back(v1); // Do listy A[v2] dodajemy wierzchołek v1 } // Tworzymy dynamicznie tablicę odwiedzin visited = new bool[n]; // Zerujemy tablicę odwiedzin for(i = 0; i < n; i++) visited[i] = false; // Na stosie umieszczamy wierzchołek -1 oraz startowy 0. -1 oznacza, że // jest to wierzchołek główny i nie należy umieszczać go w T S.push(-1); S.push(0); // Rozpoczynamy przejście DFS while(!S.empty()) { // Ze stosu odczytujemy wierzchołek oraz skąd do niego trafiliśmy v1 = S.top(); S.pop(); // Wierzchołek aktualny v2 = S.top(); S.pop(); // Wierzchołek, z którego przyszliśmy if(!visited[v1]) // Jeśli wierzchołek nie jest odwiedzony, { visited[v1] = true; // odwiedzamy go if(v2 != -1) // i uaktualniamy drzewo rozpinające T[v2].push_back(v1); // Nieodwiedzonych sąsiadów umieszczamy na stosie wraz z numerem aktualnego wierzchołka for(list<int>::iterator it = A[v1].begin(); it != A[v1].end(); it++) if(!visited[it]) { S.push(v1); S.push(it); } } } // Procedura DFS zakończyła przejście, wyświetlamy zawartość tablicy T for(i = 0; i < n; i++) { cout << endl << i << " : "; for(list<int>::iterator it = T[i].begin(); it != T[i].end(); it++) cout << *it << " "; } cout << endl << endl; // Usuwamy tablice dynamiczne z pamięci komputera delete [] visited; delete [] A; delete [] T; return 0; }
7 12 0 1 0 3 0 4 0 6 1 2 1 5 2 3 2 4 2 5 2 6 3 5 4 6 0 : 6 1 : 2 : 5 3 : 4 : 2 5 : 3 1 6 : 4
Graf wyjściowy	Drzewo rozpinające DFS

Zadanie 16

Mamy daną grupę osób. Dla każdej z tych osób znamy osoby, z którymi są one powiązane. Naszym zadaniem jest wydzielenie wszystkich grup powiązanych ze sobą osób.

Problem ten sprowadza się do wyznaczenia spójnych składowych grafu. Przez spójną składową rozumiemy maksymalny (tzn. obejmujący największą możliwą liczbę wierzchołków grafu bazowego) podgraf, który jest spójny. Osoby i ich wzajemne powiązania reprezentujemy grafem nieskierowanym. Rozwiązanie jest następujące:

Tworzymy dodatkową tablicę C o tylu elementach, ile mamy wierzchołków w grafie. Elementy tablicy C zerujemy. Tworzymy licznik obiegów DFS. Zerujemy go. Teraz w pętli wyszukujemy kolejny wierzchołek v, dla którego C[v] = 0. Zwiększamy o 1 licznik DFS. Od tego wierzchołka rozpoczynamy przejście DFS. Procedura DFS zamiast tablicy visited może wykorzystywać tablicę C do zaznaczania wierzchołków odwiedzonych, wpisując do jej komórek stan licznika DFS. Przejście DFS wyznaczy nam spójną składową, której elementem jest wierzchołek startowy. Wszystkie wierzchołki tej składowej będą posiadały w tablicy C tą samą wartość, równą zawartości licznika DFS. Gdy pętla główna zakończy działanie, graf zostanie podzielony na spójne składowe. Licznik DFS będzie zawierał informacje o liczbie tych składowych. Wystarczy teraz cyklicznie przeglądać tablicę C dla kolejnych wartości od 1 do licznika DFS i wypisywać numery wierzchołków, które w C posiadają taki numer - czyli należą do tej samej spójnej składowej.

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

Code::Blocks
// Wyszukiwanie spójnych składowych // za pomocą przejścia metodą DFS // Graf nieskierowany // (C)2011 mgr Jerzy Wałaszek //----------------------------- #include <iostream> #include <stack> #include <list> using namespace std; int main() { list<int> * A; // Tablica list sąsiedztwa grafu int * C; // Tablica numerów przejść DFS int n,m,i,j,v1,v2,licznikDFS; stack<int>S; // Stos dla DFS // Odczytujemy n i m cin >> n >> m; // Tworzymy tablicę n pustych list sąsiedztwa A = new list<int> [n]; // Wczytujemy poszczególne krawędzie i umieszczamy informację o nich na listach for(i = 0; i < m; i++) { cin >> v1 >> v2; // Odczytujemy krawędź od v1 do v2 A[v1].push_back(v2); // Do listy A[v1] dodajemy wierzchołek v2 A[v2].push_back(v1); // Do listy A[v2] dodajemy wierzchołek v1 } // Tworzymy dynamicznie tablicę numerów przejść DFS C = new int[n]; // Zerujemy tablicę C for(i = 0; i < n; i++) C[i] = 0; // Zerujemy licznik przejść DFS licznikDFS = 0; // Rozpoczynamy pętlę, która przechodzi przez kolejne wierzchołki grafu for(i = 0; i < n; i++) { if(!C[i]) // Rozpoczynamy od wierzchołka, który w C ma wartość 0. { licznikDFS++; // Zwiększamy licznik obiegów DFS S.push(i); // Na stosie umieszczamy wierzchołek startowy while(!S.empty()) // Rozpoczynamy obieg DFS { v1 = S.top(); S.pop(); // Pobieramy ze stosu wierzchołek if(!C[v1]) // Jeśli nie jest jeszcze odwiedzony, { C[v1] = licznikDFS; // to odwiedzamy go i umieszczamy na stosie wszystkich nieodwiedzonych sąsiadów for(list<int>::iterator it = A[v1].begin(); it != A[v1].end(); it++) if(!C[it]) S.push(it); } } } } // Podział na spójne składowe zakończony, teraz wypisujemy wierzchołki należące do kolejnych składowych for(i = 1; i <= licznikDFS; i++) { cout << endl << i << " : "; for(j = 0; j < n; j++) if(C[j] == i) cout << j << " "; } cout << endl << endl; // Usuwamy tablice dynamiczne z pamięci komputera delete [] C; delete [] A; return 0; }
7 9 0 2 0 3 0 5 1 4 1 6 2 3 2 5 3 5 4 6 1 : 0 2 3 5 2 : 1 4 6
Graf wyjściowy	Spójne składowe

Rozwiązania zadań 12...16 - DFS

Zadanie 12

Zadanie 13

Zadanie 14

Zadanie 15

Zadanie 16