当前位置： 首页 > article >正文

Javascript数据结构——图Graph

article 2025/1/3 4:04:19

当然，让我们深入探讨一下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;
}
  1. 图的深度优先遍历（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);
    }
}
  1. 图的广度优先遍历（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);
                }
            }
        }
    }
}
  1. 计算图的拓扑排序（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 : [];
}
  1. 计算所有节点对之间的最短路径（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;
}
  1. 检测二分图（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;
}
  1. 图的最小生成树（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);

http://www.kler.cn/a/458885.html

相关文章：

  • 2021.12.28基于UDP同信的相关流程
  • 浅谈下Spring MVC的执行流程
  • TypeScript 后端开发中的热重载编译处理
  • QT----------文件系统操作和文件读写
  • 线性代数期末复习 [基础篇]
  • Java Day1回顾简介-----变量命名规则
  • C++ 设计模式：代理模式（Proxy Pattern）
  • 力扣第116题：填充每个节点的下一个右侧节点指针 - C语言解法
  • 代码随想录day21 | leetcode 77.组合 77.组合 加剪枝操作 216.组合总和III
  • [图形渲染]【Unity Shader】【游戏开发】 Shader数学基础17-法线变换基础与应用
  • Java：192 基于SSM框架的失物招领信息管理系统
  • debian12安装docker
  • Linux的进程替换以及基础IO
  • 初学stm32 --- 高级定时器PWM输入模式
  • Github 2024-12-26 Go开源项目日报 Top10
  • （二）当人工智能是一个函数时，怎么去训练它？
  • 【机器学习】机器学习的基本分类-半监督学习-Ladder Networks
  • 【day20】集合深入探讨
  • Optional类：避免NullPointerException
  • Go语言的字符串处理
  • 每天40分玩转Django：Django Channels
  • react-native键盘遮盖底部输入框问题修复
  • 对于多个网站的爬虫管理和配置支持
  • 前端处理跨域的几种方式
  • AI 加持下的智能家居行业：变革、挑战与机遇
  • 深度学习-78-大模型量化之Quantization Aware Training量化感知训练QAT