Matrica susjedstva

Matrica susjedstva jedan je od načina prikaza grafa u memoriji.

Definicija

Jednostavan graf netežinski je, neusmjereni graf u kojem brid spaja dva različita vrha. Ne postoji više bridove između dva ista vrha.

Zadan je jednostavan graf čije vrhove (skup ) možemo poredati u niz. Neka je broj vrhova i označimo ih sa . Matrica susjedstva dimenzija dana je formulom po članovima:

Odnosno riječima, matrica susjedstva je kvadratna matrica sa , u kojoj na mjestu piše ako postoji brid koji spaja vrh i .

Primjer

Dan je graf i pripadajuća matrica susjedstva:

_anonymous_011221--2331--32--3442--43--4

Svojstva

Implementacija

Matricu susjedstva pamtimo kao polje. Ovaj isječak prikazuje učitavanje neusmjerenog grafa. Dolazi u obzir umjesto int tipa podataka koristiti bool radi uštede memorije. Isto tako, u C++ jeziku koristili bi vector i cin.

int N, graph[maxn][maxn];

void load() {
  int m, a, b;
  scanf("%d%d", &N, &m);
  for (int i = 0; i < m; ++i) {
    scanf("%d%d", &a, &b);
    --a; --b;
    graph[a][b] = graph[b][a] = 1;
  }
}

Nastavak čitanja

Što možemo raditi s ovom matricom?

© 2014. Anton Grbin Creative Commons License

Ovaj članak objavljen je pod
Creative Commons Attribution-ShareAlike 3.0 Croatia License