Graafiku adjacency maatriks (koodinäidetega C ++, Java ja Python)

Lang L: none (table-of-contents)

Adjacency maatriksi esitus
Piirangute maatriksi näide
Külgnemismaatriksi plussid
Külgnusmaatriksi miinused
Pythoni, Java ja C / C ++ näited
Adjacency Matrixi rakendused

Selles õpetuses saate teada, mis on külgnemismaatriks. Samuti leiate toimivaid näiteid külgnemismaatriksist C, C ++, Java ja Python.

Külgnemismaatriks on viis graafi G = (V, E) esitamiseks booleanide maatriksina.

Adjacency maatriksi esitus

Maatriksi suurus on see, VxVkus Von tippude arv graafikus ja kirje väärtus Aijon kas 1 või 0 sõltuvalt sellest, kas tipust i tipuni j on serv.

Piirangute maatriksi näide

Alloleval pildil on graafik ja selle ekvivalentne külgnemismaatriks.

Adjacency maatriks graafikult

Suunamata graafide korral on maatriks diagonaali suhtes sümmeetriline iga serva tõttu (i,j), seal on ka serv (j,i).

Külgnemismaatriksi plussid

Põhitoimingud nagu serva lisamine, serva eemaldamine ja tipust i kuni tipuni j on servade kontrollimine, on äärmiselt ajaefektiivsed, pideva ajaga toimingud.

Kui graafik on tihe ja servade arv on suur, peaks külgnemismaatriks olema esimene valik. Isegi kui graafik ja külgnemismaatriks on hõredad, võime seda kujutada hõredate maatriksite andmestruktuuride abil.

Suurima eelise annab aga maatriksite kasutamine. Hiljutised riistvaralised edusammud võimaldavad meil GPU-l teha isegi kalleid maatriksoperatsioone.

Tehes operatsioone külgneval maatriksil, saame olulise ülevaate graafiku olemusest ja selle tippude vahelisest suhtest.

Külgnusmaatriksi miinused

VxVRuumi nõue naabrusmaatriks muudab mälu orikas. Looduses olevatel graafikutel pole tavaliselt liiga palju ühendusi ja see on peamine põhjus, miks külgnevusloendid on enamiku ülesannete jaoks parem valik.

Ehkki põhitoimingud on lihtsad, meeldivad inEdgesja outEdgeson kallid, kui kasutada külgnemismaatriksi esitust.

Pythoni, Java ja C / C ++ näited

Kui teate, kuidas luua kahemõõtmelisi massiive, teate ka, kuidas luua külgnemismaatriks.

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