Kodowanie Efektywnych Algorytmów - Ćwiczenia 6

Poprzednie Następne

Temat: Grafy

Grafy

Podczas zajęć zostanie zaprezentowane pojęcie grafu oraz definicje z nim związane.

Reprezentacje grafu

Omawiane reprezentacje grafu to:

Tablica krawędzi

Zalety:

Optymalna pamięciowo

Prosta do stworzenia (często wykorzystywana na wejściu zadań)

Wady:

Niemal niemożliwe przeszukiwanie grafu

Nie nadaje się do używania w praktyce

Macierz incydencji

Zalety:

Prosta i intuicyjna

Optymalna dla grafów pełnych ważonych (np. odległości między miastami)

Wady:

Zajmuje bardzo dużo pamięci

Dużo czasu zajmuje znalezienie sąsiadów wierzchołka

Tablica list krawędzi/sąsiadów

Zalety:

Szybko można znaleźć sąsiadów wierzchołka

Optymalna dla algorytmów grafowych

Dobra złożoność pamięciowa

Wady:

Oprogramowana na listach nie zawsze działa szybko

Dwutablicowa reprezentacja

Zalety:

Szybko można znaleźć sąsiadów wierzchołka

Natychmiast (O(1)) znajduje stopień wierzchołka

Optymalna dla algorytmów grafowych

Dobra złożoność pamięciowa

Działa dużo szybciej niż tablica list

Wady:

Nie można łatwo modyfikować grafu zapisanego w taki sposób

Nie nadaje się do reprezentacji grafów zmieniających się w czasie

Mapa

Zalety:

Bardzo prosta w użyciu

Nie trzeba stosować struktur grafowych

Szybka i optymalna

Wady:

Możliwa do zastosowania tylko w szczególnych przypadkach

Przeszukiwanie grafu

BFS

Przeszukiwanie wszerz, czyli kolejka.

DFS

Przeszukiwanie wgłąb, czyli stos.

Pomocne kody

Template do listy list

template < class V, class E > struct Graf {
  struct Edge : E {int v; Edge(E p, int w) : E(p), v(w) {}};
  struct Vertex : V,vector < Edge > {
  };
  vector < Vertex  > g;
  Graf(int n=0) : g(n) {}
  void AddEdge(int p, int k, E d) {
    Edge v(d,k);
    g[p].PB(v);
  }
  void AddEdge(int p, int k) {E d; AddEdge(p,k,d);}
}

struct Vs{int t,s;};
struct Ve{};
int main() {
  Graf < Vs,Ve > gr(n);

Przetwarzania tablicy krawędzi na dwutablicową reprezentację

  int n,m;
  int t[101], s[2001];

    cin >> n >> m;
    int i, dane[1001][2];

    for (i=0; i <=n; i++) t[i]=0;
    for (i=0; i < m; i++)
    {
      cin >> dane[i][1] >> dane[i][2];
      t[dane[i][1]+1]++;
      t[dane[i][2]+1]++;
    }

    t[1]=1;
    for (i=1; i < n; i++) t[i+1]+=t[i];

    for (i=0; i < m; i++)
    {
      s[t[dane[i][1]]++]=dane[i][2];
      s[t[dane[i][2]]++]=dane[i][1];
    }

    for (i=n+1; i > 0; i--) t[i+1]=t[i];
    t[1]=1;

Pętla przechodząca przez wszystkich sąsiadów wierzchołka x:

   for (i=t[x]; i < t[x+1]; i++) // sąsiadami są wierzchołki s[i]