Matrice di Adiacenza - Rappresentazione di un Grafo
Un grafo è una struttura composta da vertici (nodi) e archi che collegano tali vertici. I grafi possono essere utilizzati per modellare relazioni tra oggetti o per rappresentare una rete. Spesso vengono impiegati per descrivere i collegamenti tra città, persone o anche entità astratte.
I grafi possono essere diretti oppure non diretti:
- Grafi diretti: Tutti gli archi hanno una direzione, il che significa che esiste una “strada” da un vertice a un altro e non è detto che ci sia il verso opposto. È simile a una strada a senso unico.
Yet, it’s possible to have both directions in a directed graph. They are just explicitly marked for that (the connection between vertices 5 and 8 in the graph).
- Grafi non diretti: Gli archi non hanno alcuna direzione, il che implica che se esiste un arco tra due vertici, questi risultano collegati tra loro in entrambi i versi.
Uno dei modi per rappresentare un grafo è attraverso la Matrice di Adiacenza. Si tratta di una matrice quadrata che rappresenta l’intero grafo. Ogni riga e colonna della matrice corrisponde a un vertice del grafo. Se esiste un arco tra due vertici, l’elemento corrispondente nella matrice viene impostato a 1. Altrimenti, è pari a 0.
Ecco un esempio di matrice di adiacenza per il grafo diretto sopra descritto:
g = [
# 1 2 3 4 5 6 7 8
[0, 1, 0, 1, 0, 0, 0, 0], # connessioni in uscita dal vertice 1
[0, 0, 0, 0, 1, 0, 0, 0], # connessioni in uscita dal vertice 2
[0, 1, 0, 0, 0, 0, 0, 0], # connessioni in uscita dal vertice 3
[0, 0, 0, 0, 0, 0, 0, 0], # connessioni in uscita dal vertice 4
[0, 0, 0, 0, 0, 1, 0, 1], # connessioni in uscita dal vertice 5
[0, 0, 0, 1, 0, 0, 1, 0], # connessioni in uscita dal vertice 6
[0, 0, 0, 0, 0, 0, 0, 1], # connessioni in uscita dal vertice 7
[0, 0, 0, 0, 1, 0, 0, 0], # connessioni in uscita dal vertice 8
]Si noti che, in caso di arco bidirezionale, entrambi i vertici avranno il valore 1 nelle rispettive posizioni.
Inoltre, vale la pena osservare che abbiamo modificato la numerazione dei vertici. Di conseguenza, se accediamo a
g[0], in realtà otteniamo tutte le connessioni del nodo con indice 1. Avremmo potuto usare 9 righe e 9 colonne invece di 8, mantenendo una corrispondenza uno a uno tra i numeri nell’immagine e gli indici nella matrice g, ma la scelta dipende esclusivamente da voi 😎.Sfida: Da Archi a Matrice di Adiacenza
Dato un grafo con
v vertici e e archi, l’obiettivo è costruirne la matrice di adiacenza.Input
La prima riga di input contiene due interi
v (1 ≤ v ≤ 1000) ed e (1 ≤ e ≤ 100 000).Le successive
e righe contengono coppie di interi v1, v2 (1 ≤ v1, v2 ≤ v), indicando che il vertice v1 è collegato al vertice v2 e viceversa.Output
Il programma deve stampare la matrice di adiacenza corrispondente al grafo fornito in ingresso. I valori in ciascuna riga devono essere separati da uno spazio.
Esempi
Input | Output |
8 9
1 4
4 6
3 2
2 1
5 2
5 6
8 5
7 6
7 8 | 0 1 0 1 0 0 0 0
1 0 1 0 1 0 0 0
0 1 0 0 0 0 0 0
1 0 0 0 0 1 0 0
0 1 0 0 0 1 0 1
0 0 0 1 1 0 1 0
0 0 0 0 0 1 0 1
0 0 0 0 1 0 1 0 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 5 MB