https://thita.ai/_next/static/chunks/5301.ee3bc7f1c0d423d9.js

1"use strict";(self.webpackChunk_N_E=self.webpackChunk_N_E||[]).push([[5301],{5301:e=>{e.exports=JSON.parse('{"metadata":{"id":"dsa-basics-graphs-basics-adjacency-list-and-matrix","name":"Adjacency List and Matrix","category":"Graph","description":"Build adjacency-list and adjacency-matrix representations for the undirected graph with vertex order A, B, C, D by inserting A-B, A-C, B-D, and C-D in order.","difficulty":"Easy","estimatedTime":"6 minutes","prerequisites":["graph-terminology-and-types"]},"layout":{"type":"graph","nodes":[{"id":"A","value":"A","x":180,"y":120},{"id":"B","value":"B","x":420,"y":120},{"id":"C","value":"C","x":180,"y":320},{"id":"D","value":"D","x":420,"y":320}],"edges":[{"from":"A","to":"B","directed":false},{"from":"A","to":"C","directed":false},{"from":"B","to":"D","directed":false},{"from":"C","to":"D","directed":false}],"codeBlocks":[{"id":"dsa-basics-graphs-basics-adjacency-list-and-matrix-code","language":"pseudo","lines":["Assign each vertex a fixed index in the ordered vertex list","Create one empty neighbor list per vertex and a V by V zero matrix","For each undirected edge u-v in the given order","Append v to u\'s list and append u to v\'s list","Set matrix[u,v] and matrix[v,u] to 1","hasEdge(u, v): matrix[u,v] != 0 or v in neighbors[u]"]}],"regions":{"codePanel":{"codeBlockId":"dsa-basics-graphs-basics-adjacency-list-and-matrix-code","position":"right","title":"Pseudocode"}}},"initialState":{"pointers":{"source":{"id":"source","type":"custom","index":0,"nodeId":"A","label":"next u","color":"#2563EB"},"target":{"id":"target","type":"custom","index":1,"nodeId":"B","label":"next v","color":"#DC2626"}},"highlights":[],"flags":{"isUndirected":true,"processedEdges":0,"matrixIsSymmetric":true},"annotation":"State 0: vertex order is [A,B,C,D]. Initialize A:[], B:[], C:[], D:[] and a 4 by 4 matrix of zeros. The next input edge is A-B.","aux":{"vertexOrder":["A","B","C","D"],"adjacencyList":{"A":[],"B":[],"C":[],"D":[]},"matrix":{"vertices":["A","B","C","D"],"rows":[[0,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,0]]}},"uiState":{"activeCodeBlockId":"dsa-basics-graphs-basics-adjacency-list-and-matrix-code","activeCodeLine":2}},"steps":[{"stepNumber":1,"title":"Insert the undirected edge A-B","description":"Add B to A\'s list and A to B\'s list. Set both M[A,B] and M[B,A] to 1.","explanation":"A-B is the first processed edge. Because the graph is undirected, both representations must record the connection in both directions.","changes":{"pointers":{"target":{"index":2,"nodeId":"C"}},"highlights":{"add":[{"index":0,"type":"primary"},{"index":1,"type":"secondary"}],"remove":[],"clear":false},"flags":{"processedEdges":1},"aux":{"adjacencyList":{"update":[{"vertex":"A","neighbors":["B"]},{"vertex":"B","neighbors":["A"]}]},"matrix":{"update":[{"row":0,"column":1,"value":1},{"row":1,"column":0,"value":1}]}},"annotation":"State 1: A:[B], B:[A], C:[], D:[]. The matrix has M[A,B]=1 and M[B,A]=1; all other cells remain 0."},"technicalDetails":{"complexity":"An adjacency-list insertion is O(1) amortized per endpoint; assigning two matrix cells is O(1).","insight":"For every processed undirected edge u-v, record v in u\'s list, u in v\'s list, and set both symmetric matrix cells.","warning":"Appending only B to A would incorrectly leave B\'s neighbor list empty."},"highlight":true,"uiState":{"activeCodeBlockId":"dsa-basics-graphs-basics-adjacency-list-and-matrix-code","activeCodeLine":5}},{"stepNumber":2,"title":"Insert the undirected edge A-C","description":"Append C after B in A\'s list and append A to C\'s list. Set M[A,C] and M[C,A] to 1.","explanation":"The list for A preserves the given edge-processing order, so A becomes [B,C]. The new matrix entries use A\'s index 0 and C\'s index 2.","changes":{"pointers":{"source":{"index":1,"nodeId":"B"},"target":{"index":3,"nodeId":"D"}},"highlights":{"add":[{"index":2,"type":"secondary"}],"remove":[1],"clear":false},"flags":{"processedEdges":2},"aux":{"adjacencyList":{"update":[{"vertex":"A","neighbors":["B","C"]},{"vertex":"C","neighbors":["A"]}]},"matrix":{"update":[{"row":0,"column":2,"value":1},{"row":2,"column":0,"value":1}]}},"annotation":"State 2: A:[B,C], B:[A], C:[A], D:[]. Set M[A,C]=1 and M[C,A]=1. The next input edge is B-D."},"technicalDetails":{"complexity":"This edge still performs two list appends and two constant-time matrix writes.","insight":"The invariant is now visible for two edges: every processed edge appears once in each endpoint\'s neighbor list and in two symmetric matrix cells.","warning":"Keep the fixed map A→0, B→1, C→2, D→3; changing index order can mark the wrong matrix cell."},"highlight":true,"uiState":{"activeCodeBlockId":"dsa-basics-graphs-basics-adjacency-list-and-matrix-code","activeCodeLine":5}},{"stepNumber":3,"title":"Insert the undirected edge B-D","description":"Append D to B\'s existing list [A] and append B to D\'s empty list. Set M[B,D] and M[D,B] to 1.","explanation":"B\'s neighbor list becomes [A,D], while D receives its first neighbor B. The matrix positions are row 1 column 3 and row 3 column 1.","changes":{"pointers":{"source":{"index":2,"no

1deId":"C"}},"highlights":{"add":[{"index":1,"type":"primary"},{"index":3,"type":"secondary"}],"remove":[0,2],"clear":false},"flags":{"processedEdges":3},"aux":{"adjacencyList":{"update":[{"vertex":"B","neighbors":["A","D"]},{"vertex":"D","neighbors":["B"]}]},"matrix":{"update":[{"row":1,"column":3,"value":1},{"row":3,"column":1,"value":1}]}},"annotation":"State 3: A:[B,C], B:[A,D], C:[A], D:[B]. Set M[B,D]=1 and M[D,B]=1. The next input edge is C-D."},"technicalDetails":{"complexity":"The representation update remains O(1) per endpoint, independent of the number of vertices.","insight":"Processed edges are symmetric in the matrix: M[B,D]=M[D,B]=1.","warning":"A V by V matrix is sized by the 4 vertices, not by the number of processed edges."},"highlight":true,"uiState":{"activeCodeBlockId":"dsa-basics-graphs-basics-adjacency-list-and-matrix-code","activeCodeLine":5}},{"stepNumber":4,"title":"Insert the undirected edge C-D","description":"Append D to C\'s list and C to D\'s list. Set M[C,D] and M[D,C] to 1 to complete both representations.","explanation":"All four input edges are now processed. Each endpoint owns one neighbor-list entry for every incident edge, and every matrix 1 has a matching symmetric 1.","changes":{"pointers":{"source":{"index":0,"nodeId":"A","label":"query u"},"target":{"index":3,"nodeId":"D","label":"query v"}},"highlights":{"add":[{"index":2,"type":"primary"}],"remove":[1],"clear":false},"flags":{"processedEdges":4},"aux":{"adjacencyList":{"update":[{"vertex":"C","neighbors":["A","D"]},{"vertex":"D","neighbors":["B","C"]}]},"matrix":{"update":[{"row":2,"column":3,"value":1},{"row":3,"column":2,"value":1}]}},"annotation":"State 4: final lists are A:[B,C], B:[A,D], C:[A,D], D:[B,C]. Final matrix rows are A:0110, B:1001, C:1001, D:0110. Query A-D is next."},"technicalDetails":{"complexity":"The matrix uses O(V\xb2) space, while the undirected adjacency list uses O(V+E) stored entries.","insight":"After the complete edge list, the invariant holds for every edge: M[u,v]=M[v,u]=1 and each edge is present in both endpoint lists.","warning":"Writing only M[C,D] would break matrix symmetry and make the reverse query D-C fail."},"highlight":true,"uiState":{"activeCodeBlockId":"dsa-basics-graphs-basics-adjacency-list-and-matrix-code","activeCodeLine":5}},{"stepNumber":5,"title":"Query whether A-D exists","description":"Inspect M[A,D], which is 0, and inspect A\'s list [B,C], which does not contain D.","explanation":"Both representations agree that A-D was never inserted. Therefore no edge exists between A and D.","changes":{"highlights":{"add":[{"index":0,"type":"current"},{"index":3,"type":"comparing"}],"remove":[2,3],"clear":false},"flags":{"queryEdgeExists":false},"annotation":"State 5: query A-D. M[A,D]=0, and D is absent from A:[B,C], so no A-D edge exists."},"technicalDetails":{"complexity":"Matrix lookup is O(1). Searching A\'s adjacency list is O(deg(A)), which is 2 here.","insight":"A matrix gives direct edge-existence lookup, while an adjacency list answers by checking the source vertex\'s neighbors.","warning":"Do not infer an edge from a path: A can reach D through B or C, but the direct edge A-D does not exist."},"highlight":true,"uiState":{"activeCodeBlockId":"dsa-basics-graphs-basics-adjacency-list-and-matrix-code","activeCodeLine":6}}],"conclusion":{"keyTakeaways":["For an undirected edge u-v, add each endpoint to the other\'s adjacency list.","For an undirected adjacency matrix, set both M[u,v] and M[v,u] to 1.","With order [A,B,C,D], the final matrix rows are 0110, 1001, 1001, 0110.","A-D is not an edge because M[A,D]=0 and D is absent from A\'s neighbor list."],"commonMistakes":["Adding an undirected edge to only one neighbor list.","Setting only one of the two symmetric matrix entries.","Allocating the matrix by edge count instead of using V by V dimensions.","Using a different vertex-to-index order for different matrix updates."],"nextSteps":["Compare adjacency-list and adjacency-matrix space usage on sparse and dense graphs.","Traverse this graph with breadth-first search using the adjacency lists."],"practiceProblems":[]}}')}}]);