图
一句话解释
图是由节点(顶点)和连接它们的边构成的数据结构,用于建模实体间的关系。
用大白话说
图是由顶点(节点)和连接它们的边(链接)构成的集合。与树不同,图没有单一根节点,节点可有多条连接、存在环,甚至有指向自身的边。图可建模任何关系网络:社交网络、道路地图、网页(页面互链)、模块间依赖。图可分为有向(边有方向,如单行道)或无向(边双向)。边可带权(如距离)或不带权。两种常见表示是邻接表(每个节点存其邻居列表)和邻接矩阵(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 集合避免成环。
相关术语
相关资源
相关课程
- 数据结构
学习图与遍历。
解读错误信息
用大白话解释常见错误——什么意思、为什么发生、如何修复。