În acest tutorial, veți afla ce este o matrice de adiacență. De asemenea, veți găsi exemple de lucru ale matricei de adiacență în C, C ++, Java și Python.
O matrice de adiacență este o modalitate de a reprezenta un grafic G = (V, E) ca o matrice a booleenilor.
Reprezentarea matricei de adiacență
Dimensiunea matricei este VxVunde Veste numărul de vârfuri din grafic și valoarea unei intrări Aijeste fie 1, fie 0, în funcție de existența unei margini de la vârful i la vârful j.
Exemplu de matrice de adiacență
Imaginea de mai jos prezintă un grafic și matricea echivalentă de adiacență.
Matricea de adiacență dintr-un grafic
În cazul graficelor nedirecționate, matricea este simetrică în raport cu diagonala din cauza fiecărei muchii (i,j), există și o margine (j,i).
Pro-uri ale matricei de adiacență
Operațiile de bază, cum ar fi adăugarea unei margini, eliminarea unei margini și verificarea dacă există o margine de la vârful i la vârful j sunt extrem de eficiente în timp, operațiuni în timp constant.
Dacă graficul este dens și numărul muchiilor este mare, matricea de adiacență ar trebui să fie prima alegere. Chiar dacă graficul și matricea de adiacență sunt rare, îl putem reprezenta folosind structuri de date pentru matricele rare.
Cu toate acestea, cel mai mare avantaj vine din utilizarea matricilor. Progresele recente în materie de hardware ne permit să efectuăm chiar și operațiuni cu matrice scumpe pe GPU.
Efectuând operații pe matricea adiacentă, putem obține informații importante despre natura graficului și relația dintre vârfurile sale.
Contra matricei de adiacență
Cerința de VxVspațiu a matricei de adiacență o face să fie un porc de memorie. Graficele în natură nu au de obicei prea multe conexiuni și acesta este motivul principal pentru care listele de adiacență sunt cea mai bună alegere pentru majoritatea sarcinilor.
În timp ce operațiile de bază sunt ușoare, operațiile ca inEdgesși outEdgessunt costisitoare atunci când se utilizează reprezentarea matricei de adiacență.
Exemple Python, Java și C / C ++
Dacă știi cum să creezi tablouri bidimensionale, știi și cum să creezi o matrice de adiacență.
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(); )
Aplicații Matrice Adjacency
- Crearea tabelei de rutare în rețele
- Sarcini de navigare
