Graph Adjacency Matrix (C ++, Java és Python kódpéldákkal)

Tartalomjegyzék

Adjacency mátrix reprezentáció
Adjacency Matrix példa
A szomszédsági mátrix előnyei
A szomszédsági mátrix hátrányai
Példák Python, Java és C / C ++
Adjacency Matrix Applications

Ebben az oktatóanyagban megtudhatja, mi egy szomszédsági mátrix. A szomszédsági mátrixról működő példákat is talál C, C ++, Java és Python nyelven.

A szomszédsági mátrix a G = (V, E) gráf mint logikai mátrix ábrázolásának egyik módja.

Adjacency mátrix reprezentáció

A mátrix mérete VxVhol Vvan a gráfban lévő csúcsok száma, és egy bejegyzés Aijértéke 1 vagy 0 attól függően, hogy van-e él az i és a j csúcs között.

Adjacency Matrix példa

Az alábbi képen grafikon és annak megfelelő szomszédsági mátrix látható.

Adjacencia-mátrix egy grafikonból

Irányítatlan gráfok esetén a mátrix minden él miatt szimmetrikus az átlóval szemben (i,j), van egy él is (j,i).

A szomszédsági mátrix előnyei

Az alapvető műveletek, például egy él hozzáadása, egy él eltávolítása és annak ellenőrzése, hogy van-e él az i és a j csúcs között, rendkívül időhatékony, állandó idejű műveletek.

Ha a grafikon sűrű és az élek száma nagy, akkor a szomszédsági mátrix legyen az első választás. Még akkor is, ha a grafikon és a szomszédsági mátrix ritka, a ritka mátrixok adatstruktúráit felhasználva ábrázolhatjuk.

A legnagyobb előny azonban a mátrixok használatából származik. A hardver legújabb fejleményei lehetővé teszik számunkra, hogy még drága mátrix műveleteket hajtsunk végre a GPU-n.

A szomszédos mátrixon végzett műveletek révén fontos betekintést nyerhetünk a gráf természetébe és a csúcsai közötti kapcsolatba.

A szomszédsági mátrix hátrányai

A VxVszomszédsági mátrix helyigénye memória-disznóvá teszi. A vadonban lévő grafikonok általában nem rendelkeznek túl sok kapcsolattal, és ez a fő oka annak, hogy a szomszédsági listák a jobb választás a legtöbb feladathoz.

Míg az alapműveletek egyszerűek, a szomszédsági mátrix reprezentáció használatakor a műveletek hasonlóak inEdgesés outEdgesdrágák.

Példák Python, Java és C / C ++

Ha tudja, hogyan kell kétdimenziós tömböket létrehozni, akkor tudja, hogyan kell létrehozni egy szomszédsági mátrixot is.

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