Graph Adjacency Matrix (Med kodeeksempler i C ++, Java og Python)

I denne opplæringen lærer du hva en tilknytningsmatrise er. Du finner også arbeidseksempler på nærliggende matrise i C, C ++, Java og Python.

En tilknytningsmatrise er en måte å representere en graf G = (V, E) som en matrise av boolere.

Adjacency matrix representasjon

Matrisens størrelse er VxVhvor Ver antall hjørner i grafen, og verdien av en oppføring Aijer enten 1 eller 0, avhengig av om det er en kant fra toppunkt i til toppunkt j.

Adjacency Matrix Eksempel

Bildet nedenfor viser en graf og dens tilsvarende tilstøtende matrise.

Tilstøtningsmatrise fra en graf

I tilfelle ikke-rettede grafer er matrisen symmetrisk rundt diagonalen på grunn av hver kant (i,j), det er også en kant (j,i).

Fordeler med tilknytningsmatrise

De grunnleggende operasjonene som å legge til en kant, fjerne en kant og kontrollere om det er en kant fra toppunkt i til toppunkt j er ekstremt tidseffektive, konstant tidsoperasjoner.

Hvis grafen er tett og antall kanter er stort, bør nærhetsmatrise være førstevalget. Selv om grafen og nærhetsmatrisen er sparsom, kan vi representere den ved hjelp av datastrukturer for sparsomme matriser.

Den største fordelen kommer imidlertid fra bruk av matriser. De siste fremskrittene innen maskinvare gjør at vi kan utføre enda dyre matriseoperasjoner på GPU-en.

Ved å utføre operasjoner på den tilstøtende matrisen kan vi få viktig innsikt i grafens natur og forholdet mellom toppunktene.

Ulemper med tilknytningsmatrise

Den VxVplassbehov av nabomatrisen gjør det et minne hog. Grafer ute i naturen har vanligvis ikke for mange forbindelser, og dette er den viktigste grunnen til at nærliggende lister er det bedre valget for de fleste oppgaver.

Selv om grunnleggende operasjoner er enkle, er operasjoner som inEdgesog outEdgeser dyre når du bruker matriserepresentasjonen.

Python, Java og C / C ++ eksempler

Hvis du vet hvordan du lager todimensjonale matriser, vet du også hvordan du lager en nærliggende matrise.

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(); )