wdcp设置网站安全,php网站开发案例教程,网站公告模板代码,沈阳微信网站建设当然#xff0c;让我们深入探讨一下JavaScript中的图数据结构#xff0c;并列出一些常见的面试题及其代码示例。
图数据结构详解
图#xff08;Graph#xff09;是一种非线性的数据结构#xff0c;由节点#xff08;也称为顶点#xff09;和连接这些节点的边组成。节点…当然让我们深入探讨一下JavaScript中的图数据结构并列出一些常见的面试题及其代码示例。
图数据结构详解
图Graph是一种非线性的数据结构由节点也称为顶点和连接这些节点的边组成。节点可以表示实体如人、地点、事物等而边则表示这些实体之间的关系。图可以分为有向图和无向图
有向图Directed Graph边有方向即从一个节点指向另一个节点。无向图Undirected Graph边没有方向表示两个节点之间的连接。
图的表示方法 邻接矩阵Adjacency Matrix 使用一个二维数组表示如果节点i和节点j之间有边则数组[i][j]为1或边的权重否则为0。优点查找边是否存在很快O(1)。缺点空间复杂度较高尤其是稀疏图边的数量远小于节点对数量的图。 邻接表Adjacency List 使用一个数组或链表数组表示每个节点对应一个链表链表中存储该节点连接的所有节点。优点空间复杂度较低适合稀疏图。缺点查找边是否存在的时间复杂度较高O(V)。
图的遍历 深度优先搜索DFS, Depth-First Search 使用栈递归或显式栈遍历节点尽可能深入搜索每一个分支。可以用递归或迭代实现。 广度优先搜索BFS, Breadth-First Search 使用队列逐层遍历节点。常用于寻找最短路径在无权图中。
常见面试题及其代码
判断图是否有环DFS
function hasCycle(graph) {const visited new Set();const recursionStack new Set();function dfs(node) {if (recursionStack.has(node)) return true;if (visited.has(node)) return false;visited.add(node);recursionStack.add(node);for (const neighbor of graph[node] || []) {if (dfs(neighbor)) return true;}recursionStack.delete(node);return false;}for (const node in graph) {if (dfs(node)) return true;}return false;
}图的深度优先遍历DFS
function dfsTraversal(graph, start, visited new Set()) {if (visited.has(start)) return;visited.add(start);console.log(start);for (const neighbor of graph[start] || []) {dfsTraversal(graph, neighbor, visited);}
}图的广度优先遍历BFS
function bfsTraversal(graph, start) {const queue [start];const visited new Set();while (queue.length 0) {const node queue.shift();if (!visited.has(node)) {visited.add(node);console.log(node);for (const neighbor of graph[node] || []) {if (!visited.has(neighbor)) {queue.push(neighbor);}}}}
}计算图的拓扑排序Kahn’s Algorithm
function topologicalSort(graph) {const inDegree {};const result [];const queue [];// Initialize in-degree mapfor (const node in graph) {inDegree[node] 0;}// Calculate in-degreesfor (const node in graph) {for (const neighbor of graph[node] || []) {inDegree[neighbor] (inDegree[neighbor] || 0) 1;}}// Enqueue nodes with zero in-degreefor (const node in inDegree) {if (inDegree[node] 0) {queue.push(node);}}// Process nodeswhile (queue.length 0) {const node queue.shift();result.push(node);for (const neighbor of graph[node] || []) {inDegree[neighbor]--;if (inDegree[neighbor] 0) {queue.push(neighbor);}}}// If there was a cycle, not all nodes would be visitedreturn result.length Object.keys(graph).length ? result : [];
}计算所有节点对之间的最短路径Floyd-Warshall Algorithm
function floydWarshall(graph) {const n Object.keys(graph).length;const dist JSON.parse(JSON.stringify(graph));for (let k 0; k n; k) {for (let i 0; i n; i) {for (let j 0; j n; j) {if (dist[i][k] ! Infinity dist[k][j] ! Infinity dist[i][k] dist[k][j] dist[i][j]) {dist[i][j] dist[i][k] dist[k][j];}}}}return dist;
}检测二分图Bipartite Graph
function isBipartite(graph) {const colors {};const queue [];function bfs(node, color) {colors[node] color;queue.push(node);while (queue.length 0) {const currentNode queue.shift();const currentColor colors[currentNode];for (const neighbor of graph[currentNode] || []) {if (!colors[neighbor]) {colors[neighbor] -currentColor;queue.push(neighbor);} else if (colors[neighbor] currentColor) {return false;}}}return true;}for (const node in graph) {if (!colors[node]) {if (!bfs(node, 1)) {return false;}}}return true;
}图的最小生成树Prim’s Algorithm
function primMST(graph) {const n Object.keys(graph).length;const key new Array(n).fill(Infinity);const parent new Array(n).fill(-1);const inMST new Array(n).fill(false);key[0] 0;parent[0] -1;for (let count 0; count n - 1; count) {let u -1, min Infinity;for (let v 0; v n; v) {if (!inMST[v] key[v] min) {u v;min key[v];}}inMST[u] true;for (const v of graph[u] || []) {if (!inMST[v] graph[u][v] key[v]) {parent[v] u;key[v] graph[u][v];}}}// Construct MSTconst mst [];for (let i 1; i n; i) {mst.push([parent[i], i, graph[parent[i]][i]]);}return mst;
}}图的克鲁斯克尔算法Kruskal’s Algorithm
class UnionFind {constructor(n) {this.parent new Array(n);for (let i 0; i n; i) {this.parent[i] i;}}find(u) {if (this.parent[u] ! u) {this.parent[u] this.find(this.parent[u]); // 路径压缩使得后续查找更快}return this.parent[u];}union(u, v) {let rootU this.find(u);let rootV this.find(v);if (rootU ! rootV) {this.parent[rootU] rootV;}}
}function kruskalMST(graph) {// 图的表示graph [ [u, v, weight], ... ]let edges graph.slice().sort((a, b) a[2] - b[2]); // 排序边let n new Set(); // 存储所有顶点for (let edge of edges) {n.add(edge[0]);n.add(edge[1]);}let uf new UnionFind(n.size);let mst [];let mstCost 0;for (let edge of edges) {let u edge[0];let v edge[1];let weight edge[2];if (uf.find(u) ! uf.find(v)) {uf.union(u, v);mst.push(edge);mstCost weight;}}return {mst: mst,cost: mstCost};
}// 示例使用
let graph [[0, 1, 10],[0, 2, 6],[0, 3, 5],[1, 3, 15],[2, 3, 4]
];let result kruskalMST(graph);
console.log(Edges in MST:, result.mst);
console.log(Total cost of MST:, result.cost);
