Skip to content

图

一句话解释

图是由节点(顶点)和连接它们的边构成的数据结构,用于建模实体间的关系。

用大白话说

图是由顶点(节点)和连接它们的边(链接)构成的集合。与树不同,图没有单一根节点,节点可有多条连接、存在环,甚至有指向自身的边。图可建模任何关系网络:社交网络、道路地图、网页(页面互链)、模块间依赖。图可分为有向(边有方向,如单行道)或无向(边双向)。边可带权(如距离)或不带权。两种常见表示是邻接表(每个节点存其邻居列表)和邻接矩阵(0/1 或权重的二维网格)。关键图算法包括广度优先搜索(无权图最短路径)、深度优先搜索(一路深入再回溯)、Dijkstra 算法(带权最短路径)和拓扑排序(对有依赖的任务排序)。

示例

javascript
// 邻接表表示
const graph = {
  A: ["B", "C"],
  B: ["A", "D"],
  C: ["A", "D"],
  D: ["B", "C"],
};

// BFS — 访问从起点可达的所有节点
function bfs(graph, start) {
  const visited = new Set([start]);
  const queue = [start];
  const order = [];
  while (queue.length) {
    const node = queue.shift();
    order.push(node);
    graph[node].forEach(n => {
      if (!visited.has(n)) { visited.add(n); queue.push(n); }
    });
  }
  return order;
}
console.log(bfs(graph, "A")); // ["A", "B", "C", "D"]

图以邻接表存储。BFS 用队列逐层访问邻居,并用 visited 集合避免成环。

相关术语

相关资源

相关课程

解读错误信息

用大白话解释常见错误——什么意思、为什么发生、如何修复。

查看错误

← 返回术语表