Matica susednej závislosti grafu (s príkladmi kódu v C ++, Java a Python)

Obsah

Reprezentácia matice susedstva
Príklad matice susedstva
Pros matice susednosti
Nevýhody matice susedstva
Príklady jazyka Python, Java a C / C ++
Aplikácie susedných matíc

V tomto tutoriále sa dozviete, čo je matica susedstva. Nájdete tiež pracovné príklady matice susedstva v jazykoch C, C ++, Java a Python.

Matica susednosti je spôsob reprezentácie grafu G = (V, E) ako matice boolovských hodnôt.

Reprezentácia matice susedstva

Veľkosť matice je VxVtam, kde Vje počet vrcholov v grafe a hodnota záznamu Aijje buď 1 alebo 0 podľa toho, či existuje hrana od vrcholu i po vrchol j.

Príklad matice susedstva

Obrázok nižšie zobrazuje graf a jeho ekvivalentnú maticu susednosti.

Matica susednosti z grafu

V prípade neorientovaných grafov je matica symetrická okolo uhlopriečky, pretože každá hrana (i,j)má hranu (j,i).

Pros matice susednosti

Základné operácie, ako je pridanie okraja, odstránenie okraja a kontrola, či existuje hrana od vrcholu i po vrchol j, sú mimoriadne časovo efektívne a stále operácie.

Ak je graf hustý a počet hrán je veľký, mala by byť prvou voľbou matica susednosti. Aj keď sú graf a matica susedstva riedke, môžeme ich znázorniť pomocou dátových štruktúr pre riedke matice.

Najväčšia výhoda však pochádza z použitia matíc. Nedávny pokrok v hardvéri nám umožňuje vykonávať aj nákladné maticové operácie na GPU.

Vykonaním operácií na susednej matici môžeme získať dôležité informácie o povahe grafu a vzťahu medzi jeho vrcholmi.

Nevýhody matice susedstva

VxVPožiadavka priestor matice přilehlosti sa pamäťová prasa robí. Grafy vo voľnej prírode zvyčajne nemajú príliš veľa spojení a to je hlavný dôvod, prečo sú zoznamy susedných vzťahov lepšou voľbou pre väčšinu úloh.

Aj keď sú základné operácie jednoduché, operácie sa podobajú inEdgesa outEdgessú drahé, keď sa používa reprezentácia susednej matice.

Príklady jazyka Python, Java a C / C ++

Ak viete, ako vytvoriť dvojrozmerné polia, viete tiež, ako vytvoriť maticu susednosti.

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