जावा में भारित, निर्देशित ग्राफ का प्रतिनिधित्व करने के कुछ तरीके क्या हैं?

Question

मैं किसी बाहरी पुस्तकालय का उपयोग नहीं कर सकता, इसलिए मैं डेटा संरचना को स्वयं बनाने के कुछ तरीकों के बारे में सोचने की कोशिश कर रहा हूं। मैं शायद इस तरह कुछ सोच रहा था:

public class Node{ 
    Set<Edge> adjacent; 
    int value; 
} 

public class Edge{ 
    Node target; 
    int weight; 
} 

लेकिन मुझे लगता है कि ऐसा करने का शायद एक बेहतर तरीका है।

इस ग्राफ के लिए मेरा अंतिम उपयोग बेलमैन फोर्ड एल्गोरिदम को चलाने के लिए है, लेकिन मुझे स्पष्ट रूप से पहले एक कार्यशील ग्राफ की आवश्यकता है!

Answer 1

उत्तर आपके ग्राफ़ पर लागू करने की योजना बना रहे एल्गोरिदम पर बहुत निर्भर करता है।

ग्राफ का प्रतिनिधित्व करने के दो सामान्य तरीके हैं - adjacency list और adjacency matrix। आपके मामले में, और आसन्नता मैट्रिक्स वजन का प्रतिनिधित्व करने वाले पूर्णांक की एक वर्ग सरणी है। आपका प्रतिनिधित्व एक आसन्न सूची का उपयोग करता है।

एल्गोरिदम हैं जो आसन्नता मैट्रिक्स (उदा। फ़्लॉइड-वारशेल एल्गोरिदम) पर बेहतर काम करते हैं। अन्य एल्गोरिदम आसन्नता सूचियों (जैसे डिजस्ट्रा के एल्गोरिदम) पर बेहतर काम करते हैं। यदि आपका ग्राफ स्पैस है, तो आसन्नता मैट्रिक्स का उपयोग निषिद्ध हो सकता है।

Answer 2

सामान्य रूप से, आप ग्राज़ को एडजैसीेंसी सूचियों या एडजेंसी मैट्रिस के रूप में प्रदर्शित कर सकते हैं। पसंद वास्तव में आपकी समस्या के विवरण पर निर्भर करता है।

एक एडजेंसी मैट्रिक्स का उपयोग करके, आप केवल वजन का प्रतिनिधित्व करने वाले पूर्णांक का मैट्रिक्स प्राप्त कर सकते हैं।

आप एक संलग्नता सूची है का फैसला करते हैं, तो आप बस पूर्णांकों (अपने ग्राफ के नोड्स संभालने मान एक पूर्णांक से पहचाने जाते हैं), तो आपको क्या किया है के लिए इसी तरह की सूची की एक सूची संग्रहीत कर सकता है।

Answer 3

आप एक अनिर्धारित ग्राफ में के रूप में एक नोड का उपयोग कर सकते, नोड्स की एक सूची रखने के लिए यह जुड़ा हुआ है जो, और इसके अलावा के रूप में कनेक्शन के साथ जुड़े वजन जोड़ें:

public class Node{ 
    int value; 
    HashMap<Node,Integer> adjacency; 
}