图数据结构详解

为什么前端开发者需要了解图？

图是一种非常强大的数据结构，在前端开发中有很多实际应用：

• 社交网络关系展示
• 前端路由导航
• 组件依赖分析
• 状态管理流程图
• 数据可视化

图的表示方法

1. 邻接矩阵实现

适合稠密图，空间复杂度 O(V²)

class GraphMatrix {
    constructor(vertices, edges) {
        this.vertices = [];     // 存储顶点
        this.adjMatrix = [];    // 邻接矩阵
        
        // 初始化顶点和矩阵
        vertices.forEach(v => this.addVertex(v));
        edges.forEach(([v1, v2]) => this.addEdge(v1, v2));
    }

    addVertex(val) {
        const n = this.vertices.length;
        this.vertices.push(val);
        // 为新顶点扩展矩阵
        this.adjMatrix.push(new Array(n).fill(0));
        this.adjMatrix.forEach(row => row.push(0));
    }

    addEdge(i, j) {
        if (i === j) return;
        this.adjMatrix[i][j] = 1;
        this.adjMatrix[j][i] = 1; // 无向图需要对称
    }
}

2. 邻接表实现

适合稀疏图，空间复杂度 O(V + E)

class GraphList {
    constructor(edges) {
        this.adjList = new Map();
        
        // 添加所有边
        edges.forEach(([v1, v2]) => {
            this.addVertex(v1);
            this.addVertex(v2);
            this.addEdge(v1, v2);
        });
    }

    addVertex(v) {
        if (!this.adjList.has(v)) {
            this.adjList.set(v, []);
        }
    }

    addEdge(v1, v2) {
        this.adjList.get(v1).push(v2);
        this.adjList.get(v2).push(v1); // 无向图需要双向添加
    }
}

图的遍历算法

1. 广度优先搜索 (BFS)

适用场景：寻找最短路径、层级遍历

function bfs(graph, startNode) {
    const visited = new Set();
    const queue = [startNode];
    
    while (queue.length) {
        const node = queue.shift();
        if (visited.has(node)) continue;
        
        // 处理节点
        console.log(node);
        visited.add(node);
        
        // 将未访问的邻接节点加入队列
        graph.adjList.get(node)?.forEach(neighbor => {
            if (!visited.has(neighbor)) {
                queue.push(neighbor);
            }
        });
    }
}

2. 深度优先搜索 (DFS)

适用场景：拓扑排序、检测环、路径查找

function dfs(graph, startNode, visited = new Set()) {
    if (visited.has(startNode)) return;
    
    // 处理节点
    console.log(startNode);
    visited.add(startNode);
    
    // 递归访问邻接节点
    graph.adjList.get(startNode)?.forEach(neighbor => {
        dfs(graph, neighbor, visited);
    });
}

实际应用示例

1. 检测循环依赖

function hasCyclicDependency(dependencies) {
    const graph = new GraphList(dependencies);
    const visited = new Set();
    const path = new Set();
    
    function dfs(node) {
        if (path.has(node)) return true;  // 发现环
        if (visited.has(node)) return false;
        
        path.add(node);
        visited.add(node);
        
        for (const neighbor of graph.adjList.get(node)) {
            if (dfs(neighbor)) return true;
        }
        
        path.delete(node);
        return false;
    }
    
    for (const node of graph.adjList.keys()) {
        if (dfs(node)) return true;
    }
    return false;
}

性能对比

操作	邻接矩阵	邻接表
添加顶点	O(V²)	O(1)
添加边	O(1)	O(1)
查找边	O(1)	O(V)
内存占用	O(V²)	O(V+E)

实践建议

1. 对于小规模图（顶点<100），两种实现方式都可以
2. 对于大规模稀疏图，优先使用邻接表
3. 需要频繁查询边的存在性时，考虑使用邻接矩阵
4. 在前端项目中，通常邻接表实现更实用

相关练习

1. LeetCode 207: 课程表（依赖关系）
2. LeetCode 133: 克隆图
3. LeetCode 997: 找到小镇的法官（出入度）