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

Indholdsfortegnelse

Adjacency matrix repræsentation
Adjacency Matrix Eksempel
Fordele ved nærhedsmatrix
Ulemper ved nærhedsmatrix
Python, Java og C / C ++ eksempler
Adjacency Matrix-applikationer

I denne vejledning lærer du, hvad en nærhedsmatrix er. Du finder også arbejdseksempler på nærhedsmatrix i C, C ++, Java og Python.

En nærhedsmatrix er en måde at repræsentere en graf G = (V, E) som en matrix af booleanske.

Adjacency matrix repræsentation

Matrixens størrelse er VxVhvor Ver antallet af hjørner i grafen, og værdien af en post Aijer enten 1 eller 0 afhængigt af om der er en kant fra toppunkt i til toppunkt j.

Adjacency Matrix Eksempel

Billedet nedenfor viser en graf og dens ækvivalente nærhedsmatrix.

Adjacency matrix fra en graf

I tilfælde af ustyrede grafer er matrixen symmetrisk omkring diagonalen på grund af hver kant (i,j)er der også en kant (j,i).

Fordele ved nærhedsmatrix

De grundlæggende operationer som at tilføje en kant, fjerne en kant og kontrollere, om der er en kant fra toppunkt i til toppunkt j, er ekstremt tidseffektive, konstante tidsoperationer.

Hvis grafen er tæt, og antallet af kanter er stort, bør nærhedsmatrix være det første valg. Selvom grafen og nærhedsmatrixen er sparsom, kan vi repræsentere den ved hjælp af datastrukturer til sparsomme matricer.

Den største fordel kommer dog fra brugen af matricer. De seneste fremskridt inden for hardware gør det muligt for os at udføre endnu dyre matrixoperationer på GPU'en.

Ved at udføre operationer på den tilstødende matrix kan vi få vigtig indsigt i karakteren af grafen og forholdet mellem dens hjørner.

Ulemper ved nærhedsmatrix

Den VxVpladsbehov af nabomatricen gør det en hukommelse hog. Grafer ude i naturen har normalt ikke for mange forbindelser, og dette er hovedårsagen til, at nærhedslister er det bedre valg for de fleste opgaver.

Mens grundlæggende operationer er lette, er operationer ligesom inEdgesog outEdgesdyre, når de bruger nærhedsmatrixrepræsentation.

Python, Java og C / C ++ eksempler

Hvis du ved, hvordan du opretter todimensionale arrays, ved du også, hvordan du opretter en nærhedsmatrix.

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