Grafična matrika sosednosti (s primeri kod v C ++, Java in Python)

Kazalo

Predstavitev matrice sosedstva
Primer matrice sosedstva
Prednosti matrice sosednosti
Proti matriki sosednosti
Primeri Python, Java in C / C ++
Uporaba matrice sosedstva

V tej vadnici boste izvedeli, kaj je matrika sosednosti. Prav tako boste našli delovne primere matrice sosedstva v C, C ++, Java in Python.

Matrika sosednosti je način predstavitve grafa G = (V, E) kot matrike logičnih vrednosti.

Predstavitev matrice sosedstva

Velikost matrike je, VxVkjer Vje število točk v grafu, vrednost vnosa pa Aijje 1 ali 0, odvisno od tega, ali obstaja rob od točke i do točke j.

Primer matrice sosedstva

Spodnja slika prikazuje graf in njegovo enakovredno matriko sosednosti.

Matrika sosednosti iz grafa

V primeru neusmerjenih grafov je matrica simetrična glede diagonale zaradi vsakega roba (i,j), obstaja tudi rob (j,i).

Prednosti matrice sosednosti

Osnovne operacije, kot je dodajanje roba, odstranjevanje roba in preverjanje, ali obstaja rob od točke i do točke j, so izjemno časovno učinkovite in konstantne časovne operacije.

Če je graf gost in je število robov veliko, bi morala biti prva izbira matrika sosednosti. Tudi če sta graf in matrika sosednosti redka, ga lahko predstavimo z uporabo podatkovnih struktur za redke matrike.

Največja prednost pa je uporaba matric. Nedavni napredek v strojni opremi nam omogoča izvajanje celo dragih matričnih operacij na GPU.

Z izvajanjem operacij na sosednji matriki lahko dobimo pomemben vpogled v naravo grafa in razmerje med njegovimi točki.

Proti matriki sosednosti

Zaradi VxVprostorske potrebe matrike sosednosti je ta pomnilnik prašič. Grafi v naravi običajno nimajo preveč povezav in to je glavni razlog, zakaj so seznami sosednosti boljša izbira za večino nalog.

Osnovne operacije so sicer enostavne, inEdgesvendar outEdgesso pri vnosu matrike sosednosti všeč in drage.

Primeri Python, Java in C / C ++

Če veste, kako ustvariti dvodimenzionalne nize, veste tudi, kako ustvariti matriko sosednosti.

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