Šajā apmācībā jūs uzzināsiet, kas ir blakus esošā matrica. Jūs atradīsit arī blakus esošu matricu piemērus C, C ++, Java un Python.
Blakus matrica ir veids, kā attēlot grafiku G = (V, E) kā Būla matricu.
Blakusparādības matricas attēlojums
Matricas lielums ir VxVkur Vvirsotņu skaits diagrammā, un ieraksta vērtība Aijir vai nu 1, vai 0 atkarībā no tā, vai ir virsotne no i virsotnes līdz virsotnei j.
Blakusparādību matricas piemērs
Zemāk redzamajā attēlā redzams grafiks un tam līdzvērtīga blakus esošā matrica.
Adjacences matrica no grafika
Nenovirzītu grafiku gadījumā matrica ir simetriska attiecībā pret diagonāli katras malas dēļ (i,j), ir arī mala (j,i).
Blakus esošās matricas plusi
Pamata darbības, piemēram, malas pievienošana, malas noņemšana un pārbaude, vai no virsotnes i līdz virsotnei j ir mala, ir ārkārtīgi efektīvas, nemainīga laika operācijas.
Ja grafiks ir blīvs un malu skaits ir liels, blakus izvēles matricai jābūt pirmajai izvēlei. Pat ja grafiks un blakusesības matrica ir reti, mēs to varam attēlot, izmantojot retu matricu datu struktūras.
Lielākā priekšrocība tomēr ir matricu izmantošana. Nesenie aparatūras sasniegumi ļauj mums veikt pat dārgas matricas darbības GPU.
Veicot operācijas blakus esošajā matricā, mēs varam gūt svarīgu ieskatu par grafika būtību un attiecībām starp tā virsotnēm.
Blakus esošās matricas mīnusi
Blakus VxVesošās matricas nepieciešamība pēc vietas padara to par atmiņu. Savvaļas grafikiem parasti nav pārāk daudz savienojumu, un tas ir galvenais iemesls, kāpēc blakus esošie saraksti ir labāka izvēle lielākajai daļai uzdevumu.
Lai gan pamatdarbības ir vienkāršas, operācijām patīk inEdgesun tās outEdgesir dārgas, izmantojot blakus esošās matricas attēlojumu.
Python, Java un C / C ++ piemēri
Ja jūs zināt, kā izveidot divu dimensiju masīvus, jūs arī zināt, kā izveidot blakusesības matricu.
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(); )
Blakusparādību matricas lietojumprogrammas
- Maršrutēšanas tabulas izveide tīklos
- Navigācijas uzdevumi
