Grafiko adjacency matrica (su kodų pavyzdžiais C ++, Java ir Python)

Turinys

Adjacency matricos vaizdavimas
Žlugimo matricos pavyzdys
Gretutinės matricos pliusai
Gretutinės matricos minusai
„Python“, „Java“ ir „C / C ++“ pavyzdžiai
Gretutinės matricos programos

Šioje pamokoje sužinosite, kas yra gretimybės matrica. Taip pat rasite veikiančių gretimybių matricos pavyzdžių C, C ++, Java ir Python.

Gretimybės matrica yra būdas pavaizduoti grafiką G = (V, E) kaip loginių elementų matricą.

Adjacency matricos vaizdavimas

Matricos dydis yra VxVkur Vviršūnių skaičius grafike, o įrašo vertė Aijyra 1 arba 0, atsižvelgiant į tai, ar yra kraštas nuo i viršūnės iki viršūnės j.

Žlugimo matricos pavyzdys

Žemiau pateiktame paveikslėlyje parodytas grafikas ir jo ekvivalentinė gretimumo matrica.

Adjacency matrica iš grafiko

Nenukreiptų grafikų atveju matrica yra simetriška įstrižai dėl kiekvieno krašto (i,j), yra ir kraštas (j,i).

Gretutinės matricos pliusai

Pagrindinės operacijos, tokios kaip krašto pridėjimas, krašto pašalinimas ir patikrinimas, ar yra kraštas nuo i viršūnės iki viršūnės j, yra nepaprastai efektyvios, pastovaus laiko operacijos.

Jei grafikas yra tankus ir briaunų skaičius didelis, gretimybių matrica turėtų būti pirmas pasirinkimas. Net jei grafikas ir gretimumo matrica yra nedaug, mes galime jį pavaizduoti naudodami retų matricų duomenų struktūras.

Vis dėlto didžiausią pranašumą suteikia matricų naudojimas. Naujausi aparatinės įrangos laimėjimai leidžia mums atlikti net brangias matricos operacijas GPU.

Atlikdami operacijas gretimoje matricoje, galime gauti svarbių įžvalgų apie grafiko pobūdį ir santykį tarp jo viršūnių.

Gretutinės matricos minusai

Dėl VxVgretimos matricos reikalaujančio vietos ji tampa atminties kiaulaite. Gamtoje esančiuose grafikuose paprastai nėra per daug ryšių, ir tai yra pagrindinė priežastis, kodėl gretimybių sąrašai yra geresnis pasirinkimas daugeliui užduočių.

Nors pagrindinės operacijos yra lengvos, operacijos patinka inEdgesir outEdgesyra brangios, kai naudojama gretimumo matricos reprezentacija.

„Python“, „Java“ ir „C / C ++“ pavyzdžiai

Jei žinote, kaip sukurti dviejų matmenų masyvus, taip pat žinote, kaip sukurti gretimumo matricą.

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