当然，让我们深入探讨一下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 map
for (const node in graph) {
inDegree[node] = 0;
}
// Calculate in-degrees
for (const node in graph) {
for (const neighbor of graph[node] || []) {
inDegree[neighbor] = (inDegree[neighbor] || 0) + 1;
}
}
// Enqueue nodes with zero in-degree
for (const node in inDegree) {
if (inDegree[node] === 0) {
queue.push(node);
}
}
// Process nodes
while (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 visited
return 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 MST
const 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);
