ग्राफ़ सिद्धांत एल्गोरिदम का अभ्यास करने के लिए कुशल तरीका

Question

मैंने एल्गोरिदम पुस्तक के परिचय में breadth-first search एल्गोरिदम के बारे में पढ़ा है और मैंने पेपर पर एल्गोरिदम अनुकरण किया है। मैं अब क्या करना चाहता हूं इसे अतिरिक्त अभ्यास के लिए कोड में लागू करना है।

मैं (adjacency list, "रंग", "दूरी", और "जनक" सरणियों) लेकिन तब मुझे याद है वहाँ वर्तमान में ग्राफ पुस्तकालयों Boost ग्राफ की तरह वहाँ बाहर हैं कि खरोंच से सभी डेटा संरचनाओं को लागू करने के बारे में सोच रहा था लाइब्रेरी में लाइब्रेरी और कुछ अन्य graph APIs। मैंने UVA और Sphere Judge Online पर कुछ बीएफएस से संबंधित समस्याओं की तलाश करने की भी कोशिश की लेकिन मैं यह नहीं बता सकता कि बीएफएस समाधान की कौन सी समस्याओं की आवश्यकता होगी।

मेरा प्रश्न है कि इन ग्राफ एल्गोरिदम अभ्यास करने के लिए सबसे दर्दरहित तरीका होगा (बस BFS तक ही सीमित नहीं, लेकिन यह भी उपयोगी में आ जाएगा जब मैं, DFS, Dijkstra, Floyd-Warshall को लागू करने आदि चाहते हैं) है। अभ्यास समस्याओं के साथ साइट का स्वागत है।

Answer 1

मुझे व्यक्तिगत रूप से लगता है कि उनको समझने का सबसे अच्छा तरीका ग्राफ प्रतिनिधित्व को स्वयं स्क्रैच से लागू करेगा।

एक तरफ, यह आपको वास्तविक कार्यान्वयन चेतावनी दिखाएगा जिसमें से आप सीखते हैं क्यों एक विशेष एल्गोरिदम दिलचस्प/अच्छा/कुशल/जो कुछ भी हो सकता है। दूसरी तरफ, मुझे लगता है कि इसके प्रभाव (रिकर्सन, प्रदर्शन/स्केलेबिलिटी, एप्लिकेशन, विकल्प, ...) सहित ग्राफ़ और उनके वास्तविक जीवन के उपयोग को समझना, नीचे-नीचे दृष्टिकोण के माध्यम से आसान बना दिया गया है।

लेकिन शायद यह सिर्फ मुझे है। उपरोक्त बहुत व्यक्तिगत स्वाद है।

Answer 2

मुझे आपका प्रश्न दिलचस्प लगता है, मैंने थोड़ा गुगल किया और मुझे JGraphEd मिला।

इसमें सभी ग्राफ एल्गोरिदम शामिल नहीं हैं लेकिन यह प्रयोग के लिए एक अच्छा टूल जैसा दिखता है।

Answer 3

मैं बाल्फा से सहमत हूं। एल्गोरिदम को वास्तव में सीखने और समझने का सबसे अच्छा तरीका कार्यान्वयन करना है। बस एक एल्गोरिदम चुनें और इसे कार्यान्वित करें। जब आप किसी ऐसे बिंदु तक पहुंच जाते हैं जहां आप अटक जाते हैं या अनिश्चित हैं, तो कई मौजूदा उदाहरण देखें। फिर आप जो कुछ भी पेश किया जाता है उसे स्वीकार करने के बजाय समझदारी की स्थिति से दूसरों की अपनी सोच की तुलना करने में सक्षम होंगे।

एक बार जब आप यह जान लें कि आप क्या चाहते हैं, तो अपनी समझ को मजबूत करने का सबसे अच्छा तरीका यह है कि इसे किसी और को इसका वर्णन करने या उसका वर्णन करने का प्रयास करें। आपके पास कुछ लोग आपकी बात सुनने के इच्छुक हो सकते हैं, या कम से कम आप एल्गोरिदम के लिए नए लोगों के लिए ब्लॉग एंट्री लिख सकते हैं जो आपने अभी पढ़ा है।

लेकिन आप देख रहे हैं "दर्दरहित" के लिए, तो शायद आप एल्गोरिदम के स्पष्ट पूरी तरह रहना चाहिए ;-)

Answer 4

This site could help you

यहाँ आप ACM problemset पर हर समस्या का विवरण है। आप प्रत्येक समस्या की श्रेणी देख सकते हैं, और इसे हल करने के संकेत। बस ग्राफ से संबंधित समस्याओं के लिए ब्राउज़ करें। अच्छी सलाह है कि उन संकेतों का उपयोग केवल तभी करें जब आपने समस्या को हल करने की कोशिश की और असफल हो।

Answer 5

वास्तविक डेटा, पर कुछ कम से कम पथ एल्गोरिदम जहां पता लगाया क्षेत्र पीले रंग में प्रदर्शित किया जाता है का विजुअलाइजेशन:

• (bidirectional) Dijkstra
• A*