Javascript数据结构——图Graph

当然，让我们深入探讨一下JavaScript中的图数据结构，并列出一些常见的面试题及其代码示例。

图数据结构详解

图（Graph）是一种非线性的数据结构，由节点（也称为顶点）和连接这些节点的边组成。节点可以表示实体（如人、地点、事物等），而边则表示这些实体之间的关系。图可以分为有向图和无向图：

• 有向图（Directed Graph）：边有方向，即从一个节点指向另一个节点。
• 无向图（Undirected Graph）：边没有方向，表示两个节点之间的连接。

图的表示方法

1. 邻接矩阵（Adjacency Matrix）：

   • 使用一个二维数组表示，如果节点i和节点j之间有边，则数组[i][j]为1（或边的权重），否则为0。
   • 优点：查找边是否存在很快（O(1)）。
   • 缺点：空间复杂度较高，尤其是稀疏图（边的数量远小于节点对数量的图）。

2. 邻接表（Adjacency List）：

   • 使用一个数组或链表数组表示，每个节点对应一个链表，链表中存储该节点连接的所有节点。
   • 优点：空间复杂度较低，适合稀疏图。
   • 缺点：查找边是否存在的时间复杂度较高（O(V)）。

图的遍历

1. 深度优先搜索（DFS, Depth-First Search）：

   • 使用栈（递归或显式栈）遍历节点，尽可能深入搜索每一个分支。
   • 可以用递归或迭代实现。

2. 广度优先搜索（BFS, Breadth-First Search）：

   • 使用队列逐层遍历节点。
   • 常用于寻找最短路径（在无权图中）。

常见面试题及其代码

1. 判断图是否有环（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;
}

2. 图的深度优先遍历（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);}
}

3. 图的广度优先遍历（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);}}}}
}

4. 计算图的拓扑排序（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 : [];
}

5. 计算所有节点对之间的最短路径（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;
}

6. 检测二分图（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;
}

7. 图的最小生成树（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);