Grafik Bitişiklik Matrisi (C ++, Java ve Python'daki kod örnekleri ile)

İçindekiler

Bitişik matris gösterimi
Bitişiklik Matrisi Örneği
Bitişik matrisin artıları
Bitişik matris eksileri
Python, Java ve C / C ++ Örnekleri
Bitişiklik Matrisi Uygulamaları

Bu eğitimde, bitişik matrisin ne olduğunu öğreneceksiniz. Ayrıca, C, C ++, Java ve Python'da bitişiklik matrisinin çalışma örneklerini bulacaksınız.

Bitişik matris, G = (V, E) grafiğini boole matrisi olarak temsil etmenin bir yoludur.

Bitişik matris gösterimi

Matrisin boyutu , grafikteki köşe sayısının VxVnerede Volduğu ve bir girişin değerinin, Aijtepe noktasından j köşesine bir kenar olup olmamasına bağlı olarak 1 veya 0'dır.

Bitişiklik Matrisi Örneği

Aşağıdaki görüntü bir grafiği ve eşdeğer bitişik matrisini göstermektedir.

Bir grafikten bitişiklik matrisi

Yönlendirilmemiş grafikler olması durumunda, matris her kenardan dolayı köşegen etrafında simetriktir (i,j), ayrıca bir kenar da vardır (j,i).

Bitişik matrisin artıları

Bir kenar ekleme, bir kenar kaldırma ve tepe noktasından j tepe noktasına bir kenar olup olmadığını kontrol etme gibi temel işlemler, son derece zaman açısından verimli, sabit zamanlı işlemlerdir.

Grafik yoğunsa ve kenar sayısı büyükse, bitişik matris ilk seçenek olmalıdır. Grafik ve bitişik matris seyrek olsa bile, seyrek matrisler için veri yapıları kullanarak onu temsil edebiliriz.

Ancak en büyük avantaj, matrislerin kullanımından gelir. Donanımdaki son gelişmeler, GPU'da pahalı matris işlemlerini bile gerçekleştirmemizi sağlıyor.

Bitişik matris üzerinde işlemler gerçekleştirerek, grafiğin doğası ve köşeleri arasındaki ilişki hakkında önemli bilgiler edinebiliriz.

Bitişik matris eksileri

VxVBitişiklik matrisi uzay şartı bellek domuz yapar. Doğadaki grafiklerin genellikle çok fazla bağlantısı yoktur ve bu, bitişik listelerin çoğu görev için daha iyi seçim olmasının ana nedenidir.

Temel işlemler kolay olsa da , bitişik matris gösterimini kullanırken benzer inEdgesve outEdgespahalıdır.

Python, Java ve C / C ++ Örnekleri

İki boyutlu dizilerin nasıl oluşturulacağını biliyorsanız, bitişik matrisin nasıl oluşturulacağını da bilirsiniz.

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