ग्राफ निकटता मैट्रिक्स (सी ++, जावा और पायथन में कोड उदाहरणों के साथ)

इस ट्यूटोरियल में, आप सीखेंगे कि आसन्न मैट्रिक्स क्या है। साथ ही, आपको C, C ++, Java और पायथन में आसन्न मैट्रिक्स के काम करने के उदाहरण मिलेंगे।

एक आसन्न मैट्रिक्स एक ग्राफ G = (V, E) बूलियन के एक मैट्रिक्स के रूप में प्रतिनिधित्व करने का एक तरीका है।

आसन्न मैट्रिक्स प्रतिनिधित्व

मैट्रिक्स का आकार वह है VxVजहां Vग्राफ़ में कोने की संख्या है और एक प्रविष्टि Aijका मूल्य या तो 1 या 0 है जो इस बात पर निर्भर करता है कि क्या शीर्ष पर i से शीर्ष तक j है।

आसन्न मैट्रिक्स उदाहरण

नीचे दी गई छवि एक ग्राफ और इसके समीपवर्ती मैट्रिक्स को दिखाती है।

एक ग्राफ से आसन्न मैट्रिक्स

अप्रत्यक्ष रेखांकन के मामले में, मैट्रिक्स प्रत्येक किनारे के कारण विकर्ण के बारे में सममित है (i,j), एक किनारा भी है (j,i)।

आसन्न मैट्रिक्स के पेशेवरों

एक किनारे को जोड़ने, एक किनारे को हटाने और यह जाँचने की तरह कि बुनियादी गतिविधियाँ हैं क्या शीर्ष पर मैं i से शीर्ष j तक अत्यंत समय कुशल, निरंतर समय संचालन हैं।

यदि ग्राफ़ सघन है और किनारों की संख्या बड़ी है, तो आसन्न मैट्रिक्स पहली पसंद होनी चाहिए। भले ही ग्राफ और आसन्न मैट्रिक्स विरल हो, हम विरल मैट्रिस के लिए डेटा संरचनाओं का उपयोग करके इसका प्रतिनिधित्व कर सकते हैं।

हालांकि, सबसे बड़ा फायदा मैट्रिस के उपयोग से आता है। हार्डवेयर में हाल ही की प्रगति हमें GPU पर भी महंगे मैट्रिक्स ऑपरेशन करने में सक्षम बनाती है।

आसन्न मैट्रिक्स पर ऑपरेशन करके, हम ग्राफ की प्रकृति और इसके कोने के बीच संबंध में महत्वपूर्ण अंतर्दृष्टि प्राप्त कर सकते हैं।

आसन्न मैट्रिक्स के होते हैं

VxVआसन्न मैट्रिक्स की अंतरिक्ष आवश्यकता इसे मेमोरी हॉग बनाती है। जंगली में रेखांकन आमतौर पर बहुत अधिक कनेक्शन नहीं होते हैं और यही सबसे बड़ी वजह है कि आसन्न सूचियां अधिकांश कार्यों के लिए बेहतर विकल्प हैं।

जबकि बुनियादी ऑपरेशन आसान होते हैं, आसन्न मैट्रिक्स प्रतिनिधित्व का उपयोग करते समय ऑपरेशन जैसे inEdgesऔर outEdgesमहंगे होते हैं।

पायथन, जावा और सी / सी ++ उदाहरण

यदि आप जानते हैं कि दो आयामी सरणियों का निर्माण कैसे किया जाता है, तो आप यह भी जानते हैं कि आसन्न मैट्रिक्स कैसे बनाया जाए।

पायथन जावा सी सी +

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

आसन्न मैट्रिक्स अनुप्रयोग

1. नेटवर्क में रूटिंग टेबल बनाना
2. नेविगेशन कार्य