This article summarizes the data structure diagram related knowledge and Leetcode high-frequency problems. The first half of this article summarizes knowledge points and code reference from JavaScript data structure and algorithm.
What is the figure
- Figure is
The network structureAbstract model, is a set of abstract modelsedgeOf the connectionnode. - A graph can represent any binary relationship, a road, a flight.
- JS has no diagrams, but you can build diagrams with Object and Array.
- Graph representation: adjacency matrix, adjacency list, incidence matrix.
- Depth-first traversal of a graph: Search as deep as possible for branches of the graph.
- Breadth-first traversal of a graph: the node closest to the root node is visited first
Depth-first traversal of the graph
- Accessing the root node
- For the root node
Adjacent nodes that have not been visitedDepth-first traversal is carried out one by one
const graph = {
0: [1, 2],
1: [2],
2: [0, 3],
3: [3]
};
const visited = new Set();
const dfs = (n) => {
visited.add(n);
graph[n].forEach(c => {
if (!visited.has(c)) {
dfs(c);
}
});
}
dfs(2); // 2 -> 0 -> 1 -> 3
Copy the codeBreadth-first traversal of the graph
- Create a queue and queue the root node
- Take the team leader out of the team and visit
- Join the queue head’s unvisited adjacent nodes
- Repeat steps 2 and 3 until the queue is empty
const visited = new Set(); const bfs = (root) => { visited.add(root); const q = [root]; while (q.length) { const n = q.shift(); console.log(n); graph[n].forEach(c => { if (! visited.has(c)) { q.push(c); visited.add(c); } }) } } bfs(2); // 2 -> 0 -> 3 -> 1Copy the codeLeetcode topic
417. Pacific Atlantic current problems
Ideas:
- Depth-first traversal of the graph
Code display:
/** * @param {number[][]} heights * @return {number[][]} */ var pacificAtlantic = function(heights) { if (! heights || ! heights[0]) return []; const m = heights.length; const n = heights[0].length; const flow1 = Array.from({ length: m }, () => new Array(n).fill(false)); const flow2 = Array.from({ length: m }, () => new Array(n).fill(false)); const dfs = (r, c, flow) => { flow[r][c] = true; [[r-1, c], [r+1, c], [r, c-1], [r, c+1]].forEach(([nr, Nc]) = > {the if (/ / guarantee in nr > = 0 && nr matrix < m && nc > = 0 && nc < n && / / node has not been visited! Flow (nr)/nc && / / that upstream heights (nr)/nc > = heights [r] [c]) {DFS (nr, nc, flow); }}); } for (let r = 0; r < m; r++) { dfs(r, 0, flow1); dfs(r, n-1, flow2); } for (let c = 0; c < n; c++) { dfs(0, c, flow1); dfs(m-1, c, flow2); } // Collect the coordinates of the flow to the two oceans const res = []; for (let r = 0; r < m; r++) { for (let c = 0; c < n; c++) { if (flow1[r][c] && flow2[r][c]) { res.push([r, c]); } } } return res; };Copy the codeComplexity analysis:
- Time complexity: O(MN). M is the column of the matrix, n is the row of the matrix.
- Space complexity: O(Mn)
133. Cloning figure
Method 1: Depth-first traversal
/** * @param {Node} node * @return {Node} */ var cloneGraph = function(node) { if (! node) return; const visited = new Map(); const dfs = (n) => { const nCopy = new Node(n.val); visited.set(n, nCopy); (n.neighbors || []).forEach(ne => { if (! visited.has(ne)) { dfs(ne); } nCopy.neighbors.push(visited.get(ne)); }); } dfs(node); return visited.get(node); };Copy the codeMethod two: breadth-first traversal
/** * @param {Node} node * @return {Node} */ var cloneGraph = function(node) { if (! node) return; const visited = new Map(); const q = [node]; visited.set(node, new Node(node.val)); while (q.length) { const n = q.shift(); (n.neighbors || []).forEach(ne => { if (! visited.has(ne)) { q.push(ne); visited.set(ne, new Node(ne.val)); } visited.get(n).neighbors.push(visited.get(ne)); }) } return visited.get(node); };Copy the codeComplexity analysis:
- Time complexity: O(n). N represents the number of nodes in the graph.
- Space complexity: O(n)
207. The curriculum
Refer to the “graphic” topological sort | timetable problem
Code display:
/** * @param {number} numCourses * @param {number[][]} prerequisites * @return {boolean} */ var canFinish = function(numCourses, prerequisites) { const inDegree = new Array(numCourses).fill(0); // const map = {}; For (let I = 0; i < prerequisites.length; i++) { inDegree[prerequisites[i][0]]++; = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = Map [Prerequisites [I][1]] = [Prerequisites [I][0]]; }} const queue = []; // Create an array of dependencies and place dependencies in it. For (let I = 0; i < inDegree.length; If (inDegree[I] === 0) queue.push(I); } let count = 0; while (queue.length) { const n = queue.shift(); // count++; // toEnQueue +1 const toEnQueue = map[n]; ToEnQueue &&toenqueue.length &&toenqueue.foreach (item => {inDegree[item]--; If (inDegree[item] === 0) {queue. Push (item); // Push dependency classes to queue}}); } return count === numCourses; // If the selected classes are equal to the total number of classes, return true, otherwise return false};Copy the codeComplexity analysis:
- Time complexity: O(m+ N) : m represents the number of courses, and n represents the number of prerequisite courses.
- Space complexity: O(m+ N)
210. Curriculum II
Code reference form step by step from topological sorting ideas, class BFS
Code display:
/** * @param {number} numCourses * @param {number[][]} prerequisites * @return {number[]} */ var findOrder = function(numCourses, prerequisites) { const inDegree = new Array(numCourses).fill(0); // const map = {}; For (let I = 0; i < prerequisites.length; i++) { inDegree[prerequisites[i][0]]++; = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = Map [Prerequisites [I][1]] = [Prerequisites [I][0]]; }} const queue = []; // Create an array of dependencies and place dependencies in it. For (let I = 0; i < inDegree.length; If (inDegree[I] === 0) queue.push(I); Const res = []; // inDegree[I] const res = []; While (queue.length) {const n = queue.shift(); // Res.push (n); Const toEnQueue = map[n]; const toEnQueue = map[n]; ToEnQueue &&toenqueue.length &&toenqueue.foreach (item => {inDegree[item]--; If (inDegree[item] === 0) {queue. Push (item); // Push dependency classes to queue}}); } return res.length === numCourses ? res : []; // The selected classes are equal to the total number of classes, return res, otherwise return []};Copy the codeComplexity analysis:
- Time complexity: O(m+ N) : m represents the number of courses, and n represents the number of prerequisite courses.
- Space complexity: O(m+ N)
785. Judge the binary graph
Reference from “hand painted illustration” BFS idea | determine binary chart
Code display:
/** * @param {number[][]} graph * @return {boolean} */ var isBipartite = function(graph) { const visited = new Array(graph.length); For (let I = 0; i < visited.length; I ++) {// Iterate over each vertex if (visited[I]) continue; Const queue = [I]; // If the vertex is already colored, continue traversing const queue = [I]; // I visited[I] = 1; While (queue.length) {const cur = queue.shift(); // const curColor = visited[cur]; Const neighborColor = -curcolor; For (let I = 0; i < graph[cur].length; Const neighbor = graph[cur][I]; const neighbor = graph[cur][I]; If (visited[neighbor] == undefined) {// Visited [neighbor] = neighborColor; / / coloring queue. Push (neighbor); } else if (visited[neighbor]! NeighborColor) {return false; } } } } return true; // No error color is found};Copy the codeComplexity analysis:
- Time complexity: O(m+n) : n is the number of vertices and m is the number of edges.
- Space complexity: O(n)
1334. City with the fewest neighbors within the threshold distance
The reference solution
Code display:
/** * @param {number} n * @param {number[][]} edges * @param {number} distanceThreshold * @return {number} */ var findTheCity = function(n, edges, distanceThreshold) { const max = Number.MAX_SAFE_INTEGER; const distance = Array.from({length: n}, () => new Array(n).fill(max)); // Build an n*n array // console.log(distance); for (let i = 0; i < edges.length; i++) { distance[edges[i][0]][edges[i][1]] = distance[edges[i][1]][edges[i][0]] = edges[i][2]; } for (let i = 0; i < n; ++i) { for (let j = 0; j < n; ++j) { if (i === j || distance[j][i] === max) continue; for (let k = j + 1; k < n; ++k) { distance[k][j] = distance[j][k] = Math.min(distance[j][k], distance[j][i] + distance[i][k]); } } } let city = 0; let minNum = n; for (let i = 0; i < n; ++i) { let curNum = 0; for (let j = 0; j < n; ++j) { distance[i][j] <= distanceThreshold && ++curNum; } if (curNum <= minNum) { minNum = curNum; city = i; } } return city; };Copy the codeConclusion:
A graph is similar to a tree, which is an abstract model of a hierarchical data structure, and a graph is an abstract model of a network structure. The possibilities are a little bit more complicated.