Graph Adjacency Matrix (med kodexempel i C ++, Java och Python)

Innehållsförteckning

Adjacency matrix representation
Adjacency Matrix Exempel
Fördelar med angränsande matris
Nackdelar med angränsande matris
Python, Java och C / C ++ exempel
Adjacency Matrix Applications

I denna handledning lär du dig vad en angränsningsmatris är. Du hittar också arbetsexempel på angränsningsmatris i C, C ++, Java och Python.

En angränsande matris är ett sätt att representera en graf G = (V, E) som en matris av booléer.

Adjacency matrix representation

Matrisens storlek är VxVvar Vär antalet hörn i grafen och värdet på en post Aijär antingen 1 eller 0 beroende på om det finns en kant från toppunkt i till toppunkt j.

Adjacency Matrix Exempel

Bilden nedan visar ett diagram och dess motsvarande angränsningsmatris.

Adjacency-matris från ett diagram

Vid oriktade grafer är matrisen symmetrisk kring diagonalen på grund av varje kant (i,j), det finns också en kant (j,i).

Fördelar med angränsande matris

De grundläggande operationerna som att lägga till en kant, ta bort en kant och kontrollera om det finns en kant från vertex i till vertex j är extremt tidseffektiva, konstanta tidsoperationer.

Om diagrammet är tätt och antalet kanter är stort bör angränsningsmatrisen vara förstahandsvalet. Även om grafen och angränsningsmatrisen är gles, kan vi representera den med hjälp av datastrukturer för glesa matriser.

Den största fördelen kommer dock från användningen av matriser. De senaste framstegen inom hårdvara gör det möjligt för oss att utföra ännu dyra matrisoperationer på GPU: n.

Genom att utföra operationer på intilliggande matris kan vi få viktiga insikter i grafens karaktär och förhållandet mellan dess hörn.

Nackdelar med angränsande matris

Den VxVutrymmesbehov i grannmatris gör det till ett minne hog. Grafer ute i naturen har vanligtvis inte för många anslutningar och det här är den främsta anledningen till att närliggande listor är det bättre valet för de flesta uppgifter.

Medan grundläggande operationer är enkla, är operationer som inEdgesoch outEdgesär dyra när du använder närliggande matrisrepresentation.

Python, Java och C / C ++ exempel

Om du vet hur du skapar tvådimensionella matriser vet du också hur man skapar en angränsningsmatris.

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