मान लीजिए कि हमारे पास एक निर्देशित चक्रीय ग्राफ है जो आसन्न सूची द्वारा दर्शाया गया है। हमें ग्राफ़ में नोड दोहराव के बिना सबसे लंबा रास्ता खोजना होगा।
तो, अगर इनपुट पसंद है
तो आउटपुट 4 होगा, क्योंकि पथ 0 -> 1 -> 3 -> 4 -> 2 लंबाई 4 के साथ है।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
- उत्तर:=0
- n :=ग्राफ़ की नोड संख्या
- तालिका :=आकार n की सूची और -1 से भरें
- एक फ़ंक्शन को परिभाषित करें dfs() । यह आपको लेगा
- यदि तालिका[u] -1 नहीं है, तो
- रिटर्न टेबल[u]
- p_len :=0
- ग्राफ में प्रत्येक vectex v के लिए[u], करते हैं
- p_len :=अधिकतम p_len और (1 + dfs(v))
- टेबल[यू] :=p_len
- पी_लेन लौटाएं
- मुख्य विधि से निम्न कार्य करें -
- मैं के लिए 0 से n की सीमा में, करते हैं
- उत्तर:=अधिकतम उत्तर, dfs(i)
- वापसी उत्तर
उदाहरण (पायथन)
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
class Solution: def solve(self, graph): ans = 0 n = len(graph) table = [-1] * n def dfs(u): if table[u] != -1: return table[u] p_len = 0 for v in graph[u]: p_len = max(p_len, 1 + dfs(v)) table[u] = p_len return p_len for i in range(n): ans = max(ans, dfs(i)) return ans ob = Solution() graph = [ [1, 2], [3, 4], [], [4], [2], ] print(ob.solve(graph))
इनपुट
graph = [[1, 2],[3, 4],[],[4],[2]]
आउटपुट
4