Grafikon matrice susjedstva (s primjerima koda na C ++, Java i Python)

Sadržaj

Prikazivanje matrice susjedstva
Primjer matrice susjedstva
Prednosti matrice susjedstva
Protiv matrice susjedstva
Primjeri Pythona, Java i C / C ++
Primjene matrice susjedstva

U ovom vodiču naučit ćete što je matrica susjedstva. Također ćete naći radne primjere matrice susjedstva u C, C ++, Java i Python.

Matrica susjedstva način je predstavljanja grafa G = (V, E) kao matrice booleovih vrijednosti.

Prikazivanje matrice susjedstva

Veličina matrice je VxVgdje Vje broj vrhova na grafikonu, a vrijednost unosa Aijje 1 ili 0, ovisno o tome postoji li rub od vrha i do vrha j.

Primjer matrice susjedstva

Slika ispod prikazuje grafikon i njegovu ekvivalentnu matricu susjedstva.

Matrica susjedstva iz grafa

U slučaju neusmjerenih grafova, matrica je simetrična oko dijagonale, jer svaki rub (i,j)ima i rub (j,i).

Prednosti matrice susjedstva

Osnovne operacije poput dodavanja ruba, uklanjanja brida i provjere postoji li rub od vrha i do vrha j izuzetno su vremenski učinkovite i stalne vremenske operacije.

Ako je graf gust i broj rubova velik, matrica susjedstva trebala bi biti prvi izbor. Čak i ako su graf i matrica susjedstva rijetki, možemo ga prikazati pomoću struktura podataka za rijetke matrice.

Međutim, najveća prednost dolazi od upotrebe matrica. Nedavni napredak u hardveru omogućuje nam obavljanje čak i skupih operacija matrice na GPU-u.

Izvođenjem operacija na susjednoj matrici možemo dobiti važan uvid u prirodu grafa i odnos između njegovih vrhova.

Protiv matrice susjedstva

Zahtjev za VxVprostorom matrice susjedstva čini ga svinjskom memorijom. Grafovi u divljini obično nemaju previše veza i to je glavni razlog zašto su popisi susjedstva bolji izbor za većinu zadataka.

Iako su osnovne operacije jednostavne, operacije se sviđaju inEdgesi outEdgesskupe su kada se koristi prikaz matrice susjedstva.

Primjeri Pythona, Java i C / C ++

Ako znate kako stvoriti dvodimenzionalne nizove, također znate kako stvoriti matricu susjedstva.

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