Kodowanie Efektywnych Algorytmów - Ćwiczenia 8

Temat: Grafy

Grafy

Podczas zajęć zostanie zaprezentowane pojęcie grafu oraz definicje z nim związane. Później być może również tutaj pojawią się najważniejsze definicje związane z grafami.

Reprezentacje grafu

Omawiane reprezentacje grafu to:

Tablica krawędzi
Macierz incydencji
Tablica list krawędzi
Dwutablicowa reprezentacja

Przeszukiwanie grafu

BFS

Przeszukiwanie wszerz.

DFS

Przeszukiwanie wgłąb.

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]