Graph Representation से हमारा मतलब उस Technique से है जिसका उपयोग Computer की Memory में Graph को Store करने के लिए किया जाता है।
Graph को Memory में Representation करने के लिए दो तरीके है –
- Sequential Representation
- Linked List Representation
Sequential Representation
Sequential Representation में हम Graph को Store करने के लिए Adjacency Matrix का उपयोग करते है Adjacency Matrix में Row और Column को Graph Vertices द्वारा दर्शाया जाता है ।
इस प्रकार के Representation में एक Vertex का दूसरी Vertex से संबंध (Relation) को एक matrix के द्वारा प्रस्तुत करते है ।
चित्र में Vertices (A,B,C,D,E) के बीच Mapping देख सकते है –
- Vertex A से हम B पर भी जा सकते और D पर भी जा सकते है क्योंकि ये Undirected Graph है जहां से जाते है वह हमारा Source होता है तो हम A से जाना चाहते है तो यहां A हमारा Source है और जहां हम पहुंचते है वह Destination है तो A से हम B भी पहुँच सकते और D भी इसलिए B और D हमारी Destination है इसलिए केवल Destination हम 1 Value Store करेंगे बाद बाकी में 0 Store करेंगे और ऐसा ही अगले Vertex के लिए भी करेंगे ।
- Vertex B से हम A की तरफ जा सकते है और C की तरफ भी जा सकते है और D की तरफ भी जा सकते है इसलिए A,C,D Vertex B की Destination है तो A,C,D के स्थान पर 1 Store करेगे और सब मे 0 Store करेंगे ।
- Vertex C से हम B की तरफ जा सकते है और E की तरफ भी जा सकते है, इसलिए B,E Vertex C की Destination है तो B ,E के स्थान पर 1 Store करेगे और सब मे 0 Store करेंगे ।
- Vertex D से हम A की तरफ जा सकते है और B की तरफ भी जा सकते है और E की तरफ भी जा सकते है इसलिए A,B,E Vertex B की Destination है तो A,B,E के स्थान पर 1 Store करेगे और सब मे 0 Store करेंगे ।
- Vertex E से हम C की तरफ जा सकते है और D की तरफ भी जा सकते है, इसलिए C, D Vertex E की Destination है तो C ,D के स्थान पर 1 Store करेगे और सब मे 0 Store करेंगे ।
Linked List Representation
Linked List Representation में Adjacency List का उपयोग Graph को Computer की Memory में Store करने के लिए किया जाता है।
इसके अन्दर एक Linked List की एक Array List बनाते है और ये जो A,B,C,D,E है ये Graph की Vertices है।
फिर हम देखते है कि Vertex A से कहां कहां जा सकते है तो हम A से B भी जा सकते है और D भी जा सकते है और इन्हें A से Connect करके B और D की Linked List बनाते है और ये जो खाली Node आप चित्र में देख रहे हो ये Pointer है जो अगले Node यानि D को Point कर रहा है और अन्त में जो Node है उसमें X का चिन्ह लगा है तो वह Null Node को Point कर रहा है यानि इसके बाद अब कोई Node नही है इसी प्रकार आगे का Process बिलकुल ऐसा ही है ।
फिर हम देखते है कि B Vertex से कहां कहां जा सकते है तो B से हम A जा सकते है और B भी जा सकते है और C भी जा सकते है और फिर इन्हें B से Connect करके A, D और C की Linked List बनाते है ।
फिर हम देखते है कि C Vertex से कहां कहां जा सकते है तो C से हम B जा सकते है और E भी जा सकते है और फिर इन्हें C से Connect करके B और E की Linked List बनाते है ।
फिर हम देखते है कि D Vertex से कहां कहां जा सकते है तो D से हम A जा सकते है और B भी जा सकते है और E भी जा सकते है और फिर इन्हें D से Connect करके A, B और E की Linked List बनाते है ।
फिर हम देखते है कि E Vertex से कहां कहां जा सकते है तो E से हम C जा सकते है और D भी जा सकते है और फिर इन्हें E से Connect करके C और D की Linked List बनाते है ।