Matrica susjedstva jedan je od načina prikaza grafa u memoriji.
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 .
Dan je graf i pripadajuća matrica susjedstva:
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; } }
Što možemo raditi s ovom matricom?
Ovaj članak objavljen je pod
Creative Commons Attribution-ShareAlike 3.0 Croatia License