Tässä opetusohjelmassa opit, mikä vierekkäisyysmatriisi on. Lisäksi löydät toimivia esimerkkejä vierekkäisyysmatriisista C, C ++, Java ja Python.
Rinnakkaismatriisi on tapa esittää graafi G = (V, E) boolean-matriisina.
Adjacency-matriisin esitys
Matriisin koko on VxVmissä Vgraafin pisteiden lukumäärä on ja merkinnän arvo Aijon joko 1 tai 0 riippuen siitä, onko kärjestä kärjestä i pisteeseen j.
Esimerkki adjacency Matrix -matriisista
Alla olevassa kuvassa on kaavio ja sen vastaava vierekkäisyysmatriisi.
Adjacency-matriisi kaaviosta
Suunnittelemattomien kaavioiden tapauksessa matriisi on symmetrinen diagonaalin suhteen jokaisen reunan takia (i,j), on myös reuna (j,i).
Plussat vierekkäisyysmatriisista
Perustoiminnot, kuten reunan lisääminen, reunan poistaminen ja tarkistus, onko kärjestä kärjestä i pisteeseen j, ovat erittäin aikatehokkaita, vakioaikaisia toimintoja.
Jos kaavio on tiheä ja reunojen määrä suuri, vierekkäisyysmatriisin tulisi olla ensimmäinen valinta. Vaikka kaavio ja vierekkäisyysmatriisi ovat harvat, voimme esittää sen käyttämällä harvojen matriisien tietorakenteita.
Suurin etu on kuitenkin matriisien käyttö. Laitteiston viimeaikainen kehitys antaa meille mahdollisuuden suorittaa jopa kalliita matriisitoimintoja GPU: lla.
Suorittamalla operaatioita viereiselle matriisille voimme saada tärkeitä oivalluksia kaavion luonteesta ja sen huippujen välisestä suhteesta.
Haitat vierekkäisyysmatriisista
VxVTilantarvetta vierusmatriisi tekee muistin sika. Luonnossa olevilla kaavioilla ei yleensä ole liikaa yhteyksiä, ja tämä on tärkein syy siihen, miksi vierekkäisyysluettelot ovat parempi valinta useimpiin tehtäviin.
Vaikka perustoiminnot ovat helppoja, toiminnot pitävät inEdgesja outEdgesovat kalliita, kun käytetään vierekkäisyysmatriisin esitystä.
Python-, Java- ja C / C ++ -esimerkkejä
Jos osaat luoda kaksiulotteisia taulukoita, osaat myös luoda vierekkäisyysmatriisin.
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(); )
Adjacency Matrix -sovellukset
- Reititystaulukon luominen verkoissa
- Navigointitehtävät
