Grafy -- praktyka

10.11.2009
Trudność

Graf, to pojęcie, które jest fundamentalne dla wymyślenia rozwiązania i zaimplementowania większości olimpijskich zadań.

Jak wiemy z części teoretycznej graf powinien mieć zbiór wierzchołków i zbiór krawędzi. W praktyce jednak, przyjmujemy, że wierzchołki nazywają się od 0 do n-1, i nie musimy nigdzie pamiętać ich zbioru, a jedynie pamiętać, że jest ich n.
Graf powinien mieć też krawędzi i tu sprawa się mocno komplikuje. Teoria mówi tylko, że mamy o E myśleć jak o zbiorze par. Gdyby tę intuicję chcieć bezpośrednio przenieść do C++, to należałoby zdefiniować zbiór krawędzi jakoś tak:

set< pair<int,int> >  E;

Typ set nie pojawił się na zajęciach, ale jak sama nazwa wskazuje reprezentuje zbiory, wraz z ich podstawowymi funkcjami takimi jak: sprawdź czy coś należy, dodaj, usuń element.

W praktyce jednak, okazuje się, że większość algorytmów operujących na grafach potrzebuje mieć w miarę wygodny dostęp do tak zwanej listy sąsiedztwa dowolnego wierzchołka. Lista sąsiedztwa, to jak nazwa wskazuje, lista sąsiadów jakiegoś wierzchołka. A więc przykładowo jeśli E={ (1,2),(2,3),(2,4) } , to lista sąsiedztwa wierzchołka 2 to {3,4}. Wierzchołek 1 co prawda sąsiaduje z 2, ale, że przykładowy graf jest skierowany, (a relacja niesymetryczna), to nie występuje on na tej liście. Czasem mówi się o dwóch zbiorach krawędzi : wchodzących do x oraz wychądzących z x. Przykładowo zbiór krawędzi wchodzących do 2 to {1}, zaś wychodzących z 4 jest pusty, czyli {}. Podobnie jak mówi się o dwóch zbiorach krawędzi, mówi się też o stopniach: stopniu wejściowym i wyjściowym. Stopień wejściowy to liczba krawędzi, które wchodzą do wierzchołka, a wyjściowy to odpowiednio -- rozmiar zbioru krawędzi wychodzących z niego. Jako, że częściej chodzi się po grafie "w przód", czyli "zgodnie ze strzałkami", wygodnie jest pamiętać sobie każdą krawędź tam skąd ona wychodzi, a więc wygodnie jest pogrupować sobie zbiór E w mniejsze podzbiory, stanowiące zbiory krawędzi wychodzących z poszczególnych wierzchołków. Przykładowo zbiór E podzielilibyśmy na krawędzie wychodzące z 1, czyli {(1,2)}, oraz na krawędzie wychodzące z 2, a więc {(2,3),(2,4)}. Takie spojrzenie na zbiór E, bezpośrednio tłumaczyłoby się w STLu na coś takiego:

vector< set<pair<int,int> >   > listy_sasiedztwa;


Innymi słowy, chcemy mieć tablicę indeksowaną etykietami wierzchołków, taką, że w listy_sasiedztwa[1] znajdzie sie lista sasiadow wierzcholka 1, a wiec zbiór krawędzi z niego wychodzących.
W praktyce jednak, używanie set'a nie bardzo ma sens, gdyż niezwykle rzadko korzystamy ze zbioru sąsiadów w sposób wymagający operacji "sprawdź czy należy", czy też "usuń element".
W praktyce też, nie ma sensu pamiętać pierwszego elementu każdej pary, bo przecież wiemy, że krawędzie wychodzące z 1, wychodzą z 1.
W praktyce, graf pamiętamy więc tak:

vector< vector< int > > listy_sasiedztwa;


W ten sposób listy_sasiedztwa[1] jest wektorem ktory pamieta tylko dokąd da się dojść z 1.

Często w zadaniach krawędzie oprócz tego, że mają dwa końce, mają też jakąś wagę. Formalnie waga, to funkcja, która dla każdej krawędzi umie podać jej wagę. Tłumcząc to bezpośrodnio na STL uzyskalibyśmy coś w stylu:

map< pair<int,int> , int >  waga;


Typ map również nie pojawił się na zajęciach, ale jak sama nazwa wskazuje służy do mapowania (a więc: tłumaczenia, przyporządkowywania) jednych elementów na inne. Np. powyższa mapa, przyporządkowuje krawędziom liczby. Typ map również nie jest nam potrzebny na razie do szczęścia, bo podobnie jak to ma miejsce z samymi krawędziami, tak i z ich wagami -- najwygodniej jest trzymać je od razu na liście sąsiedztwa. Innymi słowy: zamiast pamiętać tylko dokąd prowadzi krawędź, będziemy pamiętać też jaką ma wagę. Czyli jakoś tak:

vector< vector< pair<int,double> > > listy_sasiedztwa;



Jak widać zmienił się tylko typ krawędzi. Wygodnym sposobem poradzenia sobie ze skomplikowanymi typami jest rozbicie ich na mniejsze, dające się ogarnąć i nazwać. Służy do tego typedef. Składnie itd znajdziecie sobie w internecie, nam chyba wystarczy przykład:

typedef double weight;
typedef pair<int,weight> edge;
typedef vector<edge> node;
typedef vector<node> graph;

graf g;

Powyższy kawałek kodu definiuje type edge, jako parę : cel i waga. Wagę definiuje jako double. Wierzchołek definiujemy jako liste krawedzi która z niego wychodzi (bo często nic więcej o nim wiedzieć nie musimy), w reszcie graf to tablica wierzchołków.

Zależnie od zastosowania, czasem niektóre elementy tej układanki mogą przybierać inną postać. Np. jeśli wagi na krawędziach są liczbami naturalnymi to powinniśmy mieć:

typedef int weight;

Jeśli zaś bardziej lubimy listy niż wektory, to możemy zdefiniować listę sąsiedztwa inaczej:

typedef list<edge> node;

Czy wreszcie jeśli wierchołki nazywają się nie {0,...,(n-1)} tylko np. {"Wrocław","Zielona Góra"...} itp, to możemy mieć :

typedef double weight;
typedef pair<string,weight> edge;
typedef vector<edge> node;
typedef map<string, node> graph;


Z całego ogromu dostępnych zabawek jakie daje STL niewątpliwie do algorytmów grafowych przydają się następujące:

vector
pair
queue
priority_queue
greater
less

Na zajęciach zapoznaliśmy się pokrótce z typowym "szablonem" programu, który rozwiązuje problem grafowy:

#include<vector>//potrzebny do wygodnego manipulowania tablicami/zbiorami/listami
#include<iostream>//potrzebny do wygodnego czytania i pisania
#include<algorithm>//często potrzebny
using namespace std;//wrzuca wszystko z przestrzeni nazw std, do tej w której akurat jesteśmy (globalnej), abyśmy nie musieli pisać std::cin, tylko cin
typedef double weight;//definicja typu wagi krawędzi
typedef pair<int,weight> edge;//definicja pojęcia krawędzi
typedef vector<edge> node;//definicja pojęcia wierzchołka (czy też: listy sąsiedztwa)
typedef vector<node> graph;//definicja pojecia grafu

void single_test(){ //funkcja rozwiązująca jeden test (często jedno uruchomienie musi rozwiązać kilka testów)
  int n,m;//liczba wierzchołków i krawędzi
  cin >> n >> m;//wczytanie tychże
  graph g(n,node());//zadeklarowanie (zdefiniowanie) zmiennej g, która będzie grafem, mającym n wierzchołków, każdy z nich o pustej liście sąsiedztwa
  while(m--){//m razy
    int u,v;//skąd dokąd
    weight c;//ile waży
    cin >> u >> v >> c;//wczytaj skąd dokąd jest i ile waży krawędź
    g[u].push_back(edge(v,c));//dodaj krawędź na koniec listy sąsiedztwa wierzchołka u
  }

  solve(g);//tutaj rozwiązujemy problem dotyczący grafu g
}
int main(){//główna funkcja całego programu, teoretycznie powinna zwracać liczbę 0, ale to nie jest potrzebne tak naprawdę
  int t;//liczba przypadków testowych
  cin >> t;//wczytanie tejże
  while(t--){//dla każdego testu
    single_test();//rozwiąż go
  }
}


Poznaliśmy też przykład algorytmu grafowego, rozwiązujący problem znajdowania najkrótszej ścieżki w nieważonym grafie skierowanym (czyli wszystkie krawędzie mają długość 1).
Algorytm nazywa się BFS i na pewno jest o nim dużo w sieci.
Dla grafów, w których wagi na krawędziach nie są potrzebne, rzecz jasna przydaje się inna definicja typu edge, np. taka:

typedef int edge;

A co za tym idzie wczytywanie grafu również wygląda wtedy nieco inaczej:

  while(m--){//m razy
    int u,v;//skąd dokąd
    cin >> u >> v;//wczytaj skąd dokąd jest krawędź
    g[u].push_back(v);//dodaj krawędź na koniec listy sąsiedztwa wierzchołka u
  }

Algorytm BFS wygląda mniej więcej tak:

  • włóż do kolejki wierzchołek startowy
  • dopóki kolejka jest niepusta
    • wyjmij z kolejki jakiś wierzchołek
    • oznacz go jako odwiedzony
    • dla każdego z jego sąsiadów
      • jeśli nie był odwiedzony, to dodaj go do kolejki

Pisze "mniej więcej", bo tak naprawdę powyższy algorytm ma buga i wkłada ten sam wierchołek po kilka razy do kolejki. Tak naprawdę bardziej niż to czy wierzchołek był odwiedzony interesuje nas bowiem, czy był już wrzucony do kolejki. A zatem prawdziwa implementacja wygląda jakoś tak:

void BFS(graph & g,int start){
  queue q;
  vector<bool> pushed(g.size(),false);
  q.push(start);
  pushed[start]=true;
  while(!q.empty()){
     const int v=q.top();
     q.pop();
     for(int i=g[v].size();i--;){
      const int u=g[v][i];
      if(!pushed[u]){
        q.push(u);
        pushed[u]=true;
      }
     }
  }
}


Algorytm zdefiniowany tak jak powyżej, w zasadzie niewiele robi i niczego nie zwraca (void).
Potrzebuje kolejki FIFO, czyli takiej, że kolejność wyciąganych elementów jest zgodna z kolejnością ich wsadzania.
Potrzebuje też tablicy pushed, aby zapamiętać sobie które wierzchołki były już wepchnięte do kolejki a które nie.

Ten prosty algorytm można łatwo przerobić tak, aby znajdował odległość miedzy dwoma zadanymi wierzchołkami start i end.

const int INF=0x7FFFFFFF
;
int distance(graph & g,int start,int end){
  queue q;
  vector<int> d(g.size(),INF);
  q.push(start);
  d[start]=0;
  while(!q.empty()){
     const int v=q.top();
     q.pop();
     for(int i=g[v].size();i--;){
      const int u=g[v][i];
      if(d[v]+1<d[u]){
        q.push(u);
        d[u]=d[v]+1;
      }
     }
  }
  return d[end];
}


Czasem warto zrobić return d[end] od razu jak tylko okaże się, że v==end, ale z teoretycznego punktu widzenia, nie poprawia to szybkości algorytmu dla najtrudniejszych testów, a stanowi ryzyko napisania czegoś błędnie.
Czasem też nie warto sprawdzać czy d[v]+1<d[u], bo tak naprawdę wystarczy sprawdzić, to samo czy poprzednio -- czyli czy wierzchołek nie był jeszcze wpychany do kolejki. Wystarczyłby więc if(INF!=d[u]).
Czasem w ogóle jest tak, że nie interesują nas dystanse do innych wierzchołków niż end, i taniej jest mieć tylko tablicę pushed.
Wymaga to pewnego tricku:

int distance(graph & g,int start,int end){
  queue q;
  vector<bool> pushed(g.size(),false);
  q.push(start);
  pushed[start]=true;
  int now=1;
  int then=0;
  int dist=0;
  while(!q.empty()){
     const int v=q.top();
     q.pop();
     if(v==end){
       return dist;
     }
     if(!--now){
       now=then;
       then=0;
       ++dist;
     }
     for(int i=g[v].size();i--;){
      const int u=g[v][i];
      if(!pushed[u]){
        q.push(u);
        pushed[u]=true;
        ++then;
      }
     }
  }
  return d[end];
}


Oszczędność jakaś tam jest (bool zajmuje mniej miejsca niż int), ale pisaniny więcej a i o błąd łatwiej.

Znajdowanie najkrótszej ścieżki w nieważonym grafie skierowanym, do najciekawszych zajęć może nie należy, ale algorytm BFS jest często podstawą na bazie, której powstają bardziej skomplikowane algorytmy, warto więc dobrze rozumieć dlaczego on działa.
Warto też, umieć go zaimplementować.
Niestety BFS jest tak prosty, że nie widzę zadania na themisie które wymagałoby tylko i wyłacznie BFS. Natomiast zadanie "2KRO" jest akurat na bardzo prostą modyfikację BFSa, więc proszę je rozwiązać.

Snippet icon

Zdefiniuj używając typedef typy graph, node i edge, tak aby poniższy kawałek kodu działał:

1
2
3
4
graph g(11,node());
for(int i=0;i<10;++i){
  g[i].push_back(edge(i-1,3.14));
}

Snippet icon

Zdefiniuj używając typedef typy graph, node i edge, tak aby poniższy kawałek kodu działał:

1
2
3
4
5
graph g;
for(int i=0;i<10;++i){
  g[i].insert(edge(i-1,3.14));
  g[i].insert(edge(i-1,1.11));
}

Snippet icon

Zdefiniuj używając typedef typy graph, node, edge, tak aby poniższy kawałek kodu działał:

1
2
3
4
5
graph g;
for(int i=0;i<10;++i){
  g[i][i-1]=3.14;
  g[i-1][i]=1.11;
}

4
Twoja ocena: Brak Ocena: 4 (1 ocena)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com