PGDCA, BCA, B-Tech, MCA, M-Tech, B.Sc computer science राजस्थान सूचना सहायक व कंप्यूटर शिक्षक विशेष नोट्स: इस अध्याय में हम Graph Representation: Adjacency Matrix (V x V) Space O(V^2) (ग्राफ निरूपण: आसन्नता मैट्रिक्स (Adjacency Matrix) और स्पेस O(V^2)) की संपूर्ण थ्योरी, मुख्य तकनीकी बिंदु, तुलनात्मक तालिका और विगत परीक्षाओं के पैटर्न पर आधारित 20 अति-महत्वपूर्ण बहुविकल्पीय प्रश्न (MCQs) विस्तृत हिंदी व अंग्रेजी व्याख्या सहित पढ़ेंगे।
Overview: An Adjacency Matrix represents a V-vertex graph as a V x V 2D matrix A where A[i][j] records edge presence (1/0) or edge weight. It provides O(1) edge lookup and O(V^3) compatibility with Floyd-Warshall, at the cost of Theta(V^2) memory space regardless of edge density.
अध्याय सार: आसन्नता मैट्रिक्स (Adjacency Matrix) V वर्टेक्स वाले ग्राफ को V x V की 2D सारणी A द्वारा दर्शाती है, जहाँ A[i][j] एज की उपस्थिति (1/0) या भार (Weight) बताता है। यह O(1) समय में एज जांच की सुविधा देता है, परंतु एजेज़ की संख्या कम होने पर भी सदैव Theta(V^2) मेमोरी घेरता है।
Graph Representation: Adjacency Matrix (V x V) Space O(V^2): Detailed Notes & Architecture (ग्राफ निरूपण: आसन्नता मैट्रिक्स (Adjacency Matrix) और स्पेस O(V^2))
1. 2D Grid Layout for Unweighted, Weighted & Directed Graphs (अनवेटेड, वेटेड और निर्देशित ग्राफ के लिए मैट्रिक्स संरचना)
[EN] For vertices indexed 0..V-1, an Adjacency Matrix A of size V x V stores A[i][j] = 1 if edge (i, j) exists and 0 otherwise in unweighted graphs. In weighted graphs, A[i][j] holds weight(i, j) for existing edges and infinity (or a sentinel) for missing edges, with A[i][i] = 0 on the main diagonal. In an undirected graph, every edge {i, j} sets both A[i][j] and A[j][i], making the matrix strictly symmetric (A = A^T).
[HI] 0 से V-1 वर्टेक्स के लिए V x V की मैट्रिक्स में अनवेटेड ग्राफ हेतु एज होने पर A[i][j] = 1 तथा न होने पर 0 रखा जाता है। वेटेड ग्राफ में यहाँ भार (Weight) और एज न होने पर अनंत (Infinity) लिखते हैं। अनिर्देशित ग्राफ में A[i][j] == A[j][i] होने से यह एक सममित मैट्रिक्स (Symmetric Matrix) होती है।
2. Space Complexity Theta(V^2) & Sparse Graph Bottleneck (स्पेस जटिलता Theta(V^2) और स्पार्स ग्राफ में नुकसान)
[EN] Allocating a V x V table always consumes Theta(V^2) memory regardless of whether the graph has V^2/2 edges or merely 5 edges. For instance, a road network with V = 100,000 intersections requires 10^10 matrix entries (~40 GB for 4-byte integers), even though each intersection connects to only ~4 roads! Conversely, for dense graphs (|E| ~ V^2) using 1-bit flags (V^2 / 8 bytes), a bit-packed adjacency matrix can actually use less RAM than pointer-heavy adjacency lists.
[HI] ग्राफ में चाहे 10 एजेज़ हों या हजारों, V x V मैट्रिक्स को सदैव Theta(V^2) स्पेस चाहिए। यदि V = 1,00,000 वर्टेक्स हों तो 10^10 कोशिकाएं (~40 GB RAM) लगेंगी, जो स्पार्स ग्राफ के लिए अव्यावहारिक है। हाँ, बहुत सघन (Dense) ग्राफ में बिट-आधारित मैट्रिक्स कम जगह ले सकती है।
3. Time Complexity of Core Graph Operations (प्रमुख ऑपरेशन्स की समय जटिलता)
[EN] The standout advantage of an Adjacency Matrix is O(1) constant-time edge existence check (hasEdge(u, v) simply reads A[u][v]), O(1) edge insertion, and O(1) edge deletion. However, finding all neighbors or computing the degree of vertex u requires scanning the entire row u in O(V) time. Consequently, full graph traversals like BFS or DFS on an Adjacency Matrix take O(V^2) time instead of O(V + E).
[HI] Adjacency Matrix का सबसे बड़ा लाभ O(1) समय में यह जांचना है कि u और v के बीच एज है या नहीं (A[u][v])। एज जोड़ना और हटाना भी O(1) में होता है। लेकिन किसी वर्टेक्स के पड़ोसियों को ढूंढने या डिग्री निकालने में पूरी पंक्ति स्कैन करनी पड़ती है (O(V)), जिससे पूरा BFS/DFS ट्रैवर्सल O(V^2) समय लेता है।
4. Matrix Powers (A^k) & All-Pairs Shortest Path Synergy (मैट्रिक्स घात (A^k) और फ्लॉयड-वॉर्शल एल्गोरिथ्म)
[EN] Adjacency Matrices connect graph theory directly to linear algebra: entry (A^k)[i][j] of the k-th matrix power counts the exact number of walks of length k from vertex i to vertex j! In a directed graph's adjacency matrix, row i sums to out_deg(i) while column j sums to in_deg(j). Algorithms like Floyd-Warshall (All-Pairs Shortest Paths in O(V^3)) and Warshall's Transitive Closure operate natively in-place on an Adjacency Matrix.
[HI] रैखिक बीजगणित के अनुसार मैट्रिक्स की घात A^k की प्रविष्टि (i, j) वर्टेक्स i से j तक ठीक k लंबाई के रास्तों (Walks) की संख्या बताती है। निर्देशित ग्राफ में पंक्ति i का योग Out-Degree और कॉलम j का योग In-Degree देता है। Floyd-Warshall एल्गोरिथ्म सीधे इसी मैट्रिक्स पर O(V^3) में चलता है।
Syntax, Formula & Technical Example (Graph Representation: Adjacency Matrix (V x V) Space O(V^2))
# Undirected 4-vertex cycle 0-1-2-3-0 Adjacency Matrix (Symmetric: A == A^T):
A = [
[0, 1, 0, 1], # Neighbors of 0: 1, 3 (deg = row sum = 2)
[1, 0, 1, 0], # Neighbors of 1: 0, 2
[0, 1, 0, 1], # Neighbors of 2: 1, 3
[1, 0, 1, 0], # Neighbors of 3: 0, 2
]
# Check edge(u, v): return A[u][v] == 1 -> O(1) time
# Find neighbors(u): [v for v in range(V) if A[u][v]] -> O(V) time
Graph Representation: Adjacency Matrix (V x V) Space O(V^2) Quick Reference & Comparison Table
| Adjacency Matrix Operation | Time / Space Complexity | Technical Mechanism |
|---|---|---|
| Memory Space Required | Theta(V^2) | Allocates V x V 2D array regardless of |E| |
| Check Edge (u, v) Exists | O(1) | Direct constant-time lookup at cell A[u][v] |
| Iterate All Neighbors of u | O(V) | Scans every column 0..V-1 in row u |
| Full BFS / DFS Traversal | O(V^2) | Scans row of size V for each of V vertices |
Graph Representation: Adjacency Matrix (V x V) Space O(V^2) Top 20 Bilingual MCQs with Answers
Q1. What is the exact space complexity of an Adjacency Matrix for a graph with V vertices and E edges?
(V वर्टेक्स और E एजेज़ वाले ग्राफ के लिए Adjacency Matrix की सटीक स्पेस जटिलता क्या होती है?)
(A) Theta(E)
(B) Theta(V * log V)
(C) Theta(V + E)
(D) Theta(V^2)
Correct Answer: (D)
[EN] An Adjacency Matrix always allocates a V x V two-dimensional array regardless of how small E is.
[HI] Adjacency Matrix में E का मान कितना भी कम हो, सदैव V x V आकार का एरे बनता है, इसलिए स्पेस Theta(V^2) होता है।
Q2. How fast can an Adjacency Matrix determine whether an edge exists between two given vertices u and v?
(Adjacency Matrix में किन्हीं दो वर्टेक्स u और v के बीच एज मौजूद है या नहीं, यह जांचने में कितना समय लगता है?)
(A) O(log V)
(B) O(1)
(C) O(E)
(D) O(V)
Correct Answer: (B)
[EN] Direct random-access indexing A[u][v] answers edge membership in a single constant-time operation.
[HI] सीधे 2D एरे इंडेक्स A[u][v] पढ़ने से केवल O(1) समय में एज की उपस्थिति पता चल जाती है।
Q3. For a simple UNDIRECTED graph (without self-loops), which matrix properties are strictly true of its Adjacency Matrix A?
(एक सरल अनिर्देशित ग्राफ (बिना सेल्फ-लूप) के Adjacency Matrix A के बारे में कौन से गुण सदैव सत्य होते हैं?)
(A) A is always lower triangular
(B) All diagonal entries are 1
(C) A is asymmetric with row sums unequal to column sums
(D) A is symmetric (A[i][j] = A[j][i]) and its main diagonal entries A[i][i] are all 0
Correct Answer: (D)
[EN] Each undirected edge {i, j} sets both A[i][j] = 1 and A[j][i] = 1 (symmetry), and zero self-loops keeps A[i][i] = 0.
[HI] अनिर्देशित एज दोनों तरफ समान होता है इसलिए A[i][j] = A[j][i] (सममित) और सेल्फ-लूप न होने से मुख्य विकर्ण शून्य रहता है।
Q4. In the Adjacency Matrix A of a DIRECTED unweighted graph, what do the sum of row i and the sum of column j represent?
(एक निर्देशित अनवेटेड ग्राफ के Adjacency Matrix A में पंक्ति i का योग और कॉलम j का योग क्रमशः क्या दर्शाते हैं?)
(A) Row i sum = In-Degree of i; Column j sum = Out-Degree of j
(B) Row i sum = shortest path distance from i
(C) Both sums always equal |E|
(D) Row i sum = Out-Degree of i; Column j sum = In-Degree of j
Correct Answer: (D)
[EN] Under the convention A[i][j] = 1 for directed edge i -> j, entries along row i count outgoing edges from i, while entries down column j count incoming edges into j.
[HI] मानक i -> j संकेतन में पंक्ति i से निकलने वाले एजेज़ (Out-Degree) और कॉलम j में आने वाले एजेज़ (In-Degree) गिने जाते हैं।
Q5. What is the time complexity of running a complete Breadth-First Search (BFS) or Depth-First Search (DFS) using an Adjacency Matrix?
(Adjacency Matrix का उपयोग करके पूरा BFS या DFS ट्रैवर्सल चलाने की समय जटिलता क्या होती है?)
(A) O(E log V)
(B) O(V + E)
(C) O(V)
(D) O(V^2)
Correct Answer: (D)
[EN] For each of the V vertices, BFS/DFS must loop across all V columns of its matrix row to inspect adjacent neighbors, taking V * V = O(V^2).
[HI] प्रत्येक V वर्टेक्स के पड़ोसी खोजने हेतु पूरी V लंबाई की पंक्ति जांचनी पड़ती है, जिससे कुल समय V * V = O(V^2) लगता है।
Q6. How many '1' entries appear in the Adjacency Matrix of a simple UNDIRECTED graph with V = 10 vertices and |E| = 18 edges?
(V = 10 वर्टेक्स और |E| = 18 एजेज़ वाले सरल अनिर्देशित ग्राफ के Adjacency Matrix में कुल कितने '1' होंगे?)
(A) 100
(B) 10
(C) 18
(D) 36
Correct Answer: (D)
[EN] Because each undirected edge {u, v} sets two symmetric cells A[u][v] = 1 and A[v][u] = 1, the total number of 1s equals 2 * |E| = 36.
[HI] अनिर्देशित ग्राफ में प्रत्येक एज दो स्थानों A[u][v] और A[v][u] पर 1 रखता है, इसलिए कुल 1 की संख्या 2 * 18 = 36 होगी।
Q7. If A is the 0/1 Adjacency Matrix of a graph, what does the entry (A^3)[u][v] in the cubed matrix A^3 compute?
(यदि A किसी ग्राफ की 0/1 Adjacency Matrix है, तो मैट्रिक्स घात A^3 की प्रविष्टि (A^3)[u][v] क्या गणना करती है?)
(A) Whether vertex u has degree 3
(B) The exact number of walks of length 3 from vertex u to vertex v
(C) The shortest weighted distance between u and v
(D) The number of connected components containing u and v
Correct Answer: (B)
[EN] By matrix multiplication induction, (A^k)[u][v] counts every distinct k-step walk starting at u and ending at v.
[HI] मैट्रिक्स गुणन नियम से (A^k)[u][v] वर्टेक्स u से v तक ठीक k लंबाई के कुल रास्तों (Walks) की संख्या बताता है।
Q8. For which type of graph is an Adjacency Matrix clearly preferred over an Adjacency List?
(किस प्रकार के ग्राफ के लिए Adjacency List की तुलना में Adjacency Matrix को स्पष्ट रूप से बेहतर माना जाता है?)
(A) Dense graphs (|E| close to V^2) requiring frequent O(1) edge queries
(B) Bipartite trees with V = 1,000,000
(C) Huge sparse road networks with millions of vertices and O(V) edges
(D) Graphs where edges are inserted dynamically alongside growing vertices
Correct Answer: (A)
[EN] When E approaches V^2, the V x V matrix wastes almost no space and gives O(1) edge lookup without pointer overhead.
[HI] जब ग्राफ बहुत सघन (Dense, |E| ≈ V^2) हो और बार-बार O(1) में एज जांचनी हो, तब Adjacency Matrix सर्वश्रेष्ठ होती है।
Q9. How are missing (non-existent) edges normally represented in an Adjacency Matrix for a WEIGHTED graph running shortest-path algorithms?
(शॉर्टेस्ट-पाथ एल्गोरिथ्म चलाते समय वेटेड ग्राफ की Adjacency Matrix में अनुपस्थित (Missing) एज को किस मान से दर्शाया जाता है?)
(A) 0 everywhere for missing edges
(B) 1 for all non-existent edges
(C) -1 everywhere including diagonal
(D) Infinity (INF) for i != j, and 0 along the diagonal i == j
Correct Answer: (D)
[EN] Using 0 for missing edges would falsely suggest a zero-cost path exists; INF prevents relaxing nonexistent edges while 0 on A[i][i] represents zero distance to self.
[HI] अनुपस्थित एज को 0 लिखने पर शून्य लागत का भ्रम होगा; इसलिए दो अलग वर्टेक्स के बीच एज न होने पर INF (अनंत) और स्वयं के लिए A[i][i] = 0 रखते हैं।
Q10. Suppose a graph has V = 50,000 vertices and E = 120,000 edges, and each Adjacency Matrix entry is a 4-byte integer. How much RAM does the matrix need?
(यदि किसी ग्राफ में V = 50,000 वर्टेक्स और E = 120,000 एजेज़ हैं तथा प्रत्येक मैट्रिक्स मान 4 बाइट का पूर्णांक है, तो मैट्रिक्स को कितनी RAM चाहिए?)
(A) 200 MB
(B) 1 MB
(C) 480 KB
(D) 10 GB (50,000 * 50,000 * 4 bytes)
Correct Answer: (D)
[EN] 50,000^2 * 4 = 2.5 * 10^9 * 4 = 10^10 bytes (~9.31 GiB / 10 GB), proving why matrices fail on large sparse graphs.
[HI] 50,000 * 50,000 * 4 बाइट = 10^10 बाइट (लगभग 10 GB), जो इतने कम एजेज़ के लिए मेमोरी की भारी बर्बादी है।
Q11. Which classic graph algorithm operates natively on an Adjacency Matrix representation in O(V^3) time?
(निम्नलिखित में से कौन सा प्रसिद्ध एल्गोरिथ्म सीधे Adjacency Matrix पर O(V^3) समय में कार्य करता है?)
(A) Tarjan's bridge finding in O(V + E)
(B) Topological sort via Kahn's queue
(C) Floyd-Warshall All-Pairs Shortest Path algorithm
(D) Kruskal's MST sorting edges only
Correct Answer: (C)
[EN] Floyd-Warshall updates a V x V distance matrix across k = 0..V-1 intermediate vertices in three nested loops taking O(V^3).
[HI] Floyd-Warshall एल्गोरिथ्म V x V दूरी मैट्रिक्स को तीन नेस्टेड लूप में O(V^3) समय में अपडेट करता है।
Q12. In an Adjacency Matrix of a simple graph, what happens when a new vertex is dynamically added to the graph?
(Adjacency Matrix निरूपण में ग्राफ के अंदर एक नया वर्टेक्स जोड़ने पर क्या समस्या आती है?)
(A) Only one extra element is appended in O(1) time
(B) No memory reallocation is ever needed
(C) Only row V+1 is created without adding a column
(D) The entire V x V 2D array must be reallocated and copied to size (V+1) x (V+1) in O(V^2) time
Correct Answer: (D)
[EN] Because matrix dimensions are fixed at V x V, resizing the vertex set requires allocating and copying (V+1)^2 entries.
[HI] मैट्रिक्स का आकार V x V निश्चित होता है, इसलिए नया वर्टेक्स जोड़ने पर (V+1) x (V+1) का नया ब्लॉक बनाकर O(V^2) में कॉपी करना पड़ता है।
Q13. If you want to iterate over all neighbors of a specific vertex u in a graph represented by an Adjacency Matrix, what is the worst-case time complexity?
(Adjacency Matrix से किसी एक वर्टेक्स u के सभी पड़ोसी वर्टेक्स निकालने की समय जटिलता कितनी होती है?)
(A) O(deg(u))
(B) O(1)
(C) O(V^2)
(D) O(V)
Correct Answer: (D)
[EN] Even if u has only 1 neighbor, the matrix does not store a compressed neighbor list, so you must test all V entries A[u][0..V-1].
[HI] भले ही u का केवल 1 ही पड़ोसी हो, फिर भी पूरी पंक्ति के सभी V कॉलम जांचने पड़ते हैं, अतः समय O(V) लगता है।
Q14. In an undirected simple graph's symmetric Adjacency Matrix, how can memory be cut roughly in half while keeping bit flags?
(अनिर्देशित ग्राफ की सममित Adjacency Matrix में बिट फ्लैग्स के साथ मेमोरी को लगभग आधा कैसे किया जा सकता है?)
(A) Store only the upper or lower triangular portion (V*(V-1)/2 bits)
(B) Replace columns with a single 1D degree array
(C) Store only diagonal entries
(D) Delete every second vertex
Correct Answer: (A)
[EN] Because A[i][j] == A[j][i] and diagonal A[i][i] = 0, storing only i < j halves bit storage, though asymptotic space stays Theta(V^2).
[HI] सममित होने के कारण केवल ऊपरी या निचला त्रिभुज (V(V-1)/2 बिट्स) संग्रहीत करके आधी मेमोरी बचाई जा सकती है।
Q15. What does an all-zero row i (except possibly diagonal) in a Directed Graph's Adjacency Matrix indicate about vertex i?
(किसी निर्देशित ग्राफ के Adjacency Matrix में यदि पंक्ति i के सभी मान शून्य (0) हों, तो यह वर्टेक्स i के बारे में क्या बताता है?)
(A) Vertex i is a Sink vertex with Out-Degree = 0
(B) Vertex i has In-Degree = 0
(C) The graph has zero edges anywhere
(D) Vertex i connects to every other vertex
Correct Answer: (A)
[EN] Row i lists outgoing edges i -> j; all zeros mean vertex i has zero outgoing edges (Out-Degree = 0).
[HI] पंक्ति i वर्टेक्स i से बाहर जाने वाले एजेज़ दिखाती है; पूरी पंक्ति शून्य होने का अर्थ है Out-Degree = 0।
Q16. Which statement about Adjacency Matrix graph representation is FALSE?
(Adjacency Matrix ग्राफ निरूपण के संबंध में निम्नलिखित में से कौन सा कथन असत्य (FALSE) है?)
(A) Adjacency Matrix uses O(V + E) memory space when the graph is sparse
(B) Checking if edge (u, v) exists takes O(1) time
(C) Deleting an edge (u, v) takes O(1) time
(D) An undirected graph always yields a symmetric adjacency matrix
Correct Answer: (A)
[EN] An Adjacency Matrix ALWAYS allocates Theta(V^2) space even for sparse graphs; O(V + E) space belongs to Adjacency Lists.
[HI] स्पार्स ग्राफ में भी Adjacency Matrix हमेशा Theta(V^2) मेमोरी ही लेता है; O(V + E) स्पेस केवल Adjacency List की विशेषता है।
Q17. Within Graph Representation: Adjacency Matrix (V x V) Space O(V^2), which adjacency matrix operation directly maps to: "Theta(V^2)"?
(Graph Representation: Adjacency Matrix (V x V) Space O(V^2) में कौन सा Adjacency Matrix Operation सीधे "Theta(V^2)" से संबंधित है?)
(A) Iterate All Neighbors of u
(B) Memory Space Required
(C) Full BFS / DFS Traversal
(D) Check Edge (u, v) Exists
Correct Answer: (B)
[EN] In Graph Representation: Adjacency Matrix (V x V) Space O(V^2), 'Memory Space Required' handles 'Theta(V^2)' (Allocates V x V 2D array regardless of |E|).
[HI] Graph Representation: Adjacency Matrix (V x V) Space O(V^2) में 'Memory Space Required' का कार्य/विवरण 'Theta(V^2)' (Allocates V x V 2D array regardless of |E|) है।
Q18. Which option accurately describes 'Check Edge (u, v) Exists' in Graph Representation: Adjacency Matrix (V x V) Space O(V^2)?
(Graph Representation: Adjacency Matrix (V x V) Space O(V^2) के संदर्भ में 'Check Edge (u, v) Exists' की सही विशेषता कौन सी है?)
(A) Theta(V^2)
(B) O(1)
(C) O(V)
(D) O(V^2)
Correct Answer: (B)
[EN] 'Check Edge (u, v) Exists' provides 'O(1)' — key point: Direct constant-time lookup at cell A[u][v].
[HI] 'Check Edge (u, v) Exists' का मुख्य विवरण 'O(1)' है (Direct constant-time lookup at cell A[u][v])।
Q19. In Graph Representation: Adjacency Matrix (V x V) Space O(V^2), identify the correct parameter for the specification: "O(V)".
(Graph Representation: Adjacency Matrix (V x V) Space O(V^2) में "O(V)" विवरण किस विकल्प के लिए सही है?)
(A) Iterate All Neighbors of u
(B) Check Edge (u, v) Exists
(C) Memory Space Required
(D) Full BFS / DFS Traversal
Correct Answer: (A)
[EN] 'Iterate All Neighbors of u' corresponds to 'O(V)' (Scans every column 0..V-1 in row u).
[HI] 'Iterate All Neighbors of u' का संबंध 'O(V)' (Scans every column 0..V-1 in row u) से है।
Q20. Considering Graph Representation: Adjacency Matrix (V x V) Space O(V^2), what key behavior defines 'Full BFS / DFS Traversal'?
(Graph Representation: Adjacency Matrix (V x V) Space O(V^2) में 'Full BFS / DFS Traversal' की मुख्य भूमिका या मान क्या है?)
(A) Theta(V^2)
(B) O(V^2)
(C) O(1)
(D) O(V)
Correct Answer: (B)
[EN] 'Full BFS / DFS Traversal' represents 'O(V^2)' (Scans row of size V for each of V vertices).
[HI] 'Full BFS / DFS Traversal' का अर्थ/मान 'O(V^2)' है (Scans row of size V for each of V vertices)।
Graph Representation: Adjacency Matrix (V x V) Space O(V^2) — Exam FAQs
Q1: When should I choose an Adjacency Matrix over an Adjacency List in a coding interview or exam?
कोडिंग इंटरव्यू या परीक्षा में Adjacency List के बजाय Adjacency Matrix कब चुननी चाहिए?
[EN] Choose an Adjacency Matrix when V is small (e.g., V <= 1000), the graph is dense (E ~ V^2), you need instant O(1) edge existence checks/removals, or you are implementing Floyd-Warshall.
[HI] जब V छोटा हो (<= 1000), ग्राफ सघन (Dense) हो, बार-बार O(1) में एज जांचना/हटाना हो या Floyd-Warshall चलाना हो, तब Adjacency Matrix चुनें।
Q2: How do you store parallel (multiple) edges in an Adjacency Matrix?
Adjacency Matrix में समानांतर (Parallel / Multiple) एजेज़ को कैसे दर्शाया जाता है?
[EN] In an unweighted multigraph, set A[i][j] equal to the integer count of edges between i and j instead of just 0 or 1 (though weighted multigraphs usually prefer Adjacency Lists).
[HI] अनवेटेड मल्टीग्राफ में A[i][j] में 0 या 1 के स्थान पर i और j के बीच मौजूद एजेज़ की कुल संख्या लिख दी जाती है।
Q3: Why is BFS/DFS O(V^2) on an Adjacency Matrix even if there are only 3 edges?
यदि ग्राफ में केवल 3 एजेज़ हों तब भी Adjacency Matrix पर BFS/DFS चलाने में O(V^2) समय क्यों लगता है?
[EN] Because discovering neighbors of each visited vertex u forces scanning all V columns in row u, totaling V * V checks across V vertices.
[HI] क्योंकि हर विजिट किए गए वर्टेक्स u के पड़ोसी खोजने के लिए उसकी पूरी V आकार की पंक्ति के सभी कॉलम जांचने पड़ते हैं।
Post a Comment
Post a Comment