Data Structures
पाठ · #9 / 11

ग्राफ़ (Graphs)

शीर्ष (vertices) और किनारे (edges) — सार्वभौमिक अमूर्तन

Graph · algorithms lab

Click any node to set start, then run BFS or DFS. The frontier panel renders as a queue for BFS and a stack for DFS — that single difference is what makes the two visit orders diverge.

frontier
visited (order) 
click a node, then bfs or dfs

खुद आज़माएँ: छह मोड, एक डेमो। traverse: BFS बनाम DFS, जहाँ frontier एक क़तार बनाम एक स्टैक के रूप में दिखता है — शुरुआत तय करने के लिए किसी भी नोड पर क्लिक कीजिए, फिर दोनों को एक साथ दौड़ाइए। shortest path: शुरुआत + लक्ष्य चुनिए, और किसी भारित (weighted) ग्राफ़ पर Dijkstra की A* से तुलना कीजिए। grid: दीवारें रंगिए, और देखिए कि BFS उनके इर्द-गिर्द कैसे योजना बनाता है। dag · topo: किसी रोबोट के boot क्रम को व्यवस्थित कीजिए; एक चक्र (cycle) डालिए और देखिए कैसे एल्गोरिथ्म मना कर देता है। pose graph: किसी बहक चुके पथ को एक loop-closure बाधा का इस्तेमाल कर सीधा कीजिए (खिलौना SLAM)। coverage: anchor छोड़िए, और एक असंतत (discrete) Voronoi आरेख पाइए।

यह क्यों मायने रखता है

ग्राफ़ संबंधों को मॉडल करते हैं: सामाजिक नेटवर्क, सड़क-नक़्शे, निर्भरताएँ (dependencies), स्टेट मशीन। BFS सबसे छोटे पथ ढूँढता है, DFS सारी संभावनाओं को खँगालता है। ग्राफ़ जुड़े हुए डेटा की सार्वभौमिक भाषा हैं।

मूल विचार

सड़कों से जुड़े शहरों के एक नक़्शे को सोचिए। हर शहर एक शीर्ष (vertex) (नोड) है, हर सड़क एक किनारा (edge) (जोड़) है।

ग्राफ़ ऐसे हो सकते हैं:

दो निरूपण (representations):

  1. Adjacency matrix: 2D ऐरे जहाँ किनारा होने पर matrix[i][j] = 1। Lookup तेज़ O(1), पर जगह O(V^2)।
  2. Adjacency list: हर शीर्ष अपने पड़ोसियों की एक सूची रखता है। जगह के लिहाज़ से कुशल O(V+E)।

दो traversal:

मुख्य बातें

और गहराई में

Topological sort — Kahn का एल्गोरिथ्म और DFS-finish-time

एक DAG (directed acyclic graph) निर्भरताओं को दर्शाता है। Topological sort DAG को इस तरह रैखिक करता है कि हर किनारे u → v के लिए आउटपुट में u, v से पहले आए — यानी हर निर्भरता अपने आश्रितों से पहले आए। दो एल्गोरिथ्म, दोनों O(V + E):

Kahn का एल्गोरिथ्म (डेमो के dag · topo मोड में इस्तेमाल):

1. Compute in-degree for every node.
2. Enqueue all nodes with in-degree 0 (no dependencies).
3. While the queue is non-empty:
     u = dequeue.  emit(u).
     For each edge u → v:
       in-degree[v] -= 1
       if in-degree[v] == 0: enqueue(v).
4. If emitted fewer than V nodes → the graph contains a cycle.

DFS-finish-time वाला रूप: हर बिना-देखे नोड से DFS चलाओ; जब कोई नोड पूरा हो जाए (उसके सारे वंशज खोज लिए जाएँ), तो उसे एक स्टैक पर push कर दो। topological क्रम पाने के लिए स्टैक को उल्टा pop कीजिए। यह रूप स्वाभाविक रूप से strongly connected components ढूँढने तक फैलता है (Kosaraju का, Tarjan का) — उपयोगों में सामाजिक ग्राफ़ों में गुच्छे ढूँढना और प्रोग्राम control flow का विश्लेषण शामिल है।

रोबोटिक्स उपयोग: ROS launch फ़ाइलें एक DAG बनाती हैं (हर नोड के पूर्वापेक्षित नोड होते हैं जिन्हें पहले शुरू होना चाहिए); launch सिस्टम परदे के पीछे topological sort करता है। Behavior tree और Make/Bazel build ग्राफ़ भी वही आकार हैं।

Bellman-Ford — Dijkstra का ऋण-भार वाला चचेरा भाई

Dijkstra ऋणेतर (non-negative) किनारा भार मान लेता है। इसकी शुद्धता का प्रमाण इस तथ्य पर टिका है कि जैसे ही आप priority queue से सबसे कम अब-तक-की-लागत वाले नोड को pop करते हैं, बाद में कोई छोटा पथ आ ही नहीं सकता। ऋण किनारे इस मान्यता को तोड़ देते हैं — एक लंबा पर सस्ता चक्कर किसी "तय" पथ को छोटा कर सकता है।

Bellman-Ford रफ़्तार के बदले ऋण भार सँभालने की क्षमता लेता है:

For each of V−1 iterations:
  For each edge (u, v, w):
    if dist[u] + w < dist[v]: dist[v] = dist[u] + w

यह O(V·E) है — एक हीप के साथ Dijkstra के O((V+E) log V) से कहीं धीमा। बदले में मिलती है ऋण भार के तहत शुद्धता, और ऋण चक्रों को पहचानने की क्षमता (V-वाँ iteration जो अब भी किसी किनारे को relax करे, तो इसका मतलब है कुल ऋण भार वाला एक चक्र मौजूद है — आपका सबसे छोटा पथ हमेशा घूमता ही रहेगा)।

कब चाहिए: मुद्रा arbitrage पहचान, टोल वापसी / सब्सिडी वाला मार्ग-नियोजन, जहाँ भी किनारे "छूट" हो सकते हों। ज़्यादातर रोबोटिक्स navigation सिर्फ़ ऋणेतर लागतें इस्तेमाल करता है (दूरी, ऊर्जा, समय), इसलिए वहाँ Dijkstra और A* हावी रहते हैं।

न्यूनतम विस्तार वृक्ष (MST)

किसी जुड़े, अदिशात्मक (undirected), भारित ग्राफ़ के लिए, एक MST उन V − 1 किनारों का उपसमुच्चय है जो सारे शीर्षों को न्यूनतम कुल भार के साथ जोड़ता है। दो चिर-परिचित एल्गोरिथ्म, दोनों O(E log V):

कब चाहिए: सड़क / केबल / पाइपलाइन बिछावट, गुच्छन (single-link clustering = MST बनाकर सबसे बड़े किनारे काटना), नेटवर्क डिज़ाइन। रोबोटिक्स में बहु-एजेंट समन्वय के लिए, MST सारे रोबोटों को घेरता न्यूनतम-संचार पेड़ देता है।

निरूपण के चुनाव

Adjacency-matrix बनाम adjacency-list सिर्फ़ जगह का मामला नहीं। इनके अलग-अलग उपयुक्त मौक़े हैं:

ज़्यादातर प्रोडक्शन ग्राफ़ लाइब्रेरियाँ list को डिफ़ॉल्ट रखती हैं। ऊपर के shortest-path डेमो में Graph struct नोड id से keyed adjacency list इस्तेमाल करता है।

गणितीय ब्यौरा

Space Complexity
Adjacency Matrix: O(V^2)
Adjacency List: O(V + E)
Time Complexity
BFS/DFS: O(V + E)
Check edge (matrix): O(1)
Check edge (list): O(degree)

क्रियान्वयन (Implementation)

ग्राफ़ निरूपण

// Adjacency List
let mut graph: Vec<Vec<usize>> = vec![vec![]; n];
graph[0].push(1);  // Edge 0 -> 1
graph[1].push(0);  // Edge 1 -> 0 (undirected)

// BFS from vertex 0
let mut visited = vec![false; n];
let mut queue = VecDeque::from([0]);
while let Some(v) = queue.pop_front() {
    if visited[v] { continue; }
    visited[v] = true;
    for &neighbor in &graph[v] {
        queue.push_back(neighbor);
    }
}

चिर-परिचित एल्गोरिथ्म

अभ्यास

तीन सबसे ज़्यादा पूछे जाने वाले ग्राफ़ मुहावरों को समेटते तीन सवाल:

→ सभी अभ्यास सवाल देखें