In questo tutorial imparerai cos'è una matrice di adiacenza. Inoltre, troverai esempi funzionanti di matrice di adiacenza in C, C ++, Java e Python.
Una matrice di adiacenza è un modo per rappresentare un grafo G = (V, E) come una matrice di valori booleani.
Rappresentazione in matrice di adiacenza
La dimensione della matrice è VxVdove Vè il numero di vertici nel grafico e il valore di una voce Aijè 1 o 0 a seconda che ci sia un bordo dal vertice i al vertice j.
Esempio di matrice di adiacenza
L'immagine sotto mostra un grafico e la sua matrice di adiacenza equivalente.
Matrice di adiacenza da un grafico
In caso di grafici non orientati, la matrice è simmetrica rispetto alla diagonale a causa di ogni bordo (i,j), c'è anche un bordo (j,i).
Pro della matrice di adiacenza
Le operazioni di base come l'aggiunta di un bordo, la rimozione di un bordo e il controllo della presenza di un bordo dal vertice i al vertice j sono operazioni estremamente efficienti in termini di tempo e costanti.
Se il grafico è denso e il numero di bordi è grande, la matrice di adiacenza dovrebbe essere la prima scelta. Anche se il grafico e la matrice di adiacenza sono sparsi, possiamo rappresentarli utilizzando strutture dati per matrici sparse.
Il vantaggio più grande, tuttavia, deriva dall'uso delle matrici. I recenti progressi nell'hardware ci consentono di eseguire anche costose operazioni di matrice sulla GPU.
Eseguendo operazioni sulla matrice adiacente, possiamo ottenere importanti informazioni sulla natura del grafo e sulla relazione tra i suoi vertici.
Contro della matrice di adiacenza
Il VxVrequisito di spazio della matrice di adiacenza lo rende un maiale di memoria. I grafici in circolazione di solito non hanno troppe connessioni e questo è il motivo principale per cui gli elenchi di adiacenza sono la scelta migliore per la maggior parte delle attività.
Mentre le operazioni di base sono facili, le operazioni come inEdgese outEdgessono costose quando si utilizza la rappresentazione della matrice di adiacenza.
Esempi di Python, Java e C / C ++
Se sai come creare array bidimensionali, sai anche come creare una matrice di adiacenza.
Python Java C C + # Adjacency Matrix representation in Python class Graph(object): # Initialize the matrix def __init__(self, size): self.adjMatrix = () for i in range(size): self.adjMatrix.append((0 for i in range(size))) self.size = size # Add edges def add_edge(self, v1, v2): if v1 == v2: print("Same vertex %d and %d" % (v1, v2)) self.adjMatrix(v1)(v2) = 1 self.adjMatrix(v2)(v1) = 1 # Remove edges def remove_edge(self, v1, v2): if self.adjMatrix(v1)(v2) == 0: print("No edge between %d and %d" % (v1, v2)) return self.adjMatrix(v1)(v2) = 0 self.adjMatrix(v2)(v1) = 0 def __len__(self): return self.size # Print the matrix def print_matrix(self): for row in self.adjMatrix: for val in row: print('(:4)'.format(val)), print def main(): g = Graph(5) g.add_edge(0, 1) g.add_edge(0, 2) g.add_edge(1, 2) g.add_edge(2, 0) g.add_edge(2, 3) g.print_matrix() if __name__ == '__main__': main()
// Adjacency Matrix representation in Java public class Graph ( private boolean adjMatrix()(); private int numVertices; // Initialize the matrix public Graph(int numVertices) ( this.numVertices = numVertices; adjMatrix = new boolean(numVertices)(numVertices); ) // Add edges public void addEdge(int i, int j) ( adjMatrix(i)(j) = true; adjMatrix(j)(i) = true; ) // Remove edges public void removeEdge(int i, int j) ( adjMatrix(i)(j) = false; adjMatrix(j)(i) = false; ) // Print the matrix public String toString() ( StringBuilder s = new StringBuilder(); for (int i = 0; i < numVertices; i++) ( s.append(i + ": "); for (boolean j : adjMatrix(i)) ( s.append((j ? 1 : 0) + " "); ) s.append(""); ) return s.toString(); ) public static void main(String args()) ( Graph g = new Graph(4); g.addEdge(0, 1); g.addEdge(0, 2); g.addEdge(1, 2); g.addEdge(2, 0); g.addEdge(2, 3); System.out.print(g.toString()); ) )
// Adjacency Matrix representation in C #include #define V 4 // Initialize the matrix to zero void init(int arr()(V)) ( int i, j; for (i = 0; i < V; i++) for (j = 0; j < V; j++) arr(i)(j) = 0; ) // Add edges void addEdge(int arr()(V), int i, int j) ( arr(i)(j) = 1; arr(j)(i) = 1; ) // Print the matrix void printAdjMatrix(int arr()(V)) ( int i, j; for (i = 0; i < V; i++) ( printf("%d: ", i); for (j = 0; j < V; j++) ( printf("%d ", arr(i)(j)); ) printf(""); ) ) int main() ( int adjMatrix(V)(V); init(adjMatrix); addEdge(adjMatrix, 0, 1); addEdge(adjMatrix, 0, 2); addEdge(adjMatrix, 1, 2); addEdge(adjMatrix, 2, 0); addEdge(adjMatrix, 2, 3); printAdjMatrix(adjMatrix); return 0; )
// Adjacency Matrix representation in C++ #include using namespace std; class Graph ( private: bool** adjMatrix; int numVertices; public: // Initialize the matrix to zero Graph(int numVertices) ( this->numVertices = numVertices; adjMatrix = new bool*(numVertices); for (int i = 0; i < numVertices; i++) ( adjMatrix(i) = new bool(numVertices); for (int j = 0; j < numVertices; j++) adjMatrix(i)(j) = false; ) ) // Add edges void addEdge(int i, int j) ( adjMatrix(i)(j) = true; adjMatrix(j)(i) = true; ) // Remove edges void removeEdge(int i, int j) ( adjMatrix(i)(j) = false; adjMatrix(j)(i) = false; ) // Print the martix void toString() ( for (int i = 0; i < numVertices; i++) ( cout << i << " : "; for (int j = 0; j < numVertices; j++) cout << adjMatrix(i)(j) << " "; cout << ""; ) ) ~Graph() ( for (int i = 0; i < numVertices; i++) delete() adjMatrix(i); delete() adjMatrix; ) ); int main() ( Graph g(4); g.addEdge(0, 1); g.addEdge(0, 2); g.addEdge(1, 2); g.addEdge(2, 0); g.addEdge(2, 3); g.toString(); )
Applicazioni della matrice di adiacenza
- Creazione della tabella di instradamento nelle reti
- Attività di navigazione
